Exact Minkowski Sums of Polygons With Holes
This is the first “real” scientific paper which I coauthored. It’s about the design and implementation of an algorithm which computes the so called Minkowski sum of two polygons.
I like to explain the topic like this: Imagine you have two stamps of arbitrary shape. First, you stamp one of them on paper, and then, you mark a point on the second one and stamp all over the other one, so that the point is inside of the first stamp. We’re interested in the shape of the result, and in this paper, we’re investigating an algorithm which computes this exactly and fast. It’s the first exact implementation that is able to compute the Minkowski sum of polygons with holes. We also show that, if the polygons contain holes, you can always “fill up” all holes in one of them without chaning the result, and use that property to speed up the algorithm even more in some cases.
The resulting implementation has become part of the open source Computational Geometry Algorithms Library, starting from version 4.7.