排序幾何點以將它們連接到關閉區域的算法

我有地理點（位置），這意味着：OOP對象與緯度/經度+我需要對待他們保持衆所周知的位置空間關係 - 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

排序幾何點以將它們連接到關閉區域的算法

回答

相關問題