Finding circumcircle and incircle of a shape in c#

Question

I need to find circumcircle and incircle of this shape

my code finds the circumcircle but the incircle is wrong

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
  }

as a result I get this: (red circumcircle, blue incircle)

I can't find why this is not working. Please help me.

Answer 1

The basic problem here is that you're assuming that the points that are "on" the circle all mathematically have the right distance from the center of the circle.

In truth, they won't, they will have a distance that is slightly inside or outside, since the pixels are on a fixed grid, and the circle has infinite resolution.

This means that there is only a handful of pixels every iteration that will be calculated to be "on" the circle, and thus found will never count all the pixels of the circle.

I understand the premise of your algorithm, but you need to figure out if you've found one of the pixels of the circle in a different manner, one that will account for the minor differences between the pixel grid and optimal circle position.

Additionally, if you're only doing it for that particular type of shape, why not simply do it mathematically? The circumcircle is easy to calculate, the radius of that is just the distance from the center to one of the corners, and the incircle is the distance from the center to the center of one of the edges.

Granted, if you need to do it for random shapes, then that won't work, but then you have a different problem, where do you place the center?

Here let me illustrate:

Here I have illustrated a circle with radius 4. The yellow pixel is the center, the red are the ones that fall exactly on the circle, mathematical-wise according to your formula. There are 2 additional ones outside the image.

The two green, however, are the problem.

For A, which has X=-1 (1 to the left of) the center, and Y=-4 (4 up above the center), your formula ends up as:

(-1)*(-1) + (-4)*(-4) == 4*4
    1     +    16     ==  16
          17          ==  16

For B, which is slightly inside, has Y=-3:

(-1)*(-1) + (-3)*(-3) == 4*4
    1     +     9     ==  16
         10           ==  16

So as you see, your approach to finding all the pixels that make up the circle is flawed. In fact, most likely you are only finding the four pixels directly up, down, left, or right, of the center, and only sometimes an odd pixel here and there.

At least I would change your circle finding algorithm with Bresenham's Circle Algorithm, or the Midpoint Circle Algorithm:

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

This will find all the points that are on the circle for, all of them, but note that some points can be returned twice, particular at the right up, down, left right pixels, and the ones at every 45 degrees.

But again, note that your algorithm will not work correctly for a random blob of pixels, since you will have no way to correctly place the center, this will only work with a strictly symmetrical shape

Here is a full working example that you can try in 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;
        }
    }
}

Output:

Answer 2

I would guess that your algorithm keeps searching. It looks like when it finds a black pixel, it assumes it's "good" for the inscribed circle. In your case, I think it ends up continually hitting the black pixels along the corners of the rectangle all the way to the circumscribed radius.

Really, once you have found any white pixel, the last good value for the inscribed should be the one you take. I haven't tested this, but I think it will work, or at least get you on the way to a solution:

bool isStillInscribed = true;
int inscribedCircleRadius = 0;
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
    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++;
                    //we are now outside the shape; cannot be inscribed anymore
                    isStillInscribed = false;
                }
            }
        }
    }

    //if the last checked circle radius still did not find any different 
    //coloured pixels, then this radius is still inscribed
    if (isStillInscribed)
        inscribedCircleRadius = r;

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