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

Downloads

Overview of Our Method
image
1. Input polygon P (red)
image
2. Input polygon Q (blue, front)
text
3. The reduced convolution of the input.
text
4. After orientable loop filtering.
text
5. After loop nesting condition filtering
text
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
image
The reduced convolution
image
Output
image
Input grate models
image
The reduced convolution
image
Output
image

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
image
The Minkowski sum of two non-simple polygons
image
Input mammoth model
image
Eroded mammoth model
image

Related Work/Links
Computer Science @ George Mason University