In cartography, line simplification algorithms are often used to render high-resolution geographic features at an appropriate output resolution. They can be applied to both polylines and polygons.
Many geometry algorithms require polygons to be simple, i.e. without self-intersections. The following map of the Norwegian coastline demonstrates occasional intersections generated by Visvalingam’s algorithm, highlighted in red.
px2.
Data: N2000 Kartdata (scale: 1:2,000,000).
Intersections can be avoided using a simple modification.
Visvalingam’s algorithm gives each point in a line an importance weighting, so that least important points are removed first. The importance is commonly derived from the area of the triangle formed by each point and its immediate neighbours.
In the following example, the triangle areas have been replaced with ranks for simplicity, starting with 0 for the smallest area.
On the left, the unmodified Visvalingam algorithm results in an intersection when point 0 is removed. On the right, the modified algorithm has promoted this point to the next-largest effective area, hence two points have rank 0, and the intersection is avoided when they are both removed at once.
We begin by assuming that there are no intersections between any segments. Each time we remove a point from the heap, we ensure that the assumption still holds. It’s somewhat easier to explain via the pseudocode below, with modifications to the standard Visvalingam algorithm highlighted:
// points is a doubly linked list
simplify(points)
heap = minHeap(compareArea)
maxArea = 0
intersecting = []
for (point in points)
point.area = area(point)
heap.add(point)
while (point = heap.pop())
if (point.area < maxArea) point.area = maxArea
else maxArea = point.area
// Check that the new segment doesn’t intersect with
// any existing segments, except for the point’s
// immediate neighbours.
if (intersect(heap, point.previous, point.next))
intersecting.push(point)
continue
// Reattempt to process points that previously would
// have caused intersections when removed.
while (i = intersecting.pop()) heap.push(i)
remove(point) // remove from doubly linked list
update(point.previous, heap)
update(point.next, heap)
update(point, heap)
point.area = area(point)
heap.update(point)
Checking for intersections between the new segment and virtually all existing segments quickly becomes impractical for non-trivial numbers of segments.
The number of intersection tests can be reduced drastically using a spatial index, e.g. an R*-tree is used in the current implementation (RBush) with excellent results.
The current implementation is 2D-only, but I’d like to add support for spherical arc intersections. This could potentially end up as part of TopoJSON so that problematic self-intersecting polygons are avoided when drawn with D3.
22 July 2014