javascript — нарисуйте путь от местоположения GEO от GPS, привязанного к дороге

Моя первая мысль состоит в том, чтобы провести точки через алгоритм упрощения линии (например, Дуглас-Peucker).

Я сделал это с вашими точками:

1. пробежал точки через Дугласа-Пеукера
2. отправил их партиями по 100 в оснастку для маршрутизации API
3. отобразил три полученных полилинии на карте

Результаты

1. Привязка к дороге не очень хороша в упрощенных линиях, она любит выбирать странные маршруты
2. Мне пришлось использовать допуск 0,5, чтобы получить разумные результаты (что только уменьшило входные данные в 2 раза). Для некоторых наборов данных я могу использовать допуск 1, 10 и даже 30, что действительно сокращает объем данных, которые необходимо отправить в Roads API.

скрипка с отображением результатов (код не подходит в ответе

Код для реализации этого (обрабатывает до 300 упрощенных пунктов):

var simplifiedPolylines = [];
var simplifiedPolyline;
var simplifiedPoints = [];
var map;
var rawPolyline;
function initialize() {
var mapOptions = {
center: new google.maps.LatLng(38.990842,-76.93625),
zoom: 17,
mapTypeId: google.maps.MapTypeId.ROADMAP
};
map = new google.maps.Map(document.getElementById("map_canvas"),
mapOptions);
google.maps.event.addDomListener(document.getElementById('btn'), 'click', displayPolylineData);
displayPolylineData();
}
function displayPolylineData() {
var path = [];
var bounds = new google.maps.LatLngBounds();
for (var i=0; i<rawData.length; i++) {
path.push(rawData[i]);
bounds.extend(rawData[i]);
}
if (rawPolyline && rawPolyline.setMap) {
rawPolyline.setMap(null);
}

rawPolyline = new google.maps.Polyline({
path:path,
strokeOpacity: 0.4,
strokeWeight: 4,
strokeColor: "#FF0000",
map: map

});
map.fitBounds(bounds);
document.getElementById("info").innerHTML = "before DP simplification: " + path.length + "<br>";
var DPtolerance = parseFloat(document.getElementById("tolerance").value);
var simplifiedPath = GDouglasPeucker(path, DPtolerance);
document.getElementById("info").innerHTML += "after DP simplification: " + simplifiedPath.length + "<br>";
if (simplifiedPoints && simplifiedPoints.length > 0) {
for (var i=0; i<simplifiedPoints.length; i++) {
simplifiedPoints[i].setMap(null);
}
}
if (snappedPoints && snappedPoints.length > 0) {
for (var i=0; i<snappedPoints.length; i++) {
snappedPoints[i].setMap(null);
}
}

document.getElementById('simplified').innerHTML = 'Raw Polyline<input type="checkbox" name="rawpolyline" onclick="rawPolylineCheck(this);" checked="checked" /><br>';
document.getElementById('simplified').innerHTML += 'Simplified Markers <input type="checkbox" name="simplifiedmarks" onclick="simplifiedPointCheck(this);" checked="checked" /><br>';
document.getElementById('simplified').innerHTML += 'Simplified Polyline<input type="checkbox" name="simplifiedpolyline" onclick="simplifiedPolylineCheck(this);" checked="checked" /><br>';

simplifiedPoints = [];
var htmlString = "<b>simplified coordinates:</b><br>";
for (var i=0; i<simplifiedPath.length; i++) {
var mark = new google.maps.Marker({
position: simplifiedPath[i],
map: map,
icon: {
url: "https://maps.gstatic.com/intl/en_us/mapfiles/markers2/measle_blue.png",
size: new google.maps.Size(7,7),
anchor: new google.maps.Point(3.5,3.5)
},
title: ""+i
});
simplifiedPoints.push(mark);
htmlString += mark.getPosition().toUrlValue(6)+"<br>";
}
document.getElementById("simplified_coords").innerHTML = htmlString;

if (simplifiedPolyline && simplifiedPolyline.setMap) {
simplifiedPolyline.setMap(null);
}
if (snappedPolylines && (snappedPolylines.length > 0)) {
for (var i=0; i<snappedPolylines.length; i++) {
snappedPolylines[i].setMap(null);
}
}

simplifiedPolyline = new google.maps.Polyline({
map: map,
path: simplifiedPath,
strokeOpacity: 0.8,
strokeColor: "#0000FF",
strokeWidth: 1
});
simplifiedPolylines.push(simplifiedPolyline);
runSnapToRoad(simplifiedPolyline.getPath());

}
// Snap a user-created polyline to roads and draw the snapped path
function runSnapToRoad(path) {
htmlString = "<b>snapped coordinates:</b><br>";
document.getElementById('snapped').innerHTML = 'Snapped Markers <input type="checkbox" name="snappedmarks" onclick="snappedPointCheck(this);" checked="checked" /><br>';
document.getElementById('snapped').innerHTML += 'Snapped Polyline<input type="checkbox" name="snappedpolyline" onclick="snappedPolylineCheck(this);" checked="checked" /><br>';
var pathValues = [];
var i;
for (i = 0; (i < path.getLength() && i < 100); i++) {
pathValues.push(path.getAt(i).toUrlValue());
}
var jqxhr = $.get('https://roads.googleapis.com/v1/snapToRoads', {
interpolate: true,
key: apiKey,
path: pathValues.join('|')
}, function(data) {
processSnapToRoadResponse(data);
})
.fail(function(jqXHR, textStatus, errorThrown ) {
console.log("error:"+textStatus);
console.log("errorCode:"+errorThrown.code+" errorMsg:"+errorThrown.message);

alert( "error requesting points snapped to road\n"+textStatus );
})
if (path.getLength() > 100) {
pathValues = [pathValues[pathValues.length-1]];
for (; (i < path.getLength() && i < (200-1)); i++) {
pathValues.push(path.getAt(i).toUrlValue());
}
setTimeout(function() {
var jqxhr2 = $.get('https://roads.googleapis.com/v1/snapToRoads', {
interpolate: true,
key: apiKey,
path: pathValues.join('|')
}, function(data) {
processSnapToRoadResponse(data);
})
.fail(function( jqXHR, textStatus, errorThrown ) {
console.log("error:"+textStatus);
console.log("errorCode:"+errorThrown.code+" errorMsg:"+errorThrown.message);
alert( "error requesting points snapped to road (2)\n"+textStatus );
})
}, 5000);
} else if (path.getLength() > (200-1)) {
pathValues = [pathValues[pathValues.length-1]];
for (; (i < path.getLength() && i < (300-2)); i++) {
pathValues.push(path.getAt(i).toUrlValue());
}
setTimeout(function() {
var jqxhr2 = $.get('https://roads.googleapis.com/v1/snapToRoads', {
interpolate: true,
key: apiKey,
path: pathValues.join('|')
}, function(data) {
processSnapToRoadResponse(data);
})
.fail(function( jqXHR, textStatus, errorThrown ) {
console.log("error:"+textStatus);
console.log("errorCode:"+errorThrown.code+" errorMsg:"+errorThrown.message);
alert( "error requesting points snapped to road (2)\n"+textStatus );
})
}, 10000);
}
}

// Store snapped polyline returned by the snap-to-road method.
function processSnapToRoadResponse(data) {
snappedCoordinates = [];
var placeIdArray = [];

for (var i = 0; i < data.snappedPoints.length; i++) {
var latlng = new google.maps.LatLng(
data.snappedPoints[i].location.latitude,
data.snappedPoints[i].location.longitude);
snappedCoordinates.push(latlng);
placeIdArray.push({placeId: data.snappedPoints[i].placeId,
location: latlng,
originalIndex: data.snappedPoints[i].originalIndex});
}
drawSnappedPolyline(snappedCoordinates, placeIdArray);
}
// Draws the snapped polyline (after processing snap-to-road response).
var snappedPolylines = [];
function drawSnappedPolyline(snappedCoordinates, placeIdArray) {
var snappedPolyline = new google.maps.Polyline({
path: snappedCoordinates,
strokeColor: 'black',
strokeWeight: 3
});
snappedPolylines.push(snappedPolyline);
for (var i=0; i<snappedCoordinates.length; i++) {
var mark = new google.maps.Marker({
position: snappedCoordinates[i],
map: map,
icon: {
url: "https://maps.gstatic.com/intl/en_us/mapfiles/markers2/measle.png",
size: new google.maps.Size(7,7),
anchor: new google.maps.Point(3.5,3.5)
},
_index: i,
title: ""+i
});
htmlString += mark.getPosition().toUrlValue(6)+"<br>";

google.maps.event.addListener(mark, 'click', function(evt){
infowindow.setContent("mark "+this._index+"<br>origIdx: "+placeIdArray[this._index].originalIndex+"<br>placeId: "+placeIdArray[this._index].placeId+"<br>location: "+placeIdArray[this._index].location);
infowindow.open(map, this);
});
snappedPoints.push(mark);
}
snappedPolyline.setMap(map);
document.getElementById("snapped_coords").innerHTML = htmlString;
}
google.maps.event.addDomListener(window, 'load', initialize);

var snappedPoints = [];
function snappedPointCheck(cb) {
var arg;
if (cb.checked) {
arg=map;
} else {
arg=null;
}
for (var i=0; i<snappedPoints.length; i++) {
snappedPoints[i].setMap(arg);
}
}
function snappedPolylineCheck(cb) {
for (var i=0; i<snappedPolylines.length; i++) {
if (cb.checked) {
snappedPolylines[i].setMap(map);
} else {
snappedPolylines[i].setMap(null);
}
}
}
function simplifiedPointCheck(cb) {
var arg;
if (cb.checked) {
arg=map;
} else {
arg=null;
}
for (var i=0; i<simplifiedPoints.length; i++) {
simplifiedPoints[i].setMap(arg);
}
}
function simplifiedPolylineCheck(cb) {
for (var i=0; i<simplifiedPolylines.length; i++) {
if (cb.checked) {
simplifiedPolylines[i].setMap(map);
} else {
simplifiedPolylines[i].setMap(null);
}
}
}
function rawPolylineCheck(cb) {
if (cb.checked) {
rawPolyline.setMap(map);
} else {
rawPolyline.setMap(null);
}
}

Дуглас-Peucker:

/* Stack-based Douglas Peucker line simplification routine
returned is a reduced GLatLng array
After code by  Dr. Gary J. Robinson,
Environmental Systems Science Centre,
University of Reading, Reading, UK
*/

function GDouglasPeucker (source, kink)
/* source[] Input coordinates in GLatLngs   */
/* kink in metres, kinks above this depth kept  */
/* kink depth is the height of the triangle abc where a-b and b-c are two consecutive line segments */
{
var n_source, n_stack, n_dest, start, end, i, sig;
var dev_sqr, max_dev_sqr, band_sqr;
var x12, y12, d12, x13, y13, d13, x23, y23, d23;
var F = ((Math.PI / 180.0) * 0.5 );
var index = new Array(); /* aray of indexes of source points to include in the reduced line */
var sig_start = new Array(); /* indices of start & end of working section */
var sig_end = new Array();

/* check for simple cases */

if ( source.length < 3 )
return(source);    /* one or two points */

/* more complex case. initialize stack */

n_source = source.length;
band_sqr = kink * 360.0 / (2.0 * Math.PI * 6378137.0);  /* Now in degrees */
band_sqr *= band_sqr;
n_dest = 0;
sig_start[0] = 0;
sig_end[0] = n_source-1;
n_stack = 1;

/* while the stack is not empty  ... */
while ( n_stack > 0 ){

/* ... pop the top-most entries off the stacks */

start = sig_start[n_stack-1];
end = sig_end[n_stack-1];
n_stack--;

if ( (end - start) > 1 ){  /* any intermediate points ? */

/* ... yes, so find most deviant intermediate point to
either side of line joining start & end points */

x12 = (source[end].lng() - source[start].lng());
y12 = (source[end].lat() - source[start].lat());
if (Math.abs(x12) > 180.0)
x12 = 360.0 - Math.abs(x12);
x12 *= Math.cos(F * (source[end].lat() + source[start].lat()));/* use avg lat to reduce lng */
d12 = (x12*x12) + (y12*y12);

for ( i = start + 1, sig = start, max_dev_sqr = -1.0; i < end; i++ ){

x13 = (source[i].lng() - source[start].lng());
y13 = (source[i].lat() - source[start].lat());
if (Math.abs(x13) > 180.0)
x13 = 360.0 - Math.abs(x13);
x13 *= Math.cos (F * (source[i].lat() + source[start].lat()));
d13 = (x13*x13) + (y13*y13);

x23 = (source[i].lng() - source[end].lng());
y23 = (source[i].lat() - source[end].lat());
if (Math.abs(x23) > 180.0)
x23 = 360.0 - Math.abs(x23);
x23 *= Math.cos(F * (source[i].lat() + source[end].lat()));
d23 = (x23*x23) + (y23*y23);

if ( d13 >= ( d12 + d23 ) )
dev_sqr = d23;
else if ( d23 >= ( d12 + d13 ) )
dev_sqr = d13;
else
dev_sqr = (x13 * y12 - y13 * x12) * (x13 * y12 - y13 * x12) / d12;// solve triangle

if ( dev_sqr > max_dev_sqr  ){
sig = i;
max_dev_sqr = dev_sqr;
}
}

if ( max_dev_sqr < band_sqr ){   /* is there a sig. intermediate point ? */
/* ... no, so transfer current start point */
index[n_dest] = start;
n_dest++;
}
else{
/* ... yes, so push two sub-sections on stack for further processing */
n_stack++;
sig_start[n_stack-1] = sig;
sig_end[n_stack-1] = end;
n_stack++;
sig_start[n_stack-1] = start;
sig_end[n_stack-1] = sig;
}
}
else{
/* ... no intermediate points, so transfer current start point */
index[n_dest] = start;
n_dest++;
}
}

/* transfer last point */
index[n_dest] = n_source-1;
n_dest++;

/* make return array */
var r = new Array();
for(var i=0; i < n_dest; i++)
r.push(source[index[i]]);
return r;

}