6
$\begingroup$

Given a list (of arbitrary length) of 2-dimensional points, is there some algorithm that I can employ to sort this list of points into an order such that line segments sequentially drawn from $p_0 \rightarrow p_1 \rightarrow \ldots \rightarrow p_{n-1} \rightarrow p_n \rightarrow p_0$ would form a non-self-intersecting polygon?

$\endgroup$
  • $\begingroup$ Thanks. The convex hull isn't exactly what I'm looking for, in that I don't want to remove any points from the resultant polygon, but the first step of the Grahm Scan algorithm should get me where I need to be. I can sort based on the angle that a line segment through the point and the lower-right point of the set makes with the X axis.If you want to write up your comment in an answer form, I will mark it as the accepted answer. $\endgroup$ – danBhentschel Feb 2 '16 at 21:34
  • 3
    $\begingroup$ Thanks. Are you aware that there's nothing wrong with answering your own question? Do that and I'll upvote it, since you need the rep more than I do. Otherwise, I'll provide an answer when I come back later. $\endgroup$ – Rick Decker Feb 2 '16 at 21:47
  • 1
    $\begingroup$ I just wanted to give credit where credit is due. You pointed me in the right direction, so I wanted to give you a chance to get the reward. I have posted (what I believe is) a solution to the problem. Thanks for your help. $\endgroup$ – danBhentschel Feb 3 '16 at 2:28
4
$\begingroup$

Thanks to the advice of Rick Decker, I was able to create an algorithm based on the first half of the Grahm Scan convex hull algorithm, as detailed here.

The first step of the Grahm Scan is to sort the points in a set based on the angle made with the X axis when drawing a line through the point and the lower-right point of the set. This seems to solve the problem for all point sets that I can think of, with a single addition...

If two or more points form the same angle with the X axis (i.e. are aligned with respect to the reference point) then those points should be sorted based on distance from the reference point.

Here is an implementation of the algorithm in JavaScript:

function sortPoints(points) {
    points = points.splice(0);
    var p0 = {};
    p0.y = Math.min.apply(null, points.map(p=>p.y));
    p0.x = Math.max.apply(null, points.filter(p=>p.y == p0.y).map(p=>p.x));
    points.sort((a,b)=>angleCompare(p0, a, b));
    return points;
};

function angleCompare(p0, a, b) {
    var left = isLeft(p0, a, b);
    if (left == 0) return distCompare(p0, a, b);
    return left;
}

function isLeft(p0, a, b) {
    return (a.x-p0.x)*(b.y-p0.y) - (b.x-p0.x)*(a.y-p0.y);
}

function distCompare(p0, a, b) {
    var distA = (p0.x-a.x)*(p0.x-a.x) + (p0.y-a.y)*(p0.y-a.y);
    var distB = (p0.x-b.x)*(p0.x-b.x) + (p0.y-b.y)*(p0.y-b.y);
    return distA - distB;
}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.