7
$\begingroup$

I have a 2D polygon that I want to shrink by a specific offset (A) to match a certain area ratio (R) of the original polygon. Is there a formula or algorithm for such a problem? I am interested in a simple solution for a triangle/quad but also a solution for complex polygons.

I attached an image for explanation. The original polygon is offset by A (equal-distant for each edge). A has to be chosen so that the new polygon has a specific area. In this example it should have half the area of the initial polygon.enter image description here

$\endgroup$

1 Answer 1

8
$\begingroup$

I am afraid there is no truly simple solution, unless you ignore the complexities. Just think of how you would shrink a sharp V-shape, like this:
      V-shrink
In the above, the offset was larger than the V-gap, and so the shape naturally fractured into two disconnected regions. This issue arises even with a quadrilateral.

To delve into the topic more thoroughly, see the result of Ron Wein's 2007 definitive Ph.D. thesis, described in this paper:

"Exact and approximate construction of offset polygons." (ACM link).


 WeinFig3

His work is implemented in CGAL (CGAL manual link), and now nicely described in this book:

Fogel, Efi, Dan Halperin, and Ron Wein. CGAL Arrangements and Their Applications: A Step-by-Step Guide. Vol. 7. Springer, 2012.

Finally, if you want to skim over the complexities, here is a decade-old survey that is nevertheless useful as a high-level viewpoint: survey link.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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