圆圆周上每个点的坐标 [英] Coordinates of every point on a circle's circumference

问题描述

首先，请注意，这个问题不是这些的重复:第二和

First, please note, that this question is not a duplicate of these: 1st , 2nd , and 3rd.

我正在使用delphi和openCV，但是我正在寻找一种算法，无论使用哪种语言，都可以找到一种解决方案.

I am using delphi and openCV, but I am looking for an algorithm, a solution regardless of the language.

出于精确图像分析的目的，我需要检查圆形区域中像素强度的变化.因此，我在连续增长的圆周上读取像素值.为了做到这一点，我当然需要知道像素的坐标.

For the purpose of a precise image analysis, I need to check for changes in pixel intensity in circular areas. So I read pixel values on a circumference of continuously growing circle. To be able to do that, I of course need to know coordinates of the pixels.

我发现的最佳解决方案是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的不精确度以及圆角的影响.

The best solution I found is y:= Round(centerY + radius * sin(angle)), x:= Round(centerX + radius * cos(angle)), while because counting with only 360 degrees is hardly enough, when the radius of the circle is larger, than circa 60px, the angle is being counted like this angle:= angle + (360 / (2 * 3.14 * currentRadius)) -> I sweep through every value from 0 to 360, while the value is being incremented by a fraction of 360/circumference of the circle in pixels. But this approach is not very precise. The larger the circle, the smaller the fraction of the angle needs to be and the precission suffers from the inaccuracy of Pi, plus the rounding.

如果我使用上述方法，请尝试使用此代码绘制计数的像素:

If I use the mentioned method, and try to draw the counted pixels with this code:

  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;

结果是这样的:

这还不错，但考虑到圆形区域中所有像素的粗糙三分之一都是黑色，您会意识到很多像素已被跳过".再仔细观察最后一个圆的边缘，可以清楚地看到一些点偏离实际圆周，这是不准确的另一个结果...

It is not bad, but taking into account, that rougly a third of all pixels in the circular area are black, you realize, that a lot of pixels has been "skipped". Plus looking closely on the edge of the last circle, there is clearly visible, that some dots are off the actual circumference - another result of the inaccuracy...

我可能会使用公式(x - xorig)^2 + (y - yorig)^2 = r^2来检查中心周围矩形区域(比圆直径稍大)中的每个可能像素(如果存在)是否落在圆环的圆周上.但是，随着圈的不断扩大，要一直重复下去会很慢.

I could possibly use a formula (x - xorig)^2 + (y - yorig)^2 = r^2 to check every possible pixel in a rectangular area around the center, slightly bigger, than a diameter of the circle, if it does, or does't fall onto the cirle's circumference. But that would be very slow to repeat it all the time, as the circle grows.

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

Is there something, that could be done better? Could anyone help me to improve this? I don't insist on anything from my solution at all, and will accept any other solution, as long as it gives the desired results => let me read values of all (or the vast majority - 95%+) pixels on a circumference of a circle with given center and radius. The faster, the better...

推荐答案

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

1) Build a list of pixels of the smallest radius circumference. It is enough to keep the first octant (range 0..Pi/4 in the 1st quadrant of coordinate system) of circle, and get symmetric points with reflections. You can use, for example, Bresenham circle algorithm or just circle equation.

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

2) For the next iteration walk through all coordinates in the list (use right one, if there are two points with the same Y value) and check whether right neighbor (or two neighbors!) lies inside the next radius. For the last point check also top, right-top neighbor (at Pi/4 diagonal). Insert good neighbors (one or two) into the next coordinate list.

 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

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

With this approach you will use all the pixels in maximal radius circle without gaps, and checking process for list generation is rather fast.

修改: 代码稍微实现了另一种方法，它使用较低的行像素限制来构建较高的行.

Code implements slightly another approach, it uses lower line pixel limit to built upper line.

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

It generates circles in given range, paints them to psychedelic colors. All math is in integers, no floats, no trigonometric functions! Pixels are used only for demonstration purposes.

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;

这篇关于圆圆周上每个点的坐标的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！