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

• 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 