How do I find a point at a given distance along a route? epoly.js is giving me extremely inaccurate and unusable results
I'm trying to find the point along a Google Maps API Directions route given a distance from the starting point. I have my code working and it gives me very accurate results most of the time. However when I make very long directions requests (for example, 1,000+ kilometers), the results are less accurate, and the longer the directions route the more inaccurate the results are. Once I reach approximately 3,000 kilometers the results are off by about 4,000 meters, which is entirely unacceptable for my application.
The function I'm using to compute the point is from epoly.js, and the code is as follows:
google.maps.Polyline.prototype.GetPointAtDistance = function(metres) {
if (metres == 0) return this.getPath().getAt(0);
if (metres < 0) return null;
if (this.getPath().getLength() < 2) return null;
var dist=0;
var olddist=0;
for (var i=1; (i < this.getPath().getLength() && dist < metres); i++) {
olddist = dist;
dist += this.getPath().getAt(i).distanceFrom(this.getPath().getAt(i-1));
}
if (dist < metres) {
return null;
}
var p1= this.getPath().getAt(i-2);
var p2= this.getPath().getAt(i-1);
var m = (metres-olddist)/(dist-olddist);
return new google.maps.LatLng( p1.lat() + (p2.lat()-p1.lat())*m, p1.lng() + (p2.lng()-p1.lng())*m);
}
This epoly.js function has this dependency function:
google.maps.LatLng.prototype.distanceFrom = function(newLatLng) {
var EarthRadiusMeters = 6378137.0;
var lat1 = this.lat();
var lon1 = this.lng();
var lat2 = newLatLng.lat();
var lon2 = newLatLng.lng();
var dLat = (lat2-lat1) * Math.PI / 180;
var dLon = (lon2-lon1) * Math.PI / 180;
var a = Math.sin(dLat/2) * Math.sin(dLat/2) +
Math.cos(lat1 * Math.PI / 180 ) * Math.cos(lat2 * Math.PI / 180 ) *
Math.sin(dLon/2) * Math.sin(dLon/2);
var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));
var d = EarthRadiusMeters * c;
return d;
}
What is causing the result to be so inaccurate over large distances and what can I do to make it more accurate? (I need accuracy down to approximately 1-3 meters) Does the Google Maps API have any way to do this or is epoly.js my best bet? If so, then what can I change about the above code to make it give more accurate results?
I've been searching for an answer to this for a while, but everything I can find either recommends epoly.js or shows code snippets that perform exactly the same computations as epoly.js. It seems as though Google doesn't have any built-in way to do this, however I've seen something similar done in some applications like https://routeview.org, where you can clearly see the orange man tracing along the route perfectly even when navigating thousands of kilometers at a time, so I have to believe a higher level of accuracy is possible.
Here are two screenshots illustrating a short distance request and a long distance request. Note that it's very accurate over short distances but becomes wildly inaccurate over longer distances. Also note that the marker in the second image is being viewed from far away. It may look close to the path, but it's actually about 5,000 meters away on the other side of a large hill. (The marker in the first image is viewed from very close up, and even when viewed so closely it doesn't deviate from the path any noticeable amount)
This image is for a 20km route:
This image is for a 3326km route:
Here is code that demonstrated my issue. Zoom in on the marker to see that it misses the route by a long shot.
<!DOCTYPE html>
<html lang="en">
<head>
<title>Example</title>
</head>
<body>
<div id="map" style="width: 600px;height: 600px;"></div>
<script src="https://maps.googleapis.com/maps/api/js?key=YOUR_API_KEY_HERE&v=weekly&channel=2"></script>
<script>
google.maps.LatLng.prototype.distanceFrom = function(newLatLng) {
var EarthRadiusMeters = 6378137.0;
var lat1 = this.lat();
var lon1 = this.lng();
var lat2 = newLatLng.lat();
var lon2 = newLatLng.lng();
var dLat = (lat2-lat1) * Math.PI / 180;
var dLon = (lon2-lon1) * Math.PI / 180;
var a = Math.sin(dLat/2) * Math.sin(dLat/2) +
Math.cos(lat1 * Math.PI / 180 ) * Math.cos(lat2 * Math.PI / 180 ) *
Math.sin(dLon/2) * Math.sin(dLon/2);
var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));
var d = EarthRadiusMeters * c;
return d;
}
google.maps.Polyline.prototype.GetPointAtDistance = function(metres) {// Stolen from http://www.geocodezip.com/scripts/v3_epoly.js
if (metres == 0) return this.getPath().getAt(0);
if (metres < 0) return null;
if (this.getPath().getLength() < 2) return null;
var dist=0;
var olddist=0;
for (var i=1; (i < this.getPath().getLength() && dist < metres); i++) {
olddist = dist;
dist += this.getPath().getAt(i).distanceFrom(this.getPath().getAt(i-1));
}
if (dist < metres) {
return null;
}
var p1= this.getPath().getAt(i-2);
var p2= this.getPath().getAt(i-1);
var m = (metres-olddist)/(dist-olddist);
return new google.maps.LatLng( p1.lat() + (p2.lat()-p1.lat())*m, p1.lng() + (p2.lng()-p1.lng())*m);
}
</script>
<script>
const map = new google.maps.Map(document.getElementById("map"),{
center: { lat: 37, lng: -100 },
zoom: 4,
clickableIcons: false
});
const directionsRenderer = new google.maps.DirectionsRenderer();
directionsRenderer.setMap(map);
const directions = new google.maps.DirectionsService();
directions.route({
origin: "seattle, wa",
destination: "chicago, il",
travelMode: "DRIVING"
},(data) => {
const polyline = new google.maps.Polyline({
path: data.routes[0].overview_path
});
new google.maps.Marker({
map: map,
position: polyline.GetPointAtDistance(400000)
});
directionsRenderer.setDirections(data);
});
</script>
</body>
</html>
(You'll need to provide your own API key)
EDIT:
I found out that the issue is on Google's end. Google is giving me a "close enough" polyline. Epoly.js is tracing that polyline perfectly, but that polyline simply doesn't line up with the route itself. This picture demonstrates the issue:
The dark blue line is Google's "close enough" polyline, and the light blue line is where the actual route is.
Just thought I'd leave this here for anybody else who's confused by this in the future.
Don't use the overview_path for long paths, it won't be accurate for close zoom levels. Use the concatenated steps polylines:
var legs = response.routes[0].legs;
for (i=0;i<legs.length;i++) {
var steps = legs[i].steps;
for (j=0;j<steps.length;j++) {
var nextSegment = steps[j].path;
for (k=0;k<nextSegment.length;k++) {
polyline.getPath().push(nextSegment[k]);
}
}
}
Your original code (using the overview_path):
<!DOCTYPE html>
<html lang="en">
<head>
<title>Example</title>
</head>
<body>
<div id="map" style="width: 600px;height: 600px;"></div>
<script src="https://maps.googleapis.com/maps/api/js?key=AIzaSyCkUOdZ5y7hMm0yrcCQoCvLwzdM6M8s5qk&v=weekly&channel=2"></script>
<script>
google.maps.LatLng.prototype.distanceFrom = function(newLatLng) {
var EarthRadiusMeters = 6378137.0;
var lat1 = this.lat();
var lon1 = this.lng();
var lat2 = newLatLng.lat();
var lon2 = newLatLng.lng();
var dLat = (lat2-lat1) * Math.PI / 180;
var dLon = (lon2-lon1) * Math.PI / 180;
var a = Math.sin(dLat/2) * Math.sin(dLat/2) +
Math.cos(lat1 * Math.PI / 180 ) * Math.cos(lat2 * Math.PI / 180 ) *
Math.sin(dLon/2) * Math.sin(dLon/2);
var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));
var d = EarthRadiusMeters * c;
return d;
}
google.maps.Polyline.prototype.GetPointAtDistance = function(metres) {// Stolen from http://www.geocodezip.com/scripts/v3_epoly.js
if (metres == 0) return this.getPath().getAt(0);
if (metres < 0) return null;
if (this.getPath().getLength() < 2) return null;
var dist=0;
var olddist=0;
for (var i=1; (i < this.getPath().getLength() && dist < metres); i++) {
olddist = dist;
dist += this.getPath().getAt(i).distanceFrom(this.getPath().getAt(i-1));
}
if (dist < metres) {
return null;
}
var p1= this.getPath().getAt(i-2);
var p2= this.getPath().getAt(i-1);
var m = (metres-olddist)/(dist-olddist);
return new google.maps.LatLng( p1.lat() + (p2.lat()-p1.lat())*m, p1.lng() + (p2.lng()-p1.lng())*m);
}
</script>
<script>
const map = new google.maps.Map(document.getElementById("map"),{
center: { lat: 37, lng: -100 },
zoom: 14,
clickableIcons: false
});
const directionsRenderer = new google.maps.DirectionsRenderer({preserveViewport: true});
directionsRenderer.setMap(map);
const directions = new google.maps.DirectionsService();
directions.route({
origin: "seattle, wa",
destination: "chicago, il",
travelMode: "DRIVING"
},(data) => {
const polyline = new google.maps.Polyline({
path: data.routes[0].overview_path
});
var marker = new google.maps.Marker({
map: map,
position: polyline.GetPointAtDistance(400000)
});
map.setCenter(marker.getPosition());
directionsRenderer.setDirections(data);
});
</script>
</body>
</html>
updated code snippet using the detailed path:
<!DOCTYPE html>
<html lang="en">
<head>
<title>Example</title>
</head>
<body>
<div id="map" style="width: 600px;height: 600px;"></div>
<script src="https://maps.googleapis.com/maps/api/js?key=AIzaSyCkUOdZ5y7hMm0yrcCQoCvLwzdM6M8s5qk&v=weekly&channel=2"></script>
<script>
google.maps.LatLng.prototype.distanceFrom = function(newLatLng) {
var EarthRadiusMeters = 6378137.0;
var lat1 = this.lat();
var lon1 = this.lng();
var lat2 = newLatLng.lat();
var lon2 = newLatLng.lng();
var dLat = (lat2-lat1) * Math.PI / 180;
var dLon = (lon2-lon1) * Math.PI / 180;
var a = Math.sin(dLat/2) * Math.sin(dLat/2) +
Math.cos(lat1 * Math.PI / 180 ) * Math.cos(lat2 * Math.PI / 180 ) *
Math.sin(dLon/2) * Math.sin(dLon/2);
var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));
var d = EarthRadiusMeters * c;
return d;
}
google.maps.Polyline.prototype.GetPointAtDistance = function(metres) {// Stolen from http://www.geocodezip.com/scripts/v3_epoly.js
if (metres == 0) return this.getPath().getAt(0);
if (metres < 0) return null;
if (this.getPath().getLength() < 2) return null;
var dist=0;
var olddist=0;
for (var i=1; (i < this.getPath().getLength() && dist < metres); i++) {
olddist = dist;
dist += this.getPath().getAt(i).distanceFrom(this.getPath().getAt(i-1));
}
if (dist < metres) {
return null;
}
var p1= this.getPath().getAt(i-2);
var p2= this.getPath().getAt(i-1);
var m = (metres-olddist)/(dist-olddist);
return new google.maps.LatLng( p1.lat() + (p2.lat()-p1.lat())*m, p1.lng() + (p2.lng()-p1.lng())*m);
}
</script>
<script>
const map = new google.maps.Map(document.getElementById("map"),{
center: { lat: 37, lng: -100 },
zoom: 14,
clickableIcons: false
});
const directionsRenderer = new google.maps.DirectionsRenderer({preserveViewport: true});
directionsRenderer.setMap(map);
const directions = new google.maps.DirectionsService();
directions.route({
origin: "seattle, wa",
destination: "chicago, il",
travelMode: "DRIVING"
},(data) => {
const polyline = new google.maps.Polyline();
var legs = data.routes[0].legs;
for (i=0;i<legs.length;i++) {
var steps = legs[i].steps;
for (j=0;j<steps.length;j++) {
var nextSegment = steps[j].path;
for (k=0;k<nextSegment.length;k++) {
polyline.getPath().push(nextSegment[k]);
}
}
}
var marker = new google.maps.Marker({
map: map,
position: polyline.GetPointAtDistance(400000)
});
map.setCenter(marker.getPosition());
directionsRenderer.setDirections(data);
});
</script>
</body>
</html>result using the more detailed path (not the overview_path):
- Convert the greatest binary number (by number of binary digits) to decimal
- Reading excel file into array using javascript
- Why is Vue's Composable not Isolated?
- Refused to execute script, strict MIME type checking is enabled?
- contentEditable - Firefox <br /> tag
- How to listen for a page $emit in a nuxt layout?
- Why am I getting 'Cannot GET' in localhost for Vue npm run serve
- I can't use dynamic components in Nuxt 3
- Get all files within a folder containing string, push filenames to array and return array using Node FS
- How to fix bubbles when drawing with canvas?
- how to find duplicate number in an array and increment the duplicate value using javascript
- How to enable a checkbox with Javascript?
- Check/Uncheck checkbox with JavaScript
- Symfony 7.0 AssetMapper: JS Files Only Load on Initial Page Load or After F5 Refresh
- Checkbox checked not passing an actual value?
- Err Only plain objects, and a few built-ins, can be passed to Client Components from Server Components. Classes or null prototypes are not supported
- How wait to run JavaScript function until after the DOM is ready / loaded?
- MUI TextField Background Color for auto complete
- Regular expression isn't matching all hyperlinks in a string
- downloading file-stream from browser get request
- Problem with selecting a specific web element with Playwright in Python
- how to keep class attribute stored for Leaflet.js markers
- Index of last vowel in a string
- Delete a specific user from Firebase
- How to access DOM elements by type? (similar to getElementsByName())
- How to use a regular expression in a jQuery selector?
- How to getElementByName() with a regex?
- "user friendly" vimeo embedding, get embed code from url
- Is there a way to achieve currying with a local variable
- "BigInt literals are not available when targeting lower than ESNext"