GIS, Mapping, Visualization

Simplifying multiple neighboring polygons

Complexity of polygons are often an issue when using online mapping applications that rely on JavaScript. Lengthy initial loading times, browser unresponsiveness, even crashes can occur when dealing with polygons that consist of tens of thousands of points. Real maps are generally complex but for web mapping reasons accuracy is not always a necessity. For example you probably wouldn’t worry about topographic fidelity if your goal is to show census data using a choropleth map, neither would your end users. Not to mention, at times high fidelity does not serve any purpose as zoom level may not allow a users to see the details in the first place. When user zooms in, the shrinking viewing area would allow adding more detail as you won’t have to worry about points outside the viewing area.

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.

Multiple polygon simplication resulting in gaps

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.

Topology aware polygon simplification - Click to see before and after side-by-side

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. Smile


10 thoughts on “Simplifying multiple neighboring polygons

  1. googlemapsftw says:

    Works great! I modified it a little bit (added a WKT parser) and associated with map zoom level. Does the trick for me.

  2. Leigh Webber says:

    What’s the best way to pull the geo data out of SQL Server to populate the Point and List objects? IOW, how do I set up the arguments I need to call the methods in your Geometry class?

    • Hi Jean,
      Geometry.Reduce is the method you need to use. It takes a list of point arrays and other parameters such as tolerance. Each point array is one of your polygons. Point is a struct also defined in the file which you need to plug in your x-y coordinates (or lat long). The higher the tolerance, the simpler the resulting polygons will be. The output will be in the same structure as the input but points removed as part of simplification will appear as NULLs in the Point array.

      I hope this helps.

  3. Jean says:

    Thank you very much for your answer and sorry for the delay but I didn’t check the website for an answer till today !!!
    I’ve tried to use your code but I get a stackoverflow during execution.

    Can I send you what I’ve done ? It’s pretty simple …

  4. Mary says:

    I’ve been thinking of implementing a cartogram algorithm in Tableau/R using similar principals. Could be cool: send vector of data to R to resize by, R computes new boundaries and saves them, in csv then import using custom geocoding. Would be useful, but probably slow.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s