Алгоритм для упорядочивания геоточек для соединения их с закрывающей областью

У меня есть геотоны (местоположения), что означает: OOP Object с lat/lon + Мне нужно рассматривать их, поддерживая хорошо известную пространственную взаимосвязь местоположений - 50N, 15E сверху справа до 49N, 14E ... Алгоритм для упорядочивания геоточек для соединения их с закрывающей областью

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

Например, Если я применяю это на каком-то случайном порядке текущей точек я получил:

вопрос для алгоритма/псевдо для сортировки фазы. Для простоты предположим, что Java (ArrayList, без управления памятью ...).

источник

2015-08-15 michael

Началом было бы найти центральную точку, получить полярные координаты каждой точки относительно центральной точки (= направление и расстояние от центральной точки), а затем упорядочить точки в соответствии с этими координатами. Проще всего было бы смотреть только на направление. Запустите фрагмент кода Javascript, чтобы увидеть простую версию в действии (я не знаю Java).
Дальнейшее улучшение: избегать больших прыжков на расстоянии. Вы также можете попробовать несколько точек центра и использовать тот, который приводит к кратчайшей строке.

function geoOrder(points) { 
 
    var center = {x: 0, y: 0}; 
 
    for (var i in points) { 
 
     center.x += points[i].x; 
 
     center.y += points[i].y; 
 
    } 
 
    center.x /= points.length; 
 
    center.y /= points.length; 
 
    paintDot(canvas, center.x, center.y, 5, "red"); 
 
    for (var i in points) { 
 
     var dx = points[i].x - center.x; 
 
     var dy = points[i].y - center.y; 
 
     points[i].a = Math.atan2(dx, dy); 
 
     points[i].d = Math.sqrt(Math.pow(dx, 2) + Math.pow(dy, 2)); 
 
    } 
 
    points.sort(polarSort); 
 
    for (var i in points) { 
 
     delete points[i].a; 
 
     delete points[i].d; 
 
    } 
 

 
    function polarSort(p, q) { 
 
     if (p.a < q.a) return -1 
 
     else if (p.a > q.a) return 1 
 
     return 0; 
 
    } 
 
} 
 

 
// PREPARE CANVAS 
 
var canvas = document.getElementById("canvas"); 
 
canvas.width = 440; canvas.height = 346; 
 
canvas = canvas.getContext("2d"); 
 

 
// RUN FUNCTION ON TEST DATA 
 
var points = [{x:38,y:136},{x:151,y:96},{x:152,y:282},{x:172,y:270},{x:173,y:30},{x:181,y:177},{x:200,y:179},{x:273,y:125},{x:295,y:59},{x:350,y:172},{x:361,y:216},{x:370,y:190}]; 
 
geoOrder(points); 
 

 
// SHOW RESULT ON CANVAS 
 
for (var i in points) { 
 
    if (i > 0) paintLine(canvas, points[i-1].x, points[i-1].y, points[i].x, points[i].y, 1, "blue") 
 
    else paintLine(canvas, points[points.length-1].x, points[points.length-1].y, points[i].x, points[i].y, 1, "blue"); 
 
    paintDot(canvas, points[i].x, points[i].y, 5, "black"); 
 
} 
 
function paintDot(canvas, x, y, size, color) { 
 
canvas.beginPath(); 
 
canvas.arc(x, y, size, 0, 6.2831853); 
 
canvas.closePath(); 
 
canvas.fillStyle = color; 
 
canvas.fill(); 
 
} 
 
function paintLine(canvas, x1, y1, x2, y2, width, color) { 
 
canvas.beginPath(); 
 
canvas.moveTo(x1, y1); 
 
canvas.lineTo(x2, y2); 
 
canvas.strokeStyle = color; 
 
canvas.stroke(); 
 
}

<BODY STYLE="margin: 0; border: 0; padding: 0;"> 
 
<CANVAS ID="canvas" STYLE="width: 254px; height: 200px; background-color: #EEE;"></CANVAS>

источник

2015-08-15 21:13:04 m69

Алгоритм для упорядочивания геоточек для соединения их с закрывающей областью

ответ

Смежные вопросы