中点円アルゴリズムは、円の境界をラスタライズするために使用できます。ただし、ピクセルを複数回描画せずに円を塗りつぶしたい（これは非常に重要です）。
この回答は、塗りつぶされた円を生成するアルゴリズムの変更を提供しますが、一部のピクセルは数回アクセス されます。塗りつぶされた円を描画するための高速アルゴリズム？
Q：ピクセルを複数回描画せずに円をラスタライズするにはどうすればよいですか？RAMは非常に限られていることに注意してください！
アップデート：
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace CircleTest
{
class Program
{
static void Main(string[] args)
{
byte[,] buffer = new byte[50, 50];
circle(buffer, 25, 25, 20);
for (int y = 0; y < 50; ++y)
{
for (int x = 0; x < 50; ++x)
Console.Write(buffer[y, x].ToString());
Console.WriteLine();
}
}
// 'cx' and 'cy' denote the offset of the circle center from the origin.
static void circle(byte[,] buffer, int cx, int cy, int radius)
{
int error = -radius;
int x = radius;
int y = 0;
// The following while loop may altered to 'while (x > y)' for a
// performance benefit, as long as a call to 'plot4points' follows
// the body of the loop. This allows for the elimination of the
// '(x != y)' test in 'plot8points', providing a further benefit.
//
// For the sake of clarity, this is not shown here.
while (x >= y)
{
plot8points(buffer, cx, cy, x, y);
error += y;
++y;
error += y;
// The following test may be implemented in assembly language in
// most machines by testing the carry flag after adding 'y' to
// the value of 'error' in the previous step, since 'error'
// nominally has a negative value.
if (error >= 0)
{
error -= x;
--x;
error -= x;
}
}
}
static void plot8points(byte[,] buffer, int cx, int cy, int x, int y)
{
plot4points(buffer, cx, cy, x, y);
if (x != y) plot4points(buffer, cx, cy, y, x);
}
// The '(x != 0 && y != 0)' test in the last line of this function
// may be omitted for a performance benefit if the radius of the
// circle is known to be non-zero.
static void plot4points(byte[,] buffer, int cx, int cy, int x, int y)
{
#if false // Outlined circle are indeed plotted correctly!
setPixel(buffer, cx + x, cy + y);
if (x != 0) setPixel(buffer, cx - x, cy + y);
if (y != 0) setPixel(buffer, cx + x, cy - y);
if (x != 0 && y != 0) setPixel(buffer, cx - x, cy - y);
#else // But the filled version plots some pixels multiple times...
horizontalLine(buffer, cx - x, cy + y, cx + x);
//if (x != 0) setPixel(buffer, cx - x, cy + y);
//if (y != 0) setPixel(buffer, cx + x, cy - y);
//if (x != 0 && y != 0) setPixel(buffer, cx - x, cy - y);
#endif
}
static void setPixel(byte[,] buffer, int x, int y)
{
buffer[y, x]++;
}
static void horizontalLine(byte[,] buffer, int x0, int y0, int x1)
{
for (int x = x0; x <= x1; ++x)
setPixel(buffer, x, y0);
}
}
}
関連する結果は次のとおりです。
00000111111111111111111111111111111111111111110000
00000111111111111111111111111111111111111111110000
00000111111111111111111111111111111111111111110000
00000111111111111111111111111111111111111111110000
00000111111111111111111111111111111111111111110000
00000011111111111111111111111111111111111111100000
00000011111111111111111111111111111111111111100000
00000011111111111111111111111111111111111111100000
00000001111111111111111111111111111111111111000000
00000001111111111111111111111111111111111111000000
00000000111111111111111111111111111111111110000000
00000000111111111111111111111111111111111110000000
00000000011111111111111111111111111111111100000000
00000000001111111111111111111111111111111000000000
00000000000111111111111111111111111111110000000000
00000000000011111111111111111111111111100000000000
00000000000001111111111111111111111111000000000000
00000000000000122222222222222222222210000000000000
00000000000000001222222222222222221000000000000000
00000000000000000012333333333332100000000000000000
00000000000000000000012345432100000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
下のピクセルが何度もプロットされています。ここで何が欠けていますか？
アップデート＃2：このソリューションは機能します：
static void circle(byte[,] buffer, int cx, int cy, int radius)
{
int error = -radius;
int x = radius;
int y = 0;
while (x >= y)
{
int lastY = y;
error += y;
++y;
error += y;
plot4points(buffer, cx, cy, x, lastY);
if (error >= 0)
{
if (x != lastY)
plot4points(buffer, cx, cy, lastY, x);
error -= x;
--x;
error -= x;
}
}
}
static void plot4points(byte[,] buffer, int cx, int cy, int x, int y)
{
horizontalLine(buffer, cx - x, cy + y, cx + x);
if (y != 0)
horizontalLine(buffer, cx - x, cy - y, cx + x);
}
