排序地理点以便将它们连接到封闭区域的算法

Question

我有地理点（位置），这意味着：具有 lat/lon 的 OOP 对象 + 我需要对它们进行处理以保持众所周知的位置空间关系 - 50N，15E 是右上角到 49N， 14E...

它们在数组中的顺序是随机的。我需要以这种方式对它们进行排序，其他众所周知的标准地理方法从数组中按顺序获取点并将它们连接到线，将导致关闭周围的线：

例如，如果我将此应用于我得到的点的一些当前随机顺序：

问题是 algorithm/pseudo 排序阶段的问题。为了简单起见，我们假设 Java（ArrayList，没有内存管理...）。

Answer 1

首先是找到中心点，得到每个点相对于中心点的极坐标（=方向和距中心点的距离），然后根据这些坐标对点进行排序。最简单的就是只看方向。运行 Java 脚本代码片段，以查看一个简单的版本（我不知道 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>

排序地理点以便将它们连接到封闭区域的算法

Algorithm to order geo-points in order to connect them to closing area

algorithm

graph-theory

geolocation

geospatial

graph-algorithm