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. )
Maximum inscribed circle in any polygon
Moderator: Board moderators

 New poster
 Posts: 16
 Joined: Mon Jan 06, 2003 9:27 pm
 Location: Grosskrut, Austria
Re: Maximum inscribed circle in any polygon
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.
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.

 New poster
 Posts: 1
 Joined: Tue Feb 02, 2016 10:29 am
Re: Maximum inscribed circle in any polygon
Need to calculate the size of a square peg to whittle down end to a rough octagon to fit into a round hole.

 New poster
 Posts: 16
 Joined: Mon Jan 06, 2003 9:27 pm
 Location: Grosskrut, Austria
Re: Maximum inscribed circle in any polygon
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))
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))