0

我在 DB 中记录了一些来自 GPS 的点，当我将其绘制为折线时，会形成一条丑陋的路径。

我试图通过谷歌服务快速上路；它在小路径中获得了准确的路径，因为它只有 100 个点的限制，我有超过 900 个。

然后我尝试了OSRM 匹配服务。它取决于 OSM 数据，但不像谷歌地图那样更新；路线的原始点路径错误

有没有其他方法可以使它顺利并在正确的道路上？

24.771891, 46.779722
24.770298, 46.780829
24.767267, 46.783101
24.764658, 46.785037
24.764626, 46.785056
24.764626, 46.785056
24.764429, 46.785162
24.764389, 46.785126
24.762272, 46.781747
24.761208, 46.780051
24.760184, 46.778384
24.758, 46.774842
24.756952, 46.773162
24.755906, 46.77143
24.754869, 46.769754
24.754283, 46.769098
24.754178, 46.76913
24.753171, 46.769786
24.753088, 46.769741
24.752075, 46.768083
24.750992, 46.766323
24.749939, 46.764602
24.748898, 46.762912
24.746805, 46.759517
24.745794, 46.757837
24.744741, 46.756163
24.743715, 46.754509
24.741587, 46.751046
24.740488, 46.749222
24.739446, 46.747472
24.737827, 46.744954
24.73772, 46.744941
24.737618, 46.745027
24.737589, 46.745082
24.7376, 46.745232
24.738664, 46.746954
24.739533, 46.748454
24.739491, 46.748592
24.739296, 46.748749
24.735994, 46.750701
24.734318, 46.751574
24.732608, 46.752445
24.730843, 46.753338
24.7292, 46.754166
24.727408, 46.755078
24.725634, 46.755974
24.722184, 46.757718
24.720533, 46.758557
24.71879, 46.759434
24.717093, 46.760285
24.715384, 46.761162
24.71371, 46.762141
24.712086, 46.763302
24.70892, 46.765562
24.707325, 46.766698
24.705762, 46.767811
24.704174, 46.768931
24.702605, 46.76991
24.699056, 46.771619
24.697229, 46.772346
24.695371, 46.773094
24.693531, 46.773834
24.691741, 46.774557
24.689936, 46.775226
24.686262, 46.776272
24.684325, 46.776646
24.682534, 46.776931
24.68067, 46.777248
24.678821, 46.777562
24.675216, 46.778694
24.673467, 46.779562
24.671883, 46.780582
24.670357, 46.781795
24.668755, 46.783062
24.665714, 46.785392
24.664072, 46.78648
24.662362, 46.787411
24.6606, 46.788262
24.658928, 46.789046
24.657203, 46.789875
24.655432, 46.790634
24.653747, 46.791392
24.653594, 46.791453
24.653514, 46.791418
24.653467, 46.791328
24.652752, 46.789472
24.651981, 46.787632
24.651203, 46.785722
24.650688, 46.784253
24.650768, 46.784192
24.651362, 46.783811
24.65132, 46.783638
24.649979, 46.780458
24.649915, 46.780442
24.649795, 46.780509
24.649208, 46.780829
24.649117, 46.780803
24.649085, 46.780765
24.647461, 46.777024
24.646678, 46.775216
24.646106, 46.774006
24.642701, 46.775725
24.640992, 46.776557
24.639336, 46.777373
24.635904, 46.779072
24.634282, 46.779942
24.632662, 46.780838
24.631006, 46.781786
24.627483, 46.783245
24.626557, 46.78344
24.626509, 46.783408
24.626488, 46.78337
24.626123, 46.781293
24.625594, 46.77937
24.624086, 46.775654
24.623011, 46.774003
24.621797, 46.772499
24.620475, 46.771043
24.617502, 46.768605
24.615765, 46.767632
24.614091, 46.76656
24.612358, 46.765232
24.610827, 46.763888
24.608168, 46.761069
24.606987, 46.75952
24.605874, 46.757843
24.604837, 46.75607
24.603811, 46.754182
24.602774, 46.75233
24.601768, 46.750518
24.599696, 46.746845
24.598738, 46.745082
24.597805, 46.743347
24.596802, 46.741555
24.595835, 46.739789
24.594811, 46.737933
24.593781, 46.73608
24.592787, 46.734272
24.59085, 46.730774
24.589942, 46.72905
24.589083, 46.727203
24.588331, 46.725299
24.587587, 46.723373
24.586958, 46.721344
24.585987, 46.717386
24.585659, 46.715334
24.585462, 46.713258
24.58548, 46.711142
24.58588, 46.709078
24.588002, 46.705846
24.58972, 46.705085
24.591546, 46.70457
24.593323, 46.704112
24.595067, 46.703629
24.59868, 46.703434
24.600472, 46.704118
24.601926, 46.705379
24.603453, 46.706445
24.605195, 46.707114
24.606554, 46.707408
24.606901, 46.708077
24.606933, 46.708086
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.608176, 46.707856
24.606816, 46.707971
24.60653, 46.707408
24.60653, 46.707357
24.606547, 46.707328
24.606605, 46.707312
24.610453, 46.707248
24.614214, 46.707139
24.616154, 46.706954
24.617966, 46.706736
24.619838, 46.706483
24.62168, 46.70623
24.622246, 46.706134
24.622322, 46.706048
24.622349, 46.705952
24.622306, 46.705789
24.622234, 46.705722
24.622082, 46.705693
24.618374, 46.706211
24.616514, 46.706429
24.614667, 46.706506
24.61097, 46.706624
24.609165, 46.706662
24.607328, 46.706694
24.605485, 46.706467
24.603698, 46.705872
24.600504, 46.70375
24.59868, 46.703018
24.596779, 46.702877
24.594982, 46.703235
24.591277, 46.704125
24.589506, 46.704589
24.587757, 46.70536
24.586741, 46.706605
24.585861, 46.708438
24.585102, 46.710384
24.585013, 46.71255
24.585597, 46.716835
24.586046, 46.718944
24.586566, 46.720944
24.587198, 46.722995
24.587925, 46.725018
24.58868, 46.72688
24.589509, 46.728704
24.591382, 46.732214
24.592413, 46.734026
24.593427, 46.735878
24.594379, 46.737648
24.595318, 46.739357
24.596395, 46.741286
24.598381, 46.744909
24.5994, 46.746742
24.600414, 46.748602
24.601338, 46.75031
24.60233, 46.752099
24.60331, 46.753869
24.605253, 46.757344
24.606352, 46.759069
24.607554, 46.760698
24.608837, 46.762192
24.610296, 46.763686
24.61327, 46.766227
24.614829, 46.767322
24.616411, 46.768266
24.618077, 46.769347
24.619637, 46.77063
24.621085, 46.772122
24.62232, 46.773677
24.624302, 46.777219
24.625059, 46.77921
24.625592, 46.78128
24.625941, 46.783421
24.626269, 46.785446
24.626605, 46.7876
4

1 回答 1

2

我的第一个想法是通过线简化算法（如Douglas-Peucker）运行这些点。

我用你的观点做到了这一点：

  1. 通过 Douglas-Peuker 跑分
  2. 将它们分批发送 100 个到 snap to route API
  3. 在地图上显示三个生成的折线

结果

  1. snap to road 不太擅长简化线路，喜欢挑奇怪的路线
  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);
  }
}

道格拉斯-普克：

/* 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;

}
于 2016-02-17T05:06:21.927 回答