Maximum inscribed circle in any polygon

[littlekid]

The problem is to find a maximum inscribed circle in any polygon (maybe convex or concave).

(Having the topic "Maximum inscribed circle in a convex polygon" in this board,
I'm curious about whether there are any solutions if the polygon is concave. )

[ericschmidt]

I saw this really old post - but I like the problem - so I thought about it for while.

Here's my a solution. It's a kind of "flooding" algorithm.
1.) Use a rectangular map with the polygon completely inside (not touching the edges)
2.) Initialize each dot of your map with 0 (="not forbidden as center of the circle")
3.) Mark one corner of your map with 1 (="forbidden as center of the circle")
4.) flood your map with 1s starting from that corner (do not cross a polygon line while flooding)
5.) start with r=0 into a while loop where you continously increase r until the last dot is marked with 1
in the loop: mark a circle of radius r around each polygon vertex with 1s
in the loop: mark a line parallel to each polygon edge - of same length but shifted parallel by r towards the 0s - with 1s
6.) The last dot that was marked with 1 is the center of the maximum circle and r is the radius

This also works if a concave polygon somehow "splits" the remaining map space into several islands.

[VickieMikkelson]

Need to calculate the size of a square peg to whittle down end to a rough octagon to fit into a round hole.

[ericschmidt]

Hi VickieMikkelson,

Sounds like you have a clean geometric question. If the drawing in http://jwilson.coe.uga.edu/emt725/Octagon/Octagon.html next to item 8 is what you are looking for, there's an analytical answer: The square peg has to have a side with width w = r*(1+sqrt(2))/sqrt(1+sqrt(0.5))