How can I check if a polygon can completely contain a circle of a certain radius?

Question

How can I check if a polygon (can also be irregular) can completely contain a circle of a certain radius? I do not want to actually draw a circle inside the polygon but just a boolean outcome whether or not it can be fit. I need this for an application that I'm developing in Java. Note that I'm not looking for the inscribed circle, but the largest circle that a polygon can contain. I suppose there can be multiple circles with the same area.

Could someone share an algorithm or code snippet (any language is fine) or guide me to any relevant resource?

Answer 1

This is likely more complicated than you would prefer, but: Compute the medial axis, which immediately yields the largest disks that fit inside the polygon: their centers are vertices (degree $\ge 3$) of the axis (see the figure below).

Chin, Francis, Jack Snoeyink, and Cao An Wang. "Finding the medial axis of a simple polygon in linear time." Discrete & Computational Geometry 21.3 (1999): 405-420.

---

         
          ^{(Image from Alexander Tsvyashchenko.)}

---

See also, Largest circle inside a non-convex polygon for an ad hoc approach (whose correctness I did not attempt to verify).