Source: Natural Earth, 1:10m resolution.
An interesting challenge in cartography is getting data of the appropriate resolution. As Lewis Fry Richardson observed, the more precisely you measure the length of a coastline, the longer it appears; geographic shapes have infinite complexity. Digital displays, in contrast, are limited by pixels. Choosing too high a resolution increases download time and slows rendering, while too low a resolution elides important detail. This challenge is exacerbated by zoomable maps that desire multi-resolution geometry!
To simplify geometry to suit the displayed resolution, various line simplification algorithms exist. While Douglas–Peucker is the most well-known, Visvalingam’s algorithm may be more effective and has a remarkably intuitive explanation: it progressively removes points with the least-perceptible change. Amazingly, simplification often allows the elimination of 95% or more points while retaining sufficient detail for visualization. For example, the GeoJSON file used to draw the continental United States above can be reduced from 531KB to 27KB with only minor visual changes.
To determine which point removal incurs the smallest visible change, Visvalingam’s algorithm computes triangles formed by successive triplets of points along each line; the point with the smallest associated triangle is removed. After each removal, the area of neighboring triangles is recomputed and the process is repeated.
For example, consider this line of six points:
Ignoring the endpoints, the effective area of each point is determined by its associated triangle:
The purple triangle is the smallest, so the fifth point is removed first. This removal requires recomputing the area of the adjacent red triangle:
The green triangle is now the smallest, so the third point is removed, and the adjacent orange and red triangles are recomputed. This process continues until only the endpoints remain:
There is no guarantee that removing a point increases the area of the adjacent triangles; thus, the algorithm considers the effective area as the larger of the associated triangle and the previously-removed triangle.
One of the best features of Visvalingam’s algorithm is that the effective area can be subsequently stored in the geometry. For example, a point can have a z-coordinate that indicates its effective area, allowing efficient filtering for dynamic simplification even when the algorithm is run on the server. An example of this technique is shown at the top of the page, though more commonly simplification is done based on zoom level.
Special thanks to Matt Bloch for teaching me about dynamic simplification and for MapShaper.