Perpendicular Distance Logic

Relevant source files

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

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

The Perpendicular Distance Logic is a fundamental component of the geo-path-reducer library, primarily used to support the implementation of the Douglas-Peucker algorithm. Its purpose is to calculate the distance between a specific geographic point and a line segment defined by two other points (a start and an end point). This measurement is critical for determining which points in a path are redundant and can be removed without exceeding a specified error tolerance (epsilon).

In the context of the overall project, this logic allows for the simplification of complex curves represented by arrays of latitude and longitude coordinates. By identifying points that reside far from the direct path between segment endpoints, the system can recursively refine a path to reduce data complexity while maintaining its general shape.

Sources: src/index.js:4-13, src/perpendicular-distance.js:3-11, README.md:1-5

Core Mathematical Implementation

The calculation of the perpendicular distance relies on Heron's formula to find the area of a triangle formed by three points: the target point, the segment start, and the segment end. Once the area is known, the perpendicular distance (the height of the triangle) is derived from the standard area formula ($Area = \frac{1}{2} \times base \times height$).

Distance Calculation Steps

1. Segment Leg Lengths: The system first calculates the "great-circle" distance between the three points to find the lengths of all sides of the triangle.
2. Semi-perimeter: It calculates the semi-perimeter $s$ of the triangle.
3. Area Calculation: It applies Heron's formula: $\sqrt{s(s-d1)(s-d2)(s-d3)}$.
4. Height Derivation: It returns $(Area \times 2) / d3$, where $d3$ is the length of the base (the line segment).

Sources: src/perpendicular-distance.js:5-10

The diagram shows the sequence of mathematical operations used to transform three geographical points into a single perpendicular distance value.
Sources: src/perpendicular-distance.js:5-10

Great-Circle Distance Component

The logic depends on a separate distance module that computes the distance between two points on the Earth's surface using the Haversine formula. This ensures that distances are calculated in kilometers, accounting for the Earth's curvature.

Haversine Constants and Variables

Variable	Description	Value / Source
R	Earth's radius in kilometers	6371
dLat	Difference in latitude	Radians conversion
dLon	Difference in longitude	Radians conversion
Math.PI / 180	Conversion factor	Degrees to Radians

Sources: src/distance.js:3-13

Integration with Path Reduction

The perpendicular distance logic is invoked within a loop in the main reduction function. It identifies the "point of maximum distance" ($dmax$) relative to a line segment connecting the first and last points of a coordinate array.

Data Flow for Simplification

1. The geoPathReducer receives an array of points.
2. It iterates through all intermediate points, calculating the perpendicularDistance for each.
3. If the largest found distance exceeds the user-defined epsilon, the path is split at that index.

Sources: src/index.js:4-15, README.md:31-37

This sequence diagram illustrates the internal calls between the path reduction entry point and the underlying distance calculation utilities.
Sources: src/index.js:8, src/perpendicular-distance.js:5-7

Function Specifications

perpendicularDistance(point, start, end)

Calculates how far a point is from a line.

• Parameters:
  • point: Object with lat and lng.
  • start: Object with lat and lng (segment start).
  • end: Object with lat and lng (segment end).
• Return: Number representing distance.

Sources: src/perpendicular-distance.js:3, README.md:33-35

distance(lat1, lon1, lat2, lon2)

Calculates the great-circle distance between two coordinates.

• Parameters:
  • lat1, lon1: Coordinates of first point.
  • lat2, lon2: Coordinates of second point.
• Return: Distance in kilometers.

Sources: src/distance.js:1-16

Summary

The Perpendicular Distance Logic is the geometric engine of the geo-path-reducer library. By combining spherical trigonometry (Haversine formula) with planar triangle geometry (Heron's formula), it provides a robust metric for the Douglas-Peucker algorithm to evaluate the significance of individual points within a geographic path. This allows the library to effectively simplify spatial data while adhering to a specified error threshold.