Simplification is a common task in vector-based map visualization. In some situations you don’t want to display a map in its full resolution for reasons like the overall filesize and the rendering time. One major class of simplification algorithms works by removing some vertices without moving the remaining ones. While there are already some good tutorials for implementation of line simplification algorithms online¹, none of them takes into account the special requirements of map data simplifications. This gap will be closed by this post. At first I want to introduce the used data set. It’s a very basic map of all european countries. The first image shows the output of the map rendering without simplification.

While there are many simplification algorithms out there, this tutorial uses a very simple one. It’s strategy is to remove certain points that are too close to the last kept point. This is not the smartest algorithm ever, but still one of the fastest, because it don’t needs recursion and runs in O(n).

const minDistSq:Number = 100000 * 100000; // radius 100km
var countries:Array, shapes:Array, shape:Array, pt:Object, lastPt:Object, distSq:Number;

for each (shapes in countries) {
	for each (shape in shapes) {
		lastPt = shape[0];
		for each (pt in shape) {
			if (pt == shape[0]) continue; // skip first point
			distSq = (lastPt.x * lastPt.x - pt.x * pt.x) + (lastPt.y * lastPt.y - pt.y * pt.y);
			if (distSq < minDistSq) pt.deleted = true;
			else lastPt = pt;
		}
	}
}

This algorithm works perfect on single polygons, but there are some drawbacks when using it for simplication of country outlines. As you can see in the next image, the simplification introduced overlappings and gaps between the countries.

The problem here is that different polygons that share the same boundary were treated seperately. To fix this we need to refine the current map topology (CONTINENT > COUNTRY > SHAPES) in a way, that the “shared vertices” were stored only once.

The algorithm simply iterates over all points and stores them into a global point register. Every new point will then be checked for equality (same x and y coordinates) with any of the previously saved points. If the algorithm finds an equal point, the reference to the duplicate point will be replaced and the custom property inner will be set to true (which means that this point lays on more than one country border). Incidentally this will also decrease the map file size and gives us a classification of “inner” and “outer” points for free. When we run the algorithm again, we need to remeber whether the simplification already visited point, to avoid double removal. The results look much better than before, but still need some improvements:

Obviously, there is one case we forgot, which I call three-country-crossings, which means all points that lay on more than two country borders. Removing one of these points leads to triangle shaped holes inside the continent area. To avoid those holes, we got to mark all three-country-crossings as undeletable. We can find three-country-crossings by counting how often we visit a single point during the topology initialization.

Now we are nearly finished. It took me a few days to notice that there is another case, we have to consider. If you compare at the crossover between Spain and France at the Mediterranean Sea side, then you note the tiny cut into the landscape, that is introduced by the simplification.

To avoid those cuts we must identify all vertices that connects two countries and lay on the outside of a continent area. We can do so by comparing the current visited point with the last visited point, and if one lays on two countries and the other only on one, we mark the one on two countries as undeletable. The last picture shows the final output of the simplification:

I hope this tutorial was useful to you, if anyone needs more code examples on this topic, let me know via comment.

Comments

Madison Mapper (Nov 23, 2010)

Matt Bloch’s mapshaper.org is a nifty tool for doing this quickly to shapefiles:

mapshaper.org

Andrei (Nov 21, 2010)

This is awesome. Have you done any benchmarking on this? I am curious to see how long it will take to ‘simplify’ 5000 points and whether simplification can be performed on every zoom level.

Gregor (Dec 03, 2010)

@andrei: sorry for the delay. the algorithm is quite fast compared to other simplification methods, but it’s still to slow to use it in realtime. Simplification of all countries takes about 3-5 secs I think..

Rendering SVG Country Maps in Python — vis4.net (Nov 01, 2011)

[…] and Visvalingam, but I used a very fast and simple one. Actually, it’s the same algorithm that I used a few years ago, when I rendered my first world maps in […]