Introduction to Geo Path Reducer
Relevant source files
The following files were used as context for generating this wiki page:
Geo Path Reducer is a JavaScript module designed to simplify curves represented by a series of geographical points. It implements the Douglas-Peucker algorithm 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 tolerance.
Sources: README.md:1-5, package.json:1-12
Core Algorithm: Douglas-Peucker Implementation
The module centers around the geoPathReducer function, which recursively simplifies an array of points. It identifies the point with the maximum perpendicular distance from the line segment connecting the start and end points of a path. If this distance exceeds a user-defined epsilon threshold, the path is split at that point, and the process is applied recursively to both resulting segments.
Sources: src/index.js:3-23, README.md:31-40
Logic Flow
The following diagram illustrates the recursive decision-making process within the reducer:
The algorithm determines whether to retain intermediate points or discard them in favor of a straight line segment based on the epsilon value.
Sources: src/index.js:6-22
Mathematical Components
The simplification process relies on two primary mathematical calculations: Great-circle distance and Perpendicular distance.
Great-circle Distance
The system calculates the distance between two points on the Earth's surface using the Haversine formula. It assumes a spherical Earth with a radius (R) of 6371 kilometers.
Sources: src/distance.js:1-16
Perpendicular Distance
To determine the deviation of a point from a path segment, the module calculates the perpendicular distance from a point to the line defined by a start and end point. This is achieved by first calculating the distances between all three points and then using Heron's formula to find the area of the triangle formed, which is subsequently used to derive the altitude (perpendicular distance).
Sources: src/perpendicular-distance.js:3-11
API and Data Structures
The module exports a single default function and utilizes specific object structures for geographical coordinates.
Main Interface
| Parameter | Type | Description |
|---|---|---|
points | Array<Object> | An array of coordinate objects containing lat and lng. |
epsilon | Number | The maximum distance (in degrees) allowed between the original and simplified curve. |
Sources: README.md:31-40, src/index.js:3
Coordinate Object
The internal functions expect points to follow a specific structure:
| Property | Type | Description |
|---|---|---|
lat | Number | Latitude of the point. |
lng | Number | Longitude of the point. |
Sources: README.md:16-20, src/perpendicular-distance.js:5-7
Architecture and Dependencies
The project is structured as a modern ES module. The index.js serves as the entry point, coordinating the higher-level logic while delegating mathematical computations to specialized utility files.
The internal dependency chain ensures that complex geographical calculations are abstracted away from the core simplification logic.
Sources: src/index.js:1, src/perpendicular-distance.js:1, package.json:11
Summary
Geo Path Reducer provides a lightweight, recursive implementation of the Douglas-Peucker algorithm specifically tuned for geographical data. By utilizing Great-circle distance calculations and a recursive splitting strategy, it effectively reduces the point density of paths while maintaining their overall shape within a configurable tolerance level.
Sources: README.md:1-5, src/index.js:3-23