ここでの基本的な問題は、円の「上」にあるすべての点が円の中心から数学的に正しい距離を持っていると仮定していることです。
ピクセルは固定グリッド上にあり、円の解像度は無限であるため、実際にはそうではありません。距離がわずかに内側または外側になります。
これは、円の「上」にあると計算される反復ごとにほんの一握りのピクセルしかないことを意味し、したがって、円のすべてのピクセルがカウントされることはありません。
あなたのアルゴリズムの前提は理解していますが、円のピクセルの 1 つを別の方法で見つけたかどうかを調べる必要があります。これは、ピクセル グリッドと最適な円の位置のわずかな違いを説明するものです。
さらに、その特定のタイプの形状に対してのみ行っている場合は、単純に数学的に行ってみませんか? 外接円は簡単に計算できます。その半径は中心から角の 1 つまでの距離であり、内接円は中心からエッジの 1 つの中心までの距離です。
確かに、ランダムな形状に対してそれを行う必要がある場合、それは機能しませんが、別の問題があります。中心をどこに配置しますか?
ここで説明しましょう：
ここでは、半径 4 の円を示しています。黄色のピクセルは中心であり、赤は数式に従って数学的に円に正確に収まるものです。画像以外に2点あります。
ただし、2 つの緑が問題です。
X=-1 (中心から左に 1)、Y=-4 (中心から上に 4) の A の場合、式は次のようになります。
(-1)*(-1) + (-4)*(-4) == 4*4
1 + 16 == 16
17 == 16
少し内側にある B の場合、Y=-3 になります。
(-1)*(-1) + (-3)*(-3) == 4*4
1 + 9 == 16
10 == 16
ご覧のとおり、円を構成するすべてのピクセルを見つけるアプローチには欠陥があります。実際、ほとんどの場合、中央の上下左右の 4 ピクセルだけが見つかり、あちこちに奇数のピクセルが見つかることもあります。
少なくとも、ブレゼンハムのサークルアルゴリズムまたはミッドポイントサークルアルゴリズムでサークル検索アルゴリズムを変更します。
IEnumerable<Point> MidpointCirclePoints(int x0, int y0, int radius)
{
int x = radius;
int y = 0;
int radiusError = 1 - x;
while (x >= y)
{
yield return new Point(x + x0, y + y0);
yield return new Point(y + x0, x + y0);
yield return new Point(-x + x0, y + y0);
yield return new Point(-y + x0, x + y0);
yield return new Point(-x + x0, -y + y0);
yield return new Point(-y + x0, -x + y0);
yield return new Point(x + x0, -y + y0);
yield return new Point(y + x0, -x + y0);
y++;
if (radiusError < 0)
radiusError += 2 * y + 1;
else
{
x--;
radiusError += 2 * (y - x) + 1;
}
}
}
これにより、円上にあるすべてのポイントがすべて検出されますが、一部のポイントは 2 回返される可能性があることに注意してください。特に、右上、下、左、右のピクセル、および 45 度ごとのポイントです。
ただし、中心を正しく配置する方法がないため、ピクセルのランダムな塊に対してはアルゴリズムが正しく機能しないことに注意してください。これは厳密に対称的な形状でのみ機能します。
LINQPadで試すことができる完全な動作例を次に示します。
void Main()
{
int size = 256;
int radius = 110; // of the square, not of the circles
var b = new Bitmap(size, size);
using (Graphics g = Graphics.FromImage(b))
{
g.Clear(Color.White);
g.FillPolygon(Brushes.Black, new[]
{
new Point(size / 2, size / 2 - radius),
new Point(size / 2 + radius, size / 2),
new Point(size / 2, size / 2 + radius),
new Point(size / 2 - radius, size / 2)
});
}
int incircleRadius;
int circumcircleRadius;
if (FindCircles(b, out incircleRadius, out circumcircleRadius))
{
using (Graphics g = Graphics.FromImage(b))
{
g.DrawEllipse(Pens.Red, new Rectangle(
size / 2 - circumcircleRadius, size / 2 - circumcircleRadius,
circumcircleRadius * 2 + 1, circumcircleRadius * 2 + 1));
g.DrawEllipse(Pens.Blue, new Rectangle(
size / 2 - incircleRadius, size / 2 - incircleRadius,
incircleRadius * 2 + 1, incircleRadius * 2 + 1));
}
}
b.Dump();
}
bool FindCircles(Bitmap input, out int incircleRadius, out int circumcircleRadius)
{
int midX = input.Width / 2; // already we're introducing inaccuracies
int midY = input.Height / 2; // what if the bitmap is an even number?
int largestPossibleRadius = Math.Min(midX, midY);
incircleRadius = 0;
circumcircleRadius = 0;
for (int r = 30; r < largestPossibleRadius; r++)
{
bool allBlack = true;
bool allWhite = true;
// Bresenhams Circle Algorithm
foreach (Point p in MidpointCirclePoints(midX, midY, r))
{
// input.GetPixel(p.X, p.Y).R.Dump();
bool isBlack = input.GetPixel(p.X, p.Y).R < 128; // dummy test
if (isBlack)
{
// input.SetPixel(p.X, p.Y, Color.Green);
allWhite = false;
}
else
{
// input.SetPixel(p.X, p.Y, Color.Green);
allBlack = false;
}
// Debug
// input.SetPixel(p.X, p.Y, Color.Green);
}
if (allBlack)
{
incircleRadius = r;
}
else if (allWhite)
{
circumcircleRadius = r - 1;
break;
}
}
return incircleRadius > 0 && circumcircleRadius > 0;;
}
IEnumerable<Point> MidpointCirclePoints(int x0, int y0, int radius)
{
int x = radius;
int y = 0;
int radiusError = 1 - x;
while (x >= y)
{
yield return new Point(x + x0, y + y0);
yield return new Point(y + x0, x + y0);
yield return new Point(-x + x0, y + y0);
yield return new Point(-y + x0, x + y0);
yield return new Point(-x + x0, -y + y0);
yield return new Point(-y + x0, -x + y0);
yield return new Point(x + x0, -y + y0);
yield return new Point(y + x0, -x + y0);
y++;
if (radiusError < 0)
radiusError += 2 * y + 1;
else
{
x--;
radiusError += 2 * (y - x) + 1;
}
}
}
出力：
