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.
|
|
|
