7
$\begingroup$

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?

$\endgroup$
8
$\begingroup$

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.


          medialax
          (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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.