Is there a simple algorithm for calculating the maximum inscribed circle into a convex polygon?

Yes. The Chebyshev center, x*, of a set C is the center of the largest ball that lies inside C. [Boyd, p. 416] When C is a convex set, then this problem is a convex optimization problem.

Better yet, when C is a polyhedron, then this problem becomes a linear program.

Suppose the m-sided polyhedron C is defined by a set of linear inequalities: ai^T x <= bi, for i in {1, 2, ..., m}. Then the problem becomes

maximize  R
such that ai^T x + R||a|| <= bi,  i in {1, 2, ..., m}
          R >= 0

where the variables of minimization are R and x, and ||a|| is the Euclidean norm of a.


Summary: It is not trivial. So it is very unlikely that it will not get messy. But there are some lecture slides which you may find useful.

Source: http://www.eggheadcafe.com/software/aspnet/30304481/finding-the-maximum-inscribed-circle-in-c.aspx

Your problem is not trivial, and there is no C# code that does this straight out of the box. You will have to write your own. I found the problem intriguing, and did some research, so here are a few clues that may help.

First, here's an answer in "plain English" from mathforum.org:

http://mathforum.org/library/drmath/view/67030.html

The answer references Voronoi Diagrams as a methodology for making the process more efficient. In researching Voronoi diagrams, in conjunction with the "maximum empty circle" problem (same problem, different name), I came across this informative paper:

http://www.cosy.sbg.ac.at/~held/teaching/compgeo/slides/vd_slides.pdf

It was written by Martin Held, a Computational Geometry professor at the University of Salzberg in Austria. Further investigation of Dr. Held's writings yielded a couple of good articles:

http://www.cosy.sbg.ac.at/~held/projects/vroni/vroni.html http://www.cosy.sbg.ac.at/~held/projects/triang/triang.html

Further research into Vornoi Diagrams yielded the following site:

http://www.voronoi.com/

This site has lots of information, code in various languages, and links to other resources.

Finally, here is the URL to the Mathematics and Computational Sciences Division of the National Institute of Standards and Technology (U.S.), a wealth of information and links regarding mathematics of all sorts:

http://math.nist.gov/mcsd/

-- HTH,

Kevin Spencer Microsoft MVP


Perhaps these "too messy" solutions are what you actually looking for, and there are no simplier ones?

I can suggest a simple, but potentially imprecise solution, which uses numerical analysis. Assume you have a resilient ball, and you inflate it, starting from radius zero. If its center is not in the center you're looking for, then it will move, because the walls would "push" it in the proper direction, until it reaches the point, from where he can't move anywhere else. I guess, for a convex polygon, the ball will eventually move to the point where it has maximum radius.

You can write a program that emulates the process of circle inflation. Start with an arbitrary point, and "inflate" the circle until it reaches a wall. If you keep inflating it, it will move in one of the directions that don't make it any closer to the walls it already encounters. You can determine the possible ways where it could move by drawing the lines that are parallel to the walls through the center you're currently at.

In this example, the ball would move in one of the directions marked with green:


(source: coldattic.info)

Then, move your ball slightly in one of these directions (a good choice might be moving along the bisection of the angle), and repeat the step. If the new radius would be less than the one you have, retreat and decrease the pace you move it. When you'll have to make your pace less than a value of, say, 1 inch, then you've found the centre with precision of 1 in. (If you're going to draw it on a screen, precision of 0.5 pixel would be good enough, I guess).

If an imprecise solution is enough for you, this is simple enough, I guess.