栅格化圆环/圆环的算法

Question

我想将 2d 甜甜圈

栅格化为矩阵/像素（结果应该是填充的甜甜圈）。

甜甜圈由 r1， r2， x0， y0 定义。

我怀疑最佳解决方案是布雷森汉姆算法的某些功能 https://en.wikipedia.org/wiki/Midpoint_circle_algorithm

有什么想法吗？

Answer 1

是的，可以用布雷森汉姆圆或中点算法填充甜甜圈。

开始第一象限的内圆和外圆的平行行走。在 Y 更改时构建水平段。到达顶部时停止步行到内圈，继续外圈。

请注意，您必须记住第一个（最大的）外部 X 值，但对于相同的 Y，最后一个（最小的）内部 X 值。

Answer 2

布雷森汉姆现在远非最佳......利用圆方程怎么样：

(x-x0)^2 + (x-y0)^2 = r^2

所以让我们：

x0,y0 - center
r1 - outer radius
r2 - inner radius
r1<=r2
xs,ys - screen resolution
scr[ys][xy] - screen matrix

在C++中，它看起来像这样：

int x,y,xx,yy,rr,rr1=r1*r1,rr2=r2*r2;
for (y=y0-r1;y<=y0+r1;y++)                  // loop all y positions
 if ((y>=0)&&(y<ys))                        // clip to screen
  for (yy=y-y0,yy*=yy,x=x0-r1;x<=x0+r1;x++) // loop all x positions
   if ((x>=0)&&(x<xs))                      // clip to screen
    {
    xx=x-x0; xx*=xx; rr=xx+yy;
    if ((rr>=rr2)&&(rr<=rr1))               // is in between radiuses?
     scr[y][x]=fill_color;
    }

您可以通过预先计算屏幕内两个循环的边界来轻松摆脱屏幕剪辑if语句......

对于填充圆，这种方法通常比布雷森汉姆更快，更不用说易于并行化了。