2D Minkowski Sum of Polygons Using Reduced Convolution
Emily Behar and Jyh-Ming Lien
Overview
We propose a new method for computing the 2-d Minkowski sum of non-convex polygons. Our method is convolution based. The main idea is to use the reduced convolution and filter the boundary by using the topological properties of the Minkowski sum. The main benefit of this proposed approach is from the fact that, in most cases, the complexity of the complete convolution is much higher than the complexity of the final Minkowski sum boundary. Therefore, the traditional approach often wastes a large portion of the computation on computing the arrangement induced by the complete convolution that is later on thrown away. Our method is designed to specifically avoid this waste of computation.Publications
Fast and Robust 2D Minkowski Sum Using Reduced Convolution, Emily Behar and Jyh-Ming Lien, Proc. IEEE Int. Conf. Intel. Rob. Syst. (IROS), Sep. 2011
Web Site / Paper (pdf) / BibTeX
Web Site / Paper (pdf) / BibTeX
Extracting the Minkowski Sum Boundary from the Reduced Convolution, Emily Behar and Jyh-Ming Lien, 20th Annual Fall Workshop on Computational Geometry, Oct. 2010
Web Site / Paper (pdf) / BibTeX
Web Site / Paper (pdf) / BibTeX
Software
- Windows binary zip
- Linux binary bin
- Software and source code can be downloaded here
Downloads
Overview of Our Method
![]() 1. Input polygon P (red) | ![]() 2. Input polygon Q (blue, front) | ![]() 3. The reduced convolution of the input. |
![]() 4. After orientable loop filtering. | ![]() 5. After loop nesting condition filtering | ![]() 6. The full convolution of the input polygon with itself. (For comparison only) |
Examples
Our method can efficiently generate the following results.Input neuron model Compute Minkowski sum with a circle ![]() | The reduced convolution![]() | Output![]() |
Input grate models![]() | The reduced convolution![]() | Output![]() |
More Examples
Our method can handle (certain types of) non-simple polygons andcan be used to compute erosion and other mathematical morphology operators.
non-simple polygons The Minkowski sum of a circle and a non-simple polygon ![]() | The Minkowski sum of two non-simple polygons![]() |
Input mammoth model![]() | Eroded mammoth model![]() |
Related Work/Links
- Other Minkowski sum work from MASC
- Exact Minkowski sums of planar polygons, by Ron Wein
- CGAL 2D Minkowski Sum of Polygons
- A nice overview on 2D Minkowski sum