Search code examples
algorithmgeolocationgeospatialgraph-theorygraph-algorithm

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

I have geo-points (locations), which means: OOP Object with lat/lon + I need to treat them maintaining the well known spatial relationship of locations - 50N,15E is top-right to 49N,14E... enter image description here

Their order in the array is random. I need to sort them in that way, that other well known standard geo-method that taking points in the order from the array and connecting them to line, will result closing surrounding line:

enter image description here

For example, If I apply this on some current random order of the points I got:

enter image description here

The question is for algorithm/pseudo for the sorting phase. For the sake of simplicity let's assume Java (ArrayList, no memory management...).

Solution

  • A start would be to find the center point, get the polar coordinates of every point relative to the center point (= direction and distance from center point), and then order the points according to those coordinates. Simplest would be to only look at the direction. Run the Javascript code snippet to see a simple version in action (I don't know Java).
    Further improvement: avoid big jumps in distance. You could also try several center points, and use the one which results in the shortest line. 

    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>