快速algorithm绘制实心圆？
我正在使用Bresenham的圆圈algorithm进行快速绘制圆圈。 不过，我也想（根据用户的要求）画一个实心圆。
有没有一种快速有效的方法呢？ 布雷森汉姆的相同的东西？
我使用的语言是C.
在阅读了Bresenham（也是“Midpoint”）圈子algorithm的维基百科页面之后 ，似乎要做的最简单的事情就是修改它的行为，而不是
setPixel(x0 + x, y0 + y); setPixel(x0 - x, y0 + y); 和类似的，每次你反而做
lineFrom(x0 - x, y0 + y, x0 + x, y0 + y);
也就是说，对于Bresenham的每一对点（与y相同），你可以绘制 一条线 ，而不是连线 。
只要使用暴力。 这种方法迭代了太多像素，但它只使用整数乘法和加法。 您完全避免了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);
这里有一个C＃的粗略指南（不应该很难得到正确的想法C） – 这是没有使用Bresenham消除重复的平方根的“原始”forms。
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");
你可以使用这个：
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; } } }
我喜欢palm3D的答案。 对于蛮力，这是一个惊人的快速解决scheme。 没有平方根或三angular函数来减慢速度。 它的一个弱点是嵌套循环。
把它转换成一个单一的循环使得这个函数几乎快两倍。
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); }
这种单回路解决scheme可以与线路绘图解决scheme的效率相媲美。
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); }
以下是我如何做到这一点：
我使用两位精度的定点值（我们必须pipe理半点的半点和平方值）
正如在前面的答案中提到的，我也使用平方值而不是平方根。
首先，我在圈子的1/8部分检测我的圈子的边界限制。 我使用这些点的对称来绘制圆的4个“边界”。 然后我画圈内的广场。
与中点圆algorithm不同的是，这个algorithm可以处理的是直径（即实际的数字直径也有一些小的变化）。
请原谅我，如果我的解释不清楚，我是法国人;）
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²）之间的差别，甚至可以制作一个抗混叠
如果你想要一个快速的algorithm，考虑绘制一个N边的多边形，N越高，圆越精确。
我只会生成一个点列表，然后使用多边形绘制函数进行渲染。
