Skip to content

Instantly share code, notes, and snippets.

@IjzerenHein
Created August 16, 2016 11:33
Show Gist options
  • Save IjzerenHein/8db810ec6e30bf2dbfe1a7d99bde88ba to your computer and use it in GitHub Desktop.
Save IjzerenHein/8db810ec6e30bf2dbfe1a7d99bde88ba to your computer and use it in GitHub Desktop.
const R = 6371; // earths radius in km
function radiansFromDegrees(deg) {
return deg * (Math.PI / 180);
}
// reduce number of positions using the Ramer–Douglas–Peucker algorithm
// https://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm
// Code based on: https://www.namekdev.net/2014/06/iterative-version-of-ramer-douglas-peucker-line-simplification-algorithm/
function simplifyGeoCoordinates(positions, tolerance) {
if (positions.length <= 2) return positions;
const stack = [[0, positions.length - 1]];
const bitArray = new Int8Array(positions.length);
while (stack.length > 0) {
const startIndex = stack[stack.length - 1][0];
const endIndex = stack[stack.length - 1][1];
stack.splice(stack.length - 1, 1);
let dmax = 0;
let index = startIndex;
const pos0 = positions[index];
const cos0 = Math.cos(radiansFromDegrees(pos0.latitude));
for (let i = startIndex + 1; i < endIndex; i++) {
if (!bitArray[i]) {
const pos = positions[i];
const deltaLat = radiansFromDegrees(pos.latitude - pos0.latitude);
const deltaLng = radiansFromDegrees(pos.longitude - pos0.longitude);
const a = Math.sin(deltaLat / 2) * Math.sin(deltaLat / 2) +
cos0 * Math.cos(radiansFromDegrees(pos.latitude)) *
Math.sin(deltaLng / 2) * Math.sin(deltaLng / 2);
const c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
const d = R * c * 1000;
if (d > dmax){
index = i;
dmax = d;
}
}
}
if (dmax > tolerance){
stack.push([startIndex, index]);
stack.push([index, endIndex]);
}
else {
for (let i = startIndex + 1; i < endIndex; i++) {
bitArray[i] = true;
}
}
}
const result = [];
for (let i = 0, n = positions.length; i < n; i++) {
if (!bitArray[i]) result.push(positions[i]);
}
return result;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment