圆周上每个点的坐标

Question

首先，请注意，这个问题不是这些问题的重复：1st、2nd和3rd。

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

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

我找到的最好的解决方案是y:= Round(centerY + radius * sin(angle)), x:= Round(centerX + radius * cos(angle))，因为只用 360 度计数是不够的，当圆的半径大于大约 60 像素时，角度是这样计算的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来检查围绕中心的矩形区域中的每个可能的像素，该区域比圆的直径稍大，如果它落在或没有落在圆的圆周上。但是随着圆圈的扩大，一直重复它会非常缓慢。

有什么可以做得更好的吗？有人可以帮我改进这个吗？我根本不坚持我的解决方案中的任何内容，并且会接受任何其他解决方案，只要它给出所需的结果 => 让我读取圆周上所有（或绝大多数 - 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

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

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

它在给定范围内生成圆圈，将它们绘制成迷幻的颜色。所有数学都是整数，没有浮点数，没有三角函数！Pixels仅用于演示目的。

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;