Maximum inscribed circle in any polygon

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
littlekid
New poster
Posts: 1
Joined: Sun Dec 28, 2008 8:10 am

Maximum inscribed circle in any polygon

Post by littlekid » Sun Dec 28, 2008 8:14 am

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. :roll: )

ericschmidt
New poster
Posts: 16
Joined: Mon Jan 06, 2003 9:27 pm
Location: Grosskrut, Austria

Re: Maximum inscribed circle in any polygon

Post by ericschmidt » Sun May 17, 2015 12:32 am

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
New poster
Posts: 1
Joined: Tue Feb 02, 2016 10:29 am

Re: Maximum inscribed circle in any polygon

Post by VickieMikkelson » Tue Feb 02, 2016 11:01 am

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

ericschmidt
New poster
Posts: 16
Joined: Mon Jan 06, 2003 9:27 pm
Location: Grosskrut, Austria

Re: Maximum inscribed circle in any polygon

Post by ericschmidt » Tue Feb 02, 2016 9:15 pm

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))

Post Reply

Return to “Algorithms”