Generalization algorithms

Douglas–Peucker

The Douglas–Peucker is a classic line simplification method. It removes points while keeping the overall shape by measuring how far vertices deviate from a straight baseline and preserving only the vertices that exceed a chosen tolerance.

The illustration shows the key idea: take a polyline segment with endpoints A and B, and consider all intermediate points. For each intermediate vertex P, compute the perpendicular distance to the baseline AB.

• Baseline AB – the straight reference line connecting the current segment’s endpoints.
• d(P, AB) – the perpendicular distance from a vertex P to the baseline, measuring local deviation.
• Farthest point – the vertex with the maximum distance to AB; this point represents the most important bend within the segment.

The tolerance ε is a distance threshold (same unit as the coordinates). A vertex is considered significant if its deviation from the baseline is greater than ε. Formally, the algorithm finds: max d(P, AB) over all interior vertices P.

If the maximum deviation is ≤ ε, the entire segment is considered sufficiently straight and all intermediate points can be removed, keeping only A and B. If the maximum deviation is > ε, the farthest point is kept and the line is split into two sub-segments (A–P and P–B).

As suggested by the figure, the algorithm then repeats the same test recursively on each sub-segment. Increasing ε produces stronger simplification (fewer retained vertices), while decreasing ε preserves more detail.

Douglas–Peucker is simple, fast, and effective for strong point reduction, making it well suited for simplifying single polylines while preserving their overall shape. However, because it relies only on distance to a baseline, it may remove meaningful bends and does not inherently respect topology. As a result, it is best used for roads, rivers, or trajectories where speed and geometric reduction are more important than structural detail.

Wang–Müller

The Wang–Müller algorithm is a bend-based line simplification method. Unlike distance-based approaches, it focuses on the structural bends of a line and removes vertices that contribute little to the overall directional change.

As illustrated above, the line is analyzed locally by examining each interior vertex together with its immediate predecessor and successor. These three points define a bend, representing a local change in direction.

• Bend – a polyline segment formed by three consecutive vertices, capturing a local directional change.
• Bend size – a measure derived from the bend geometry, typically related to the turning angle and the spatial extent of the bend.
• Dominant bends – large or sharp directional changes that characterize the overall shape of the line.

The tolerance ε controls how aggressively minor bends are removed. In the original bend-based literature and GIS implementations, “bend size” can be defined using bend geometry (e.g., the bend’s span and shape). In this interactive demo, ε is mapped to a turn-angle threshold: higher ε means a higher minimum turning angle is required for a vertex to be kept. As ε increases, small directional wiggles disappear first, while dominant turns remain.

The process is iterative, as shown in the figure: bends are identified along the line; the least significant bend is removed; the line is reconnected; and the analysis is repeated. This continues until all remaining bends meet the ε criterion.

By prioritizing dominant directional changes instead of local distances, the Wang–Müller algorithm preserves the overall shape and orientation of the line, making it especially suitable for cartographic generalization where structural readability is more important than geometric precision.

The main strength of the Wang–Müller algorithm is its focus on structural bends and directional change, which often produces results that look more cartographically natural. By prioritizing dominant turns over small fluctuations, it preserves the perceived shape of a line. Its limitation is that results can be sensitive to local geometry and parameter choice, especially in noisy data. It is particularly suitable for rivers, coastlines, and contour lines, where shape readability matters more than exact geometry.

Visvalingam–Whyatt

The Visvalingam–Whyatt (VW) algorithm simplifies a polyline by repeatedly removing the least important vertex, where importance is measured by the area of a local triangle. Compared with “distance-to-baseline” methods, VW is more “shape-aware”: it tends to keep visually meaningful bends and removes tiny fluctuations first.

The figure illustrates the key idea: for each interior vertex P_i, form a triangle using its immediate neighbors (P_i-1, P_i, P_i+1). The shaded region is the effective area of that triangle—intuitively, how much that vertex “sticks out” from the straight connection between its neighbors. Small, skinny triangles mean the vertex contributes little to the overall shape, so it is removed first.

The triangle area for vertex P_i is: A_i = 1/2 · | (x_i-1(y_i-y_i+1) + x_i(y_i+1-y_i-1) + x_i+1(y_i-1-y_i)) |

In hands-on implementation, the shared slider defines the threshold as ε² . That means: vertices with A_i < ε² are considered insignificant and are removed. Increasing ε raises the minimum area required to keep a vertex, producing stronger simplification; ε = 0 yields the least simplification (in practice, perfectly collinear points may still be removable because they contribute zero area).

The process repeats: after removing the smallest-area vertex, its neighbors get new triangles (new shaded areas), and the algorithm continues until no triangle area falls below the ε² threshold (or until only the protected minimum number of points remains, if you enforce a stability guard).

Visvalingam–Whyatt excels at removing small, visually insignificant fluctuations by measuring the effective area of local triangles, often producing smoother and cleaner-looking lines. However, its purely local area measure can sometimes misjudge importance in elongated or unevenly sampled geometries. It is well suited for natural boundaries such as coastlines and riverbanks, especially when visual smoothness is a primary goal.

Zhou–Jones

The Zhou–Jones algorithm is a refinement of the Visvalingam–Whyatt line simplification method. Instead of relying on triangle area alone, it evaluates the visual importance of each vertex using a weighted effective area. This allows the algorithm to preserve significant bends while removing redundant detail.

For each interior vertex, a triangle is formed using its immediate predecessor and successor. Several geometric properties of this triangle are evaluated:

• H (Height) – the perpendicular distance from the vertex to the baseline connecting its neighbors, representing local deviation from a straight line.
• ML (Baseline length) – the distance between the adjacent vertices, describing the spatial span of the bend.
• W (Edge span) – the longest edge of the triangle, reflecting its overall scale.
• Turning angle – indicating local curvature at the vertex.

The triangle area is multiplied by a weight derived from curvature, flatness, and skewness. Sharp, well-proportioned bends receive higher weights, while small or nearly collinear triangles are penalized.

The tolerance ε defines a minimum weighted-area threshold. Vertices whose weighted area falls below ε² are considered insignificant and are removed. Increasing ε produces stronger simplification, while ε = 0 yields the least simplification (zero-weight / zero-area cases may still be removable).

As illustrated above, the algorithm proceeds iteratively: a local triangle is evaluated, the vertex with the lowest weighted importance is removed, and the line is reconnected. This process repeats until the desired level of simplification is reached.

Zhou–Jones extends the Visvalingam–Whyatt approach by incorporating additional geometric weights, allowing it to better preserve visually important bends and structural features. This often leads to higher-quality cartographic results, but at the cost of greater complexity and reduced parameter intuitiveness. It is most appropriate for high-quality cartographic generalization, where maintaining visual structure is more important than algorithmic simplicity.