Recursive Implementation
Relevant source files
The following files were used as context for generating this wiki page:
The recursive implementation in the geo-path-reducer project utilizes the Douglas-Peucker algorithm to simplify complex geospatial paths. The core purpose of this system is to reduce the number of points in a curve while maintaining a shape that remains within a specified tolerance, known as epsilon. This process is essential for optimizing spatial data performance and reducing storage requirements for map-based applications.
Sources: README.md:3-7, src/index.js:3-5
Algorithm Logic and Flow
The implementation follows a divide-and-conquer strategy. It identifies the point with the maximum perpendicular distance from the line segment formed by the start and end points of the current path. If this maximum distance exceeds the user-defined epsilon threshold, the path is split at that point, and the algorithm recursively processes both resulting segments.
Main Processing Loop
The main entry point is the geoPathReducer function. It iterates through the internal points of a segment to determine which point deviates most from a straight line connecting the extremities.
The diagram above illustrates the recursive branching logic used to simplify the path based on the distance threshold.
Sources: src/index.js:3-23
Geometric Calculations
The recursion relies on precise distance calculations to determine whether a point should be kept or discarded. This involves two primary mathematical modules:
- Great-Circle Distance: Calculates the distance between two coordinates on Earth's surface using the Haversine formula, assuming a radius of 6371 km.
- Perpendicular Distance: Calculates the shortest distance from a point to a line segment using Heron's formula to find the area of the triangle formed by the three points.
| Module | Purpose | Key Variables |
|---|---|---|
distance.js | Great-circle distance between two points | lat, lon, R (6371) |
perpendicular-distance.js | Perpendicular distance from point to line | d1, d2, d3, s, area |
Sources: src/distance.js:1-14, src/perpendicular-distance.js:3-12
Component Architecture
The system is structured as a modular JavaScript library using ES modules.
Function Definitions
geoPathReducer(points, epsilon)
This is the primary export. It takes an array of point objects and a numerical tolerance. Note that the internal recursive calls reference douglasPeucker, which corresponds to the same logic as the exported function.
- Logic:
- Iterates from index
1ton-2. - Uses
perpendicularDistanceto evaluate each point. - Returns a concatenated array of simplified results if a split occurs.
- Returns just the first and last points if no point exceeds
epsilon.
- Iterates from index
Sources: src/index.js:3-23
perpendicularDistance(point, start, end)
Calculates the height of the triangle where the base is the line segment between start and end.
const s = (d1 + d2 + d3) / 2;
const area = Math.sqrt(s * (s - d1) * (s - d2) * (s - d3));
return (area * 2) / d3;
Sources: src/perpendicular-distance.js:8-11
Data Structures
The implementation expects points to be objects with specific properties as defined in the API and used in the distance modules.
| Property | Type | Description |
|---|---|---|
lat | Number | Latitude of the point in degrees |
lng | Number | Longitude of the point in degrees |
epsilon | Number | Maximum distance in degrees (as per README) or kilometers (implied by distance logic) |
Sources: README.md:21-25, src/distance.js:4-6, src/perpendicular-distance.js:5-7
Implementation Sequence
The interaction between the modules during a single reduction step is shown below:
Conclusion
The recursive implementation provides a robust way to simplify geographical paths by identifying and preserving critical vertices while removing redundant points. By utilizing the Douglas-Peucker algorithm and great-circle distance calculations, the library ensures that the simplified path remains a mathematically accurate representation of the original curve within the specified epsilon tolerance.