Minkowksi Sums and Buffering

As usual, a concept which I struggled with for years is implemented cleanly and elegantly in CGAL.  I've spent more hours than I can think of fighting with buffering algorithms - the one I finally came up with is very similar in approach to the GEOS buffering algorithm.

Buffering is the process of making a polygon bigger or smaller - a trivial operation unless something ugly happens, like the polygon bumping into its new bloated self.

GEOS solves the problem the same way CGAL does: using the winding rule.  Basically, as long as your offset polygon segments always turn in the same direction as the original, you can count the number of edges you cross - each time you go from the right side of the edge to the left, you increase the winding count (for counter-clockwise polygons) - and vice versa.  If the winding count is positive, you're inside.

Why this works, I don't know - I couldn't prove it to you.  But it does seem to work, and it seems to produce robust results even with fairly smashed up offset polygons, which is important to me, because often my offsets are larger than the polygons themselves.

If I had to prove it, I'd probably try to demonstrate that certain overlapping cases of similarly wound polygons form "union" operations, thus the results are always adding or always subtracting (depending on which kind of buffer you use).

So could I have used CGAL?  Actually no -- I needed something that's not easy to find in the GIS world: a buffer that varies its width per segment.  I buffer polygons to remove the road's width from the area I use to place buildings - sometimes the road width changes mid-polygon!