Douglas-Peucker algorithm is a very popular algorithm for curve simplification. It is a method offered in many spatial packages including SQL Server’s spatial library. However a common problem is that the algorithm simplifies polygons one at a time without taking into account shared boundaries between neighboring polygons. This results in gaps and overlaps between polygons as seen below.
I wrote a small utility in C# that helps address this problem which I’d like to share here. It took me about an hour so don’t be surprised if you find bugs. At least with the maps I used it on and reasonable tolerance factors the results were great. Keep in mind that Douglas-Peucker algorithm can reduce polygons to lines or even points if the provided tolerance factor is high, so you may want to try different values to find what’s ideal.
Code looks for two types of shared edges:
Start-end points of polylines that make up the polygon overlap with those on other polygons (which is the most common case).
Lines overlap without start-end points necessarily overlapping (a rare case for most maps).
Algorithm is applied to all polygons, then simplification applied to shared edges are synced between polygons. First and the last shared point between two polygons are always kept to maintain the edge.
Code doesn’t do any special handling for multiple geometries. They need to be broken into their pieces e.g. multi-polygons into individual polygons. Same applies to interior/exterior rings.
It takes a call to the function “Reduce” and a loop over the array of points returned to get the results. Function returns the list of polygons (a list of array of points) in which the removed points are set to null. Just filter out the nulls and you’re good to go.
Above is a very simplified (orange) version of the map of California overlaid on top of the source map (in gray). Dashed lines indicate the new boundaries between polygons. You can see that the islands completely disappeared and San Francisco bay isn’t there anymore while most counties are reduced to rectangles and even triangles yet the borders are still maintained. Ideally you’d pick a tolerance value that won’t simplify the polygons this much. You can download the code here. Feedback appreciated. Maybe somebody can make this into a SQL Server UDF.