Code Examples
Relevant source files
The following files were used as context for generating this wiki page:
The geo-path-reducer library provides a technical implementation of the Douglas-Peucker algorithm, designed to simplify geographic paths by reducing the number of points in a series while maintaining the overall shape. This module is particularly useful for optimizing spatial data, such as map coordinates, to reduce payload sizes and improve rendering performance.
The system is structured as a recursive reduction process that evaluates the perpendicular distance of points from a line segment. If the maximum distance of a point exceeds a user-defined threshold (epsilon), the path is split and processed recursively.
Sources: README.md:3-7, src/index.js:1-25
Core Algorithm Implementation
The primary entry point of the library is the geoPathReducer function. It takes an array of geographic points and a tolerance value to determine which points are significant enough to be retained.
Algorithm Logic and Data Flow
The process begins by calculating the perpendicular distance for every intermediate point between the start and end of the current path segment. The point with the greatest distance (dmax) is identified. If dmax is larger than the provided epsilon, the algorithm splits the array at that index and calls itself recursively on both resulting segments.
The following diagram illustrates the logical flow of the path reduction process:
The algorithm uses a recursive approach to divide and conquer the path segments until all points within a segment fall within the epsilon tolerance.
Sources: src/index.js:4-24
Geometric Calculations
The library relies on precise geographic distance calculations to determine the relevance of specific points. This is handled by two internal utility modules.
Perpendicular Distance
The perpendicular-distance.js module calculates how far a specific point sits from a line segment defined by two other points (start and end). It uses the semi-perimeter and Heron's formula to find the area of the triangle formed by the three points, then derives the height (distance) from that area.
Sources: src/perpendicular-distance.js:3-11
Haversine Distance
The distance.js module calculates the great-circle distance between two points on the Earth's surface using the Haversine formula. It uses a constant for the Earth's radius (6371 km).
| Variable | Description | Source |
|---|---|---|
R | Earth's radius in kilometers (6371) | src/distance.js:3 |
dLat | Delta latitude in radians | src/distance.js:4 |
dLon | Delta longitude in radians | src/distance.js:5 |
a | Square of half the chord length between points | src/distance.js:7-12 |
c | Angular distance in radians | src/distance.js:13 |
Sources: src/distance.js:1-15
API Usage and Configuration
The library is consumed as an ES module. It expects a specific data structure for geographic points and a numerical epsilon value.
Function Signature
geoPathReducer(points, epsilon)
| Parameter | Type | Description |
|---|---|---|
points | Array<Object> | An array of objects containing lat and lng properties. |
epsilon | Number | The maximum distance (in degrees) allowed between the original and simplified curve. |
Sources: README.md:28-33
Integration Example
Users can import the default export and pass a coordinate array. The following example demonstrates a typical implementation:
import geoPathReducer from 'geo-path-reducer';
const points = [
{ lat: 37.7749, lng: -122.4194 },
{ lat: 37.7755, lng: -122.4182 },
{ lat: 37.7758, lng: -122.4177 }
];
const epsilon = 0.0001;
const simplifiedPoints = geoPathReducer(points, epsilon);
Sources: README.md:14-25, package.json:11
Module Structure
The project is organized into a main entry file and two utility files for mathematical operations.
The geo-path-reducer provides a lightweight, dependency-free (as per package.json) solution for spatial data simplification using standard geographic distance formulas and the Douglas-Peucker recursion strategy.
Sources: package.json:1-13