1
$\begingroup$

Given a 2D simple polygon with $n$ vertices, how would I find the largest circle (whose centre and radius are unknown) that fits inside (circle can be tangent to edges/coincident with vertices) the polygon? Is there any way to solve this analytically as opposed to algorithmically?

$\endgroup$
4
  • 1
    $\begingroup$ If by polygon you mean a regular polygon, then it will be it's in-circle. $\endgroup$ – John Paul Dec 5 '19 at 17:48
  • $\begingroup$ @John Does regular imply that the polygon is 'convex'? If so, no...I deal with arbitrary polygons too. $\endgroup$ – niran90 Dec 5 '19 at 17:50
  • $\begingroup$ @John Oh right, I just read the definition of regular. No, the polygon could have arbitrary lengths. $\endgroup$ – niran90 Dec 5 '19 at 17:51
  • 2
    $\begingroup$ stackoverflow.com/questions/4279478/… might be worth a look. $\endgroup$ – Barry Cipra Dec 5 '19 at 18:37
2
$\begingroup$

I guess you could mix analytic and algorithmic. The maximiser circle will necessarily be constrained by three conditions which could be either "containing a vertex" or "being tangent to one of the edges". So you could iterate over each of the $\binom {2n} 3$ possible sets of three constraints, translate those into systems of equations, and solve them, throw out solutions that are not actually inscribed, and then maximise radius...

$\endgroup$
2
  • 1
    $\begingroup$ It might also help to note that a vertex can be contained only when its internal angle exceeds $180^\circ$. $\endgroup$ – URL Dec 5 '19 at 18:36
  • $\begingroup$ @URL Good point! $\endgroup$ – niran90 Dec 5 '19 at 18:55

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.