simplifyGeoCoordinates.js

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;
}