2D Minkowski Sum of Polygons Using Reduced Convolution

Evan 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, Evan Behar and Jyh-Ming Lien, Proc. IEEE Int. Conf. Intel. Rob. Syst. (IROS), Sep. 2011
Web Site / Paper (pdf) / BibTeX

Extracting the Minkowski Sum Boundary from the Reduced Convolution, Evan Behar and Jyh-Ming Lien, 20th Annual Fall Workshop on Computational Geometry, Oct. 2010
Web Site / Paper (pdf) / BibTeX

Software

Windows binary zip
Linux binary bin
Software and source code can be downloaded here

Downloads

The input polygons used in the experiment: (zip) (bzip2) (gz)

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 and
can 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