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

Web Site / Paper (pdf) / BibTeX

*Proc. IEEE Int. Conf. Intel. Rob. Syst. (IROS)*, Sep. 2011Web Site / Paper (pdf) / BibTeX

Extracting the Minkowski Sum Boundary from the Reduced Convolution, Evan Behar and Jyh-Ming Lien,

Web Site / Paper (pdf) / BibTeX

*20th Annual Fall Workshop on Computational Geometry*, Oct. 2010Web 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 modelCompute 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 polygonsThe 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