algorithm - 圆周上每一点的坐标

Question

首先，请注意，这个问题不是这些问题的重复:1st , 2nd , 和 3rd .

我正在使用 delphi 和 openCV，但我正在寻找一种算法，一种与语言无关的解决方案。

为了进行精确的图像分析，我需要检查圆形区域中像素强度的变化。所以我读取了不断增长的圆周上的像素值。为了能够做到这一点，我当然需要知道像素的坐标。

我找到的最佳解决方案是 y:= Round(centerY + radius * sin(angle)), x:= Round(centerX + radius * cos(angle))，而因为用只有 360 度是不够的，当圆的半径大于大约 60px 时，角度是这样计算的 angle:= angle + (360/(2 * 3.14 * currentRadius)) -> 我扫过从 0 到 360 的每个值，同时该值以 360/圆周长的分数递增(以像素为单位)。但是这种方法不是很精确。圆越大，所需的角度分数越小，精度受到 Pi 的不准确度和舍入的影响。

如果我使用提到的方法，并尝试用这段代码绘制计数的像素:

  centerX:= 1700;
  centerY:= 1200;
  maxRadius:= 500;

  for currentRadius:= 80 to maxRadius do
  begin

    angle:= 0;
    while angle < 360 do
    begin

      xI:= Round(centerX + currentRadius * cos(angle));
      yI:= Round(centerY + currentRadius * sin(angle));
      angle:= angle + (360 / (2 * 3.14 * currentRadius));

      //this is openCV function, to test the code, you can use anything, that will draw a dot...
      cvLine(image,cvPoint(xI,yI),cvPoint(xI,yI),CV_RGB(0, 255, 0));

    end;

  end;

结果是这样的:

这还不错，但考虑到圆形区域中大约三分之一的像素是黑色，您会发现很多像素已被“跳过”。再加上仔细观察最后一个圆的边缘，可以清楚地看到一些点偏离实际圆周 - 另一个不准确的结果......

我可能会使用公式 (x - xorig)^2 + (y - yorig)^2 = r^2 来检查中心周围的矩形区域中的每个可能像素，稍微大一点，而不是圆的直径，如果它落在或不落在圆的圆周上。但是，随着圈子的扩大，一直重复它会很慢。

有什么可以做得更好的吗？谁能帮我改进这个？我根本不坚持我的解决方案中的任何内容，并且会接受任何其他解决方案，只要它能提供所需的结果 => 让我读取 all 的值(或绝大多数 - 95 %+) 给定圆心和半径的圆的圆周上的像素。越快越好...

Answer 1

1) 构建最小半径圆周的像素列表。这足以保留圆的第一个八分圆(坐标系第一象限范围0..Pi/4)，得到带反射的对称点。例如，您可以使用 Bresenham 圆算法或仅使用圆方程。

2) 对于下一次迭代，遍历列表中的所有坐标(如果有两个点具有相同的 Y 值，则使用右坐标)并检查右邻居(或两个邻居!)是否位于下一个半径内。对于最后一个点，还要检查顶部的右上邻居(在 Pi/4 对角线处)。将好邻居(一个或两个)插入下一个坐标列表。

 Example for Y=5.
 R=8   X=5,6 //note that (5,5) point is not inside r=7 circle
 R=9   X=7
 R=10  X=8
 R=11  X=9
 R=12  X=10
 R=13  X=11,12 //!
 R=14  X=13

通过这种方法，您将无间隙地使用最大半径圆中的所有像素，并且列表生成的检查过程相当快。

编辑:代码实现了另一种方法，它使用下线像素限制来构建上线。

它在给定范围内生成圆圈，将它们涂成迷幻的颜色。所有数学都是整数，没有 float ，没有三角函数! 像素仅用于演示目的。

procedure TForm1.Button16Click(Sender: TObject);

  procedure FillCircles(CX, CY, RMin, RMax: Integer);

    //control painting, slow due to Pixels using
    procedure PaintPixels(XX, YY, rad: Integer);
    var
      Color: TColor;
      r, g, B: Byte;
    begin
      g := (rad mod 16) * 16;
      r := (rad mod 7) * 42;
      B := (rad mod 11) * 25;
      Color := RGB(r, g, B);
     // Memo1.Lines.Add(Format('%d  %d  %d', [rad, XX, YY]));
      Canvas.Pixels[CX + XX, CY + YY] := Color;
      Canvas.Pixels[CX - YY, CY + XX] := Color;
      Canvas.Pixels[CX - XX, CY - YY] := Color;
      Canvas.Pixels[CX + YY, CY - XX] := Color;
      if XX <> YY then begin
        Canvas.Pixels[CX + YY, CY + XX] := Color;
        Canvas.Pixels[CX - XX, CY + YY] := Color;
        Canvas.Pixels[CX - YY, CY - XX] := Color;
        Canvas.Pixels[CX + XX, CY - YY] := Color;
      end;
    end;

  var
    Pts: array of array [0 .. 1] of Integer;
    iR, iY, SqD, SqrLast, SqrCurr, MX, LX, cnt: Integer;
  begin
    SetLength(Pts, RMax);

    for iR := RMin to RMax do begin
      SqrLast := Sqr(iR - 1) + 1;
      SqrCurr := Sqr(iR);
      LX := iR; // the most left X to check

      for iY := 0 to RMax do begin
        cnt := 0;
        Pts[iY, 1] := 0; // no second point at this Y-line
        for MX := LX to LX + 1 do begin
          SqD := MX * MX + iY * iY;
          if InRange(SqD, SqrLast, SqrCurr) then begin
            Pts[iY, cnt] := MX;
            Inc(cnt);
          end;
        end;

        PaintPixels(Pts[iY, 0], iY, iR);
        if cnt = 2 then
          PaintPixels(Pts[iY, 1], iY, iR);

        LX := Pts[iY, 0] - 1; // update left limit
        if LX < iY then // angle Pi/4 is reached
          Break;
      end;
    end;
    // here Pts contains all point coordinates for current iR radius
    //if list is not needed, remove Pts, just use PaintPixels-like output
  end;

begin
  FillCircles(100, 100, 10, 100);
  //enlarge your first quadrant to check for missed points
  StretchBlt(Canvas.Handle, 0, 200, 800, 800, Canvas.Handle, 100, 100, 100,
    100, SRCCOPY);
end;