Small circle inside a simple polygon
I was working on a computational geometry problem and came across the following problem (which is needed as a subroutine), but couldn't find any good references or algorithms.
Given a simple (possibly concave) polygon P, the goal is to compute the center and radius of the smallest circle that is entirely contained in P (empty circle), but touches the polygon at least two places (point or edge). If two "places" are polygon points, then there is no limit. There is also no limitation if we hit point and edge. But if we hit two edges, then they don't have to be consecutive (assuming clockwise or counterclockwise order).
I am targeting an implementable algorithm that works in order n ^ 3 or better. Any pointers, links or ideas would be very helpful.
Thank! Amer
source to share
Since you're just looking for pointers or ideas, I'll be brief. The medial axis of a polygon is the set of circle centers that touch the border at two or more locations ( https://en.wikipedia.org/wiki/Topological_skeleton#Centers_of_bi-tangent_circles ). Also known as the skeleton, the medial axis is composed of a treelike graph made of lines and parabolas. If you check the circles at the vertices of this graph (ignoring the vertices of the graph that coincide with the vertices of the polygon), you can find both the largest and smallest circles. You will need to fine tune to meet your "no consistent edges" requirements.
source to share