绘制实心圆的快速算法？

Question

我正在使用Bresenham's circle algorithm进行快速绘制圆形图。但是，我也想（根据用户的要求）绘制一个实心圆。

有没有一种快速有效的方法呢？布雷森汉姆有同样的线条吗？

的语言，我现在用的就是C.

Answer 1

看了the Wikipedia page on Bresenham's (also 'Midpoint') circle algorithm，这样看来，最容易做的事情是修改自己的行动，使得代替

setPixel(x0 + x, y0 + y); 
setPixel(x0 - x, y0 + y); 

和类似的，每次你，而不是做

lineFrom(x0 - x, y0 + y, x0 + x, y0 + y); 

也就是说，对于每一对点（具有相同的y）Bresenham你会有你阴谋，你改为连线。

Answer 2

这里有一个C＃粗略的指南（不应该是很难获得对C正确的想法） - 这是“原始”的形式，而无需使用布氏消除重复平方根。

Bitmap bmp = new Bitmap(200, 200); 

int r = 50; // radius 
int ox = 100, oy = 100; // origin 

for (int x = -r; x < r ; x++) 
{ 
    int height = (int)Math.Sqrt(r * r - x * x); 

    for (int y = -height; y < height; y++) 
     bmp.SetPixel(x + ox, y + oy, Color.Red); 
} 

bmp.Save(@"c:\users\dearwicker\Desktop\circle.bmp"); 

Answer 3

我只是生成一个点的列表，然后使用多边形绘制函数进行渲染。

Answer 4

只需使用蛮力。这种方法遍历几个像素过多，但它只使用整数乘法和加法。您完全避免了Bresenham的复杂性和sqrt的可能瓶颈。

for(int y=-radius; y<=radius; y++) 
    for(int x=-radius; x<=radius; x++) 
     if(x*x+y*y <= radius*radius) 
      setpixel(origin.x+x, origin.y+y); 

Answer 5

如果你想要一个快速的算法，考虑用N个边绘制一个多边形，N越高，圆越精确。

Answer 6

这里是我如何做它：
我使用的固定点值有两个位精度（我们不得不管理半分和半分平方值）
正如在前面的回答mentionned，我m也使用平方值而不是平方根。
首先，我在圈子的1/8部分检测我的圈子的边界限制。我使用这些点的对称来绘制圆的4个“边界”。然后我画圆圈内的方块。

与中点圆算法不同的是，它可以使用均匀的直径（并且具有实数直径也有一些小的变化）。

请原谅我，如果我的解释是不明确的，我是法国人;）

void DrawFilledCircle(int circleDiameter, int circlePosX, int circlePosY) 
{ 
    const int FULL = (1 << 2); 
    const int HALF = (FULL >> 1); 

    int size = (circleDiameter << 2);// fixed point value for size 
    int ray = (size >> 1); 
    int dY2; 
    int ray2 = ray * ray; 
    int posmin,posmax; 
    int Y,X; 
    int x = ((circleDiameter&1)==1) ? ray : ray - HALF; 
    int y = HALF; 
    circlePosX -= (circleDiameter>>1); 
    circlePosY -= (circleDiameter>>1); 

    for (;; y+=FULL) 
    { 
     dY2 = (ray - y) * (ray - y); 

     for (;; x-=FULL) 
     { 
      if (dY2 + (ray - x) * (ray - x) <= ray2) continue; 

      if (x < y) 
      { 
       Y = (y >> 2); 
       posmin = Y; 
       posmax = circleDiameter - Y; 

       // Draw inside square and leave 
       while (Y < posmax) 
       { 
        for (X = posmin; X < posmax; X++) 
         setPixel(circlePosX+X, circlePosY+Y); 
        Y++; 
       } 
       // Just for a better understanding, the while loop does the same thing as: 
       // DrawSquare(circlePosX+Y, circlePosY+Y, circleDiameter - 2*Y); 
       return; 
      } 

      // Draw the 4 borders 
      X = (x >> 2) + 1; 
      Y = y >> 2; 
      posmax = circleDiameter - X; 
      int mirrorY = circleDiameter - Y - 1; 

      while (X < posmax) 
      { 
       setPixel(circlePosX+X, circlePosY+Y); 
       setPixel(circlePosX+X, circlePosY+mirrorY); 
       setPixel(circlePosX+Y, circlePosY+X); 
       setPixel(circlePosX+mirrorY, circlePosY+X); 
       X++; 
      } 
      // Just for a better understanding, the while loop does the same thing as: 
      // int lineSize = circleDiameter - X*2; 
      // Upper border: 
      // DrawHorizontalLine(circlePosX+X, circlePosY+Y, lineSize); 
      // Lower border: 
      // DrawHorizontalLine(circlePosX+X, circlePosY+mirrorY, lineSize); 
      // Left border: 
      // DrawVerticalLine(circlePosX+Y, circlePosY+X, lineSize); 
      // Right border: 
      // DrawVerticalLine(circlePosX+mirrorY, circlePosY+X, lineSize); 

      break; 
     } 
    } 
} 

void DrawSquare(int x, int y, int size) 
{ 
    for(int i=0 ; i<size ; i++) 
     DrawHorizontalLine(x, y+i, size); 
} 

void DrawHorizontalLine(int x, int y, int width) 
{ 
    for(int i=0 ; i<width ; i++) 
     SetPixel(x+i, y); 
} 

void DrawVerticalLine(int x, int y, int height) 
{ 
    for(int i=0 ; i<height ; i++) 
     SetPixel(x, y+i); 
} 

使用非整数直径，可以增加固定点的精度或使用双值。 根据dY2 +（ray-x）*（ray-x）和ray2（dx²+dy²和r²）之间的差异，甚至可以制作一种抗混叠类型

Answer 7

您可以使用这个：

void DrawFilledCircle(int x0, int y0, int radius) 
{ 
    int x = radius; 
    int y = 0; 
    int xChange = 1 - (radius << 1); 
    int yChange = 0; 
    int radiusError = 0; 

    while (x >= y) 
    { 
     for (int i = x0 - x; i <= x0 + x; i++) 
     { 
      SetPixel(i, y0 + y); 
      SetPixel(i, y0 - y); 
     } 
     for (int i = x0 - y; i <= x0 + y; i++) 
     { 
      SetPixel(i, y0 + x); 
      SetPixel(i, y0 - x); 
     } 

     y++; 
     radiusError += yChange; 
     yChange += 2; 
     if (((radiusError << 1) + xChange) > 0) 
     { 
      x--; 
      radiusError += xChange; 
      xChange += 2; 
     } 
    } 
} 

Answer 8

我喜欢palm3D的回答。对于蛮力来说，这是一个非常快速的解决方案。没有平方根或三角函数来减慢速度。它的一个弱点是嵌套循环。

将此转换为单个循环使该功能几乎快两倍。

int r2 = r * r; 
int area = r2 << 2; 
int rr = r << 1; 

for (int i = 0; i < area; i++) 
{ 
    int tx = (i % rr) - r; 
    int ty = (i/rr) - r; 

    if (tx * tx + ty * ty <= r2) 
     SetPixel(x + tx, y + ty, c); 
} 

这种单环解决方案可以与线绘图解决方案的效率相媲美。

  int r2 = r * r; 
      for (int cy = -r; cy <= r; cy++) 
      { 
       int cx = (int)(Math.Sqrt(r2 - cy * cy) + 0.5); 
       int cyy = cy + y; 

       lineDDA(x - cx, cyy, x + cx, cyy, c); 
      }