math - Finding circumcircle and incircle of a shape in c# -

i need find circumcircle , incircle of shape

my code finds circumcircle incircle wrong

for (int r = 1; ; r++) //r radius {     int found = 0; //counts found pixels     int wrong = 0; //counts pixels on circle have different color desirable     int = 0; //counts pixels on circle desirable color     (int y = point.y - r ; y <= point.y + r ; y++) //point center of figure (110,110)     {         (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 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 result this: (red circumcircle, blue incircle)

i can't find why not working. please me.

the basic problem here you're assuming points "on" circle mathematically have right distance center of circle.

in truth, won't, have distance inside or outside, since pixels on fixed grid, , circle has infinite resolution.

this means there handful of pixels every iteration calculated "on" circle, , found never count pixels of circle.

i understand premise of algorithm, need figure out if you've found 1 of pixels of circle in different manner, 1 account minor differences between pixel grid , optimal circle position.

additionally, if you're doing particular type of shape, why not mathematically? circumcircle easy calculate, radius of distance center 1 of corners, , incircle distance center center of 1 of edges.

granted, if need random shapes, won't work, have different problem, place center?

here let me illustrate:

here have illustrated circle radius 4. yellow pixel center, red ones fall on circle, mathematical-wise according formula. there 2 additional ones outside image.

the 2 green, however, problem.

for a, has x=-1 (1 left of) center, , y=-4 (4 above center), formula ends as:

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

for b, inside, has y=-3:

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

so see, approach finding pixels make circle flawed. in fact, finding 4 pixels directly up, down, left, or right, of center, , odd pixel here , there.

at least change circle finding algorithm bresenham's circle algorithm, or 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 find points on circle for, of them, note points can returned twice, particular @ right up, down, left right pixels, , ones @ every 45 degrees.

but again, note algorithm not work correctly random blob of pixels, since have no way correctly place center, work strictly symmetrical shape

here full working example can try in linqpad:

void main() {     int size = 256;     int radius = 110; // of square, not of 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; // we're introducing inaccuracies     int midy = input.height / 2; // if bitmap number?     int largestpossibleradius = math.min(midx, midy);      incircleradius = 0;     circumcircleradius = 0;      (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: