繪製實心圓的快速算法？

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); 
      }