Search
Close this search box.

Exact and Efficient Construction of Planar Minkowski Sums using the Convolution Method

References

Two cycles in
Two cycles in
two cycles out
Two cycles out

We describe an efficient and robust implementation for the construction of Minkowski sums of polygons in the plane using the convolution of the polygon boundaries. This method allows for faster computation of the sum of non-convex polygons in comparison with the widely-used methods for Minkowski-sum computation that decompose the input polygons into convex sub-polygons and compute the union of the pairwise sums of these convex sub-polygon. Our implementation is part of the 2D Minkowski-sum package of CGAL.

The first example demonstrates computation of the convolution of two non-convex octagons (two cycles in). The convolution consists of two cycles (two cycles out). The Minkowski sum of the polygons is shaded. One cycle (solid arrows) comprises 32 line segments, while the other consists of 48 line segments,  non of which lies on the boundary of the Minkowski sum. The latter cycle is drawn using dashed arrows.

The example below depicts a house plan and a star-shaped furniture (tight in). The Minkowski sum of the two polygons (tight out) consists of low-dimensional features. For clarity, two copies of the  star are drawn using a dashed line with their center positioned on these features. The left copy is located on an antenna on the Minkowski-sum boundary, such that the star can move along this antenna while touching the walls of  the house without penetrating into the walls. The right copy is located such that the star center is on an isolated vertex, which designates a location where the star does not penetrate into the walls, but it is immobilized. Our algorithm, which employs exact computation, is capable of detecting such low-dimensional features that are crucial for the success of some motion-planning algorithms.

tight in
Tight in

tight out
Tight out

Links

  • Ron Wein
    Exact and efficient construction of planar Minkowski sums using the convolution method
    In Proceedings of the 14th European Symposium on Algorithms (ESA), Volume 4186 of LNCS, pages 829-840, 2006 [link][bibtex]

Contacts

Ron Wein
Dan Halperin
@inproceedings{w-eecpm-06,
  author       = {Ron Wein},
  editor       = {Yossi Azar and Thomas Erlebach},
  title        = {Exact and efficient construction of planar Minkowski sums using the convolution method},
  booktitle    = {Proceedings of the 14th Annual European Symposium on Algorithms (ESA)},
  series       = {Lecture Notes in Computer Science ({LNCS})},
  volume       = {4168},
  year         = {2006},
  publisher    = {Springer},
  pages        = {829--840},
  doi          = {10.1007/11841036_73}
}

Yair Oz - Webcreator

Contact

Skip to content