The Douglas-Peucker Algorithm
Relevant source files
The following files were used as context for generating this wiki page:
The Douglas-Peucker algorithm is a method implemented within the geo-path-reducer module to simplify curves composed of a series of points. Its primary purpose is to reduce the complexity of spatial data, such as map coordinates, by removing points that do not significantly contribute to the shape of the path based on a specified threshold.
In this project, the algorithm is exposed via the geoPathReducer function, which processes geographic coordinates consisting of latitude and longitude. The reduction process is controlled by an epsilon parameter, representing the maximum allowable distance between the original curve and the simplified version.
Sources: README.md:3-8, src/index.js:3
Core Logic and Recursion
The algorithm operates recursively by identifying the point with the maximum perpendicular distance from a line segment connecting the first and last points of a path.
Process Flow
- Find Maximum Distance: The algorithm iterates through all intermediate points to find the point farthest from the line segment formed by the start and end points.
- Threshold Comparison: If this maximum distance (
dmax) is greater than the user-definedepsilon, the point is kept, and the algorithm recursively splits the path into two parts: from the start to the maximum distance point, and from that point to the end. - Path Simplification: If the maximum distance is less than or equal to
epsilon, all intermediate points are discarded, and only the start and end points are retained for that segment.
The following diagram illustrates the decision logic within the main reducer function:
The flowchart demonstrates the recursive splitting of the coordinate array based on the epsilon threshold.
Sources: src/index.js:5-23
Mathematical Components
The algorithm relies on two specific mathematical calculations to determine point relevance: Great-Circle distance and Heron's formula for perpendicular distance.
Distance Calculation
The module calculates the great-circle distance between two points on Earth using the Haversine formula, which accounts for the Earth's radius (defined as 6371 km).
| Variable | Description | Formula/Value |
|---|---|---|
R | Earth's radius | 6371 km |
dLat | Difference in latitude | (lat2 - lat1) * PI / 180 |
dLon | Difference in longitude | (lon2 - lon1) * PI / 180 |
a | Square of half the chord length | sinĀ²(dLat/2) + cos(lat1)*cos(lat2)*sinĀ²(dLon/2) |
Sources: src/distance.js:3-15
Perpendicular Distance
The perpendicular distance from a point to the line segment (start, end) is calculated by treating the three points as a triangle. The algorithm finds the area of the triangle using Heron's formula and then derives the height (distance).
The diagram shows how three distinct point-to-point distances are converted into a single perpendicular distance value.
Sources: src/perpendicular-distance.js:3-10
API Reference
The project provides a single main entry point for using the algorithm.
geoPathReducer(points, epsilon)
| Parameter | Type | Description |
|---|---|---|
points | Array<Object> | An array of objects, each containing lat and lng properties. |
epsilon | Number | The maximum distance (in degrees) for the simplified curve. |
Returns: A new Array of simplified point objects.
import geoPathReducer from 'geo-path-reducer';
const simplified = geoPathReducer([
{ lat: 37.7749, lng: -122.4194 },
{ lat: 37.7755, lng: -122.4182 },
{ lat: 37.7769, lng: -122.4159 }
], 0.0001);
Sources: README.md:20-33, src/index.js:3
Module Structure
The project is structured as a modern ES module with clear separation between the recursive logic and the mathematical utilities.
The dependency hierarchy shows that the main reducer relies on perpendicular calculations, which in turn rely on basic point-to-point distance calculations.
Sources: src/index.js:1, src/perpendicular-distance.js:1, package.json:11
Conclusion
The implementation of the Douglas-Peucker algorithm in geo-path-reducer provides an efficient way to simplify geographic paths by recursively evaluating the spatial significance of coordinates. By leveraging the Haversine formula and Heron's formula, the module ensures that the simplification remains accurate relative to the Earth's curvature while allowing users to control the level of detail via the epsilon parameter.