在c#中找到一个形状的外接圆和内圆

Question

我需要找到这种形状的外接圆和内圆

我的代码找到了外接圆,但是外圆是错的

for (int r = 1; ; r++) //r is radius
{
    int found = 0; //counts found pixels
    int wrong = 0; //counts pixels that are on the circle but have different color that desirable
    int good = 0; //counts pixels that are on the circle with desirable color
    for (int y = point.Y - r ; y <= point.Y + r ; y++) //point is the center of the figure (110,110)
    {
        for (int x = point.X - r ; x <= point.X + r; x++)
        {
            if((x - point.X) * (x - point.X) + (y - point.Y)*(y - point.Y) == r*r) //is on the circle
            {
                found++;
                if (img.GetPixel(x, y).ToArgb() != color.ToArgb()) // has given color (black)
                {
                    wrong++;
                }
                else 
                {
                    good++;
                }

            }
        }
    }
    outerRadius = r;
    if (found == wrong) break; //circumcircle found
    if (found == good) innerRadius = r; //incircle found
  }

结果我得到了这个:(红色外圈,蓝色外圈)

我找不到为什么这不起作用.请帮我.

Answer 1

这里的基本问题是你假设圆圈"上"的点在数学上都与圆心有正确的距离.

实际上,他们不会,因为像素位于固定网格上,所以它们将具有略微内部或外部的距离,并且圆圈具有无限分辨率.

这意味着每次迭代只有少数几个像素将被计算为"在圆圈上",因此发现永远不会计算圆的所有像素.

我理解你的算法的前提,但你需要弄清楚你是否以不同的方式找到了圆的一个像素,一个将解释像素网格和最佳圆位置之间的微小差异.

另外,如果你只是为那种特殊形状做这件事,为什么不简单地用数学方法做呢？外接圆很容易计算,其半径只是从中心到其中一个角的距离,而外圆是从中心到其中一个边的中心的距离.

当然,如果你需要为随机形状做这件事,那那就不行了,但是你有一个不同的问题,你在哪里放置中心？

这里让我说明一下:

这里我展示了一个半径为4的圆.黄色像素是中心,红色是完全落在圆上的,根据你的公式,数学方面.图像外还有2个额外的.

然而,这两个绿色是问题所在.

对于A,其中X = -1(中间左侧1),Y = -4(中心上方4),您的公式最终为:

(-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

如您所见,您找到构成圆圈的所有像素的方法存在缺陷.事实上,很可能你只是直接向上,向下,向左或向右找到中心的四个像素,有时只有奇数像素.

至少我会用Bresenham的圆算法或中点圆算法改变你的圆寻找算法:

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

这将找到圆圈上的所有点,所有这些点,但请注意,某些点可以返回两次,特别是在右上,下,左右像素和每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;
        }
    }
}

输出: