Полигон из коллекции широт и долгот - PullRequest
Новая
       13

Полигон из коллекции широт и долгот

2 голосов
/ 23 декабря 2011

У меня есть коллекция широт и долгот, и я собираю их наборы и хочу нарисовать полигон на их основе.

Наборы данных не будут контурами, поэтому потребуется алгоритм, чтобы определить, какие из них составляют контур многоугольника, содержащего все предоставленные широты и долготы. Этот многоугольник должен быть гибким, чтобы он мог быть вогнутым, если точки диктуют это.

Любая помощь будет оценена.

** ОБНОВЛЕНИЕ **

Извините, следовало бы поставить больше деталей.

Мой код ниже создает ужасно выглядящий многоугольник. Как объясняется в моем первом посте, я хочу создать хороший вогнутый или выпуклый многоугольник на основе предоставленных значений.

Просто нужен способ построения внешних значений.

Извиняюсь, если это все еще требует слишком много, но подумал, что это стоило сделать последнюю попытку. 

function initialize() {
    var myLatLng = new google.maps.LatLng(51.407431, -0.727142);
    var myOptions = {
        zoom: 12,
        center: myLatLng,
        mapTypeId: google.maps.MapTypeId.TERRAIN
    }; 

    var map = new google.maps.Map(document.getElementById("map_canvas"), myOptions);

    var bermudaTriangle;

    var map = new google.maps.Map(document.getElementById("map_canvas"), myOptions);

    var triangleCoords = [
    new google.maps.LatLng(51.392692, -0.740358),
new google.maps.LatLng(51.400618, -0.742469),
new google.maps.LatLng(51.40072, -0.72418),
new google.maps.LatLng(51.400732, -0.743817),
new google.maps.LatLng(51.401258, -0.743386),
new google.maps.LatLng(51.401264, -0.741445),
new google.maps.LatLng(51.401443, -0.725555),
new google.maps.LatLng(51.401463, -0.744042),
new google.maps.LatLng(51.402281, -0.739059)
    ];

    var minX = triangleCoords[0].lat();
    var maxX = triangleCoords[0].lat();
    var minY = triangleCoords[0].lng();
    var maxY = triangleCoords[0].lng();

    for (var i = 1; i < triangleCoords.length; i++) {
        if (triangleCoords[i].lat() < minX) minX = triangleCoords[i].lat();
        if (triangleCoords[i].lat() > maxX) maxX = triangleCoords[i].lat();
        if (triangleCoords[i].lng() < minY) minY = triangleCoords[i].lng();
        if (triangleCoords[i].lng() > maxY) maxY = triangleCoords[i].lng();
    }

    // Construct the polygon
    bermudaTriangle = new google.maps.Polygon({
        paths: triangleCoords,
        strokeColor: "#FF0000",
        strokeOpacity: 0.8,
        strokeWeight: 2,
        fillColor: "#FF0000",
        fillOpacity: 0.35
    });

    bermudaTriangle.setMap(map); 
}

1 Ответ

0 голосов
/ 28 декабря 2011

Ваша проблема недостаточно определена: с заданным набором точек вы можете получить много разных многоугольников, если не добавите ограничение, кроме «создать хороший вогнутый или выпуклый многоугольник».

И даже простой пример показывает, что: представьте треугольник ABC, и пусть D будет центром этого треугольника, какой выход вы ожидаете для набора точек {A, B, C, D}?

  1. ABC, так как D внутри?
  2. или полигон ADBCA?
  3. или полигон ABDCA?
  4. или ABCDA многоугольник?

Теперь, если вы скажете: «Хорошо, D находится в центре, очевидно, что мы должны отказаться от D», пусть D будет все ближе и ближе, скажем, от сегмента AB. Когда вы решите, что лучшим выходом будет ABC или ADBCA?

Таким образом, вы должны добавить ограничения, чтобы иметь возможность построить алгоритм, поскольку, если вы не можете сами решить для приведенного выше примера {A, B, C, D}, как компьютер может это сделать? :-) Например, если вы называете AvgD средним расстоянием между точками, вы можете добавить ограничение, согласно которому ни один сегмент вашего внешнего многоугольника не должен быть длиннее 1,2 * AvgD (или, лучше, Alpha * AvgD, и вы попробуете свой алгоритм с другим альфа).

Чтобы решить вашу проблему, я бы сначала использовал классический алгоритм оболочки, чтобы получить внешний выпуклый многоугольник (который является детерминированным), а затем разбил бы сегменты, которые являются «слишком длинными» (с желаемым ограничением), помещая все больше и больше внутренних точек в контуре, пока все ограничения не будут в порядке. Что-то вроде «копания ям» в выпуклый многоугольник.

«Сломать» слишком длинный сегмент - это тоже то, что вы можете делать совершенно другими способами. Можно искать ближайшую не в наброске точку от средней точки сегмента. Другой вариант - выбрать точку с наименьшим радиусом для текущего сегмента ... Теперь, когда у вас есть новая точка, разбейте сегмент на две части, обновите список слишком длинных сегментов и делайте это снова, пока не закончите (или пока вы не достигнете «удовлетворительной» средней длины для слишком длинных сегментов или ...)

Удачи!

...