Point Distance Calculation

Relevant source files

The following files were used as context for generating this wiki page:

• src/distance.js
• src/perpendicular-distance.js
• src/index.js
• README.md
• package.json

The Point Distance Calculation module provides the mathematical foundation for the Geo Path Reducer project. Its primary purpose is to calculate spatial relationships between geographic points, specifically great-circle distances and perpendicular distances from points to line segments. These calculations are critical for the implementation of the Douglas-Peucker algorithm, which simplifies complex curves by identifying and removing redundant points based on a distance threshold.

Within the project, these calculations allow the system to determine which points in a path deviate furthest from a straight-line approximation. By calculating the perpendicular distance of intermediate points relative to a line segment formed by start and end points, the reducer can decide whether to retain a point or recurse further into the path segments.

Great-Circle Distance Implementation

The core distance metric used is the great-circle distance, which represents the shortest distance between two points on the surface of a sphere. This is implemented using the Haversine formula to account for the Earth's curvature.

Haversine Logic

The calculation uses the Earth's radius (6371 km) and converts latitude and longitude coordinates from degrees to radians. It computes the square of half the chord length between the points (a) and the angular distance in radians (c) before arriving at the final distance in kilometers.

The diagram above illustrates the mathematical flow within the distance utility to derive kilometers from coordinate pairs.
Sources: src/distance.js:1-15

Perpendicular Distance Logic

The system determines the deviation of a point from a path segment using a perpendicular distance calculation. This is achieved by treating the three points (the target point, the segment start, and the segment end) as a triangle and deriving the height of that triangle relative to the segment base.

Heron's Formula Integration

The module calculates the lengths of all three sides of the triangle using the great-circle distance function. It then applies Heron's formula to find the area of the triangle:

1. Calculate semi-perimeter s = (d1 + d2 + d3) / 2.
2. Calculate area Area = sqrt(s * (s-d1) * (s-d2) * (s-d3)).
3. Derive height (perpendicular distance) using (Area * 2) / base_length.

Variable	Description	Source
d1	Distance from point to start	src/perpendicular-distance.js:5
d2	Distance from point to end	src/perpendicular-distance.js:6
d3	Distance between start and end (base)	src/perpendicular-distance.js:7
area	Calculated area of the triangle	src/perpendicular-distance.js:9

This sequence shows how the perpendicular distance utility coordinates multiple calls to the basic distance function to solve for the geometric height.
Sources: src/perpendicular-distance.js:3-11

Application in Path Reduction

The distance calculations are consumed by the main reduction algorithm to identify the point with the maximum deviation (dmax) in a set of points.

Reduction Flow

The algorithm iterates through intermediate points and uses perpendicularDistance to find the most significant outlier. If the maximum distance exceeds the user-defined epsilon (threshold), the path is split at that point, and the process recurses.

API Definition

The following parameters are used in the reduction process which relies on these distance calculations:

Parameter	Type	Description
points	Array	Array of objects with lat and lng properties.
epsilon	Number	Maximum distance (in degrees/units) between original and simplified curve.

Sources: README.md:32-37, src/index.js:3

Summary

Point distance calculation in this project is a multi-layered process involving spherical geometry (Haversine formula) and triangle-based altitude derivation (Heron's formula). These utilities provide the spatial intelligence required to simplify geographic paths while maintaining a specific accuracy threshold defined by the epsilon parameter.