0

DBに記録されたいくつかのポイントがGPSから来ており、それをポリラインとして描画すると、醜いパスが作成されます。

Google サービスで道路へのスナップを作成しようとしました。100ポイントのみの制限があるため、小さなパスで正確なパスを取得します.900以上あります.

次に、 OSRM matching-serviceを試しました。OSM データに依存しますが、Google マップのように更新されません。ルートの元のポイントのパスが正しくありません

スムーズで正しい道にするために使用する他のアプローチはありますか？

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 個のバッチでスナップしてルート API に送信しました
  3. 結果の 3 つのポリラインを地図上に表示

結果

  1. 道路へのスナップは単純化された線があまり得意ではなく、奇妙なルートを選ぶのが好きです
  2. 妥当な結果を得るには、0.5 の許容値を使用する必要がありました (入力データが 2 分の 1 に減少しただけです)。一部のデータ セットでは、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 に答える