Sort points in clockwise order?

Question

Given an array of x,y points, how do I sort the points of this array in clockwise order (around their overall average center point)? My goal is to pass the points to a line-creation function to end up with something looking rather "solid", as convex as possible with no lines intersecting.

For what it's worth, I'm using Lua, but any pseudocode would be appreciated.

Update: For reference, this is the Lua code based on Ciamej's excellent answer (ignore my "app" prefix):

function appSortPointsClockwise(points)
    local centerPoint = appGetCenterPointOfPoints(points)
    app.pointsCenterPoint = centerPoint
    table.sort(points, appGetIsLess)
    return points
end

function appGetIsLess(a, b)
    local center = app.pointsCenterPoint

    if a.x >= 0 and b.x < 0 then return true
    elseif a.x == 0 and b.x == 0 then return a.y > b.y
    end

    local det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - center.y)
    if det < 0 then return true
    elseif det > 0 then return false
    end

    local d1 = (a.x - center.x) * (a.x - center.x) + (a.y - center.y) * (a.y - center.y)
    local d2 = (b.x - center.x) * (b.x - center.x) + (b.y - center.y) * (b.y - center.y)
    return d1 > d2
end

function appGetCenterPointOfPoints(points)
    local pointsSum = {x = 0, y = 0}
    for i = 1, #points do pointsSum.x = pointsSum.x + points[i].x; pointsSum.y = pointsSum.y + points[i].y end
    return {x = pointsSum.x / #points, y = pointsSum.y / #points}
end

Solution 1

First, compute the center point. Then sort the points using whatever sorting algorithm you like, but use special comparison routine to determine whether one point is less than the other.

You can check whether one point (a) is to the left or to the right of the other (b) in relation to the center by this simple calculation:

det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - center.y)

if the result is zero, then they are on the same line from the center, if it's positive or negative, then it is on one side or the other, so one point will precede the other. Using it you can construct a less-than relation to compare points and determine the order in which they should appear in the sorted array. But you have to define where is the beginning of that order, I mean what angle will be the starting one (e.g. the positive half of x-axis).

The code for the comparison function can look like this:

bool less(point a, point b)
{
    if (a.x - center.x >= 0 && b.x - center.x < 0)
        return true;
    if (a.x - center.x < 0 && b.x - center.x >= 0)
        return false;
    if (a.x - center.x == 0 && b.x - center.x == 0) {
        if (a.y - center.y >= 0 || b.y - center.y >= 0)
            return a.y > b.y;
        return b.y > a.y;
    }

    // compute the cross product of vectors (center -> a) x (center -> b)
    int det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - center.y);
    if (det < 0)
        return true;
    if (det > 0)
        return false;

    // points a and b are on the same line from the center
    // check which point is closer to the center
    int d1 = (a.x - center.x) * (a.x - center.x) + (a.y - center.y) * (a.y - center.y);
    int d2 = (b.x - center.x) * (b.x - center.x) + (b.y - center.y) * (b.y - center.y);
    return d1 > d2;
}

This will order the points clockwise starting from the 12 o'clock. Points on the same "hour" will be ordered starting from the ones that are further from the center.

If using integer types (which are not really present in Lua) you'd have to assure that det, d1 and d2 variables are of a type that will be able to hold the result of performed calculations.

If you want to achieve something looking solid, as convex as possible, then I guess you're looking for a Convex Hull. You can compute it using the Graham Scan. In this algorithm, you also have to sort the points clockwise (or counter-clockwise) starting from a special pivot point. Then you repeat simple loop steps each time checking if you turn left or right adding new points to the convex hull, this check is based on a cross product just like in the above comparison function.

Edit:

Added one more if statement if (a.y - center.y >= 0 || b.y - center.y >=0) to make sure that points that have x=0 and negative y are sorted starting from the ones that are further from the center. If you don't care about the order of points on the same 'hour' you can omit this if statement and always return a.y > b.y.

Corrected the first if statements with adding -center.x and -center.y.

Added the second if statement (a.x - center.x < 0 && b.x - center.x >= 0). It was an obvious oversight that it was missing. The if statements could be reorganized now because some checks are redundant. For example, if the first condition in the first if statement is false, then the first condition of the second if must be true. I decided, however, to leave the code as it is for the sake of simplicity. It's quite possible that the compiler will optimize the code and produce the same result anyway.

Solution 2

What you're asking for is a system known as polar coordinates. Conversion from Cartesian to polar coordinates is easily done in any language. The formulas can be found in this section.

After converting to polar coordinates, just sort by the angle, theta.

Solution 3

An interesting alternative approach to your problem would be to find the approximate minimum to the Traveling Salesman Problem (TSP), ie. the shortest route linking all your points. If your points form a convex shape, it should be the right solution, otherwise, it should still look good (a "solid" shape can be defined as one that has a low perimeter/area ratio, which is what we are optimizing here).

You can use any implementation of an optimizer for the TSP, of which I am pretty sure you can find a ton in your language of choice.

Solution 4

Another version (return true if a comes before b in counterclockwise direction):

    bool lessCcw(const Vector2D &center, const Vector2D &a, const Vector2D &b) const
    {
        // Computes the quadrant for a and b (0-3):
        //     ^
        //   1 | 0
        //  ---+-->
        //   2 | 3

        const int dax = ((a.x() - center.x()) > 0) ? 1 : 0;
        const int day = ((a.y() - center.y()) > 0) ? 1 : 0;
        const int qa = (1 - dax) + (1 - day) + ((dax & (1 - day)) << 1);

        /* The previous computes the following:

           const int qa =
           (  (a.x() > center.x())
            ? ((a.y() > center.y())
                ? 0 : 3)
            : ((a.y() > center.y())
                ? 1 : 2)); */

        const int dbx = ((b.x() - center.x()) > 0) ? 1 : 0;
        const int dby = ((b.y() - center.y()) > 0) ? 1 : 0;
        const int qb = (1 - dbx) + (1 - dby) + ((dbx & (1 - dby)) << 1);

        if (qa == qb) {
            return (b.x() - center.x()) * (a.y() - center.y()) < (b.y() - center.y()) * (a.x() - center.x());
        } else {
            return qa < qb;
       } 
    }

This is faster, because the compiler (tested on Visual C++ 2015) doesn't generate jump to compute dax, day, dbx, dby. Here the output assembly from the compiler:

; 28   :    const int dax = ((a.x() - center.x()) > 0) ? 1 : 0;

    vmovss  xmm2, DWORD PTR [ecx]
    vmovss  xmm0, DWORD PTR [edx]

; 29   :    const int day = ((a.y() - center.y()) > 0) ? 1 : 0;

    vmovss  xmm1, DWORD PTR [ecx+4]
    vsubss  xmm4, xmm0, xmm2
    vmovss  xmm0, DWORD PTR [edx+4]
    push    ebx
    xor ebx, ebx
    vxorps  xmm3, xmm3, xmm3
    vcomiss xmm4, xmm3
    vsubss  xmm5, xmm0, xmm1
    seta    bl
    xor ecx, ecx
    vcomiss xmm5, xmm3
    push    esi
    seta    cl

; 30   :    const int qa = (1 - dax) + (1 - day) + ((dax & (1 - day)) << 1);

    mov esi, 2
    push    edi
    mov edi, esi

; 31   : 
; 32   :    /* The previous computes the following:
; 33   : 
; 34   :    const int qa =
; 35   :        (   (a.x() > center.x())
; 36   :         ? ((a.y() > center.y()) ? 0 : 3)
; 37   :         : ((a.y() > center.y()) ? 1 : 2));
; 38   :    */
; 39   : 
; 40   :    const int dbx = ((b.x() - center.x()) > 0) ? 1 : 0;

    xor edx, edx
    lea eax, DWORD PTR [ecx+ecx]
    sub edi, eax
    lea eax, DWORD PTR [ebx+ebx]
    and edi, eax
    mov eax, DWORD PTR _b$[esp+8]
    sub edi, ecx
    sub edi, ebx
    add edi, esi
    vmovss  xmm0, DWORD PTR [eax]
    vsubss  xmm2, xmm0, xmm2

; 41   :    const int dby = ((b.y() - center.y()) > 0) ? 1 : 0;

    vmovss  xmm0, DWORD PTR [eax+4]
    vcomiss xmm2, xmm3
    vsubss  xmm0, xmm0, xmm1
    seta    dl
    xor ecx, ecx
    vcomiss xmm0, xmm3
    seta    cl

; 42   :    const int qb = (1 - dbx) + (1 - dby) + ((dbx & (1 - dby)) << 1);

    lea eax, DWORD PTR [ecx+ecx]
    sub esi, eax
    lea eax, DWORD PTR [edx+edx]
    and esi, eax
    sub esi, ecx
    sub esi, edx
    add esi, 2

; 43   : 
; 44   :    if (qa == qb) {

    cmp edi, esi
    jne SHORT $LN37@lessCcw

; 45   :        return (b.x() - center.x()) * (a.y() - center.y()) < (b.y() - center.y()) * (a.x() - center.x());

    vmulss  xmm1, xmm2, xmm5
    vmulss  xmm0, xmm0, xmm4
    xor eax, eax
    pop edi
    vcomiss xmm0, xmm1
    pop esi
    seta    al
    pop ebx

; 46   :    } else {
; 47   :        return qa < qb;
; 48   :    }
; 49   : }

    ret 0
$LN37@lessCcw:
    pop edi
    pop esi
    setl    al
    pop ebx
    ret 0
?lessCcw@@YA_NABVVector2D@@00@Z ENDP            ; lessCcw

Enjoy.

View more solutions

Comments

[President James K. Polk]

Think about compute the angle of the radial line through that point. Then sort by angle.

[Ponkadoodle]

In case you didn't know, lua has a builtin function ipairs(tbl) that iterates over the indices and values of tbl from 1 to #tbl. So for the sum calculation, you can do this, which most people find looks cleaner: for _, p in ipairs(points) do pointsSum.x = pointsSum.x + p.x; pointsSum.y = pointsSum.y + p.y end

[Alexander Gladysh]

@Wallacoloo That's highly arguable. Also, in vanilla Lua ipairs is significantly slower than numeric for loop.

[personalnadir]

I had to make some small changes to get it to work for my case (just comparing two points relative to a centre). gist.github.com/personalnadir/6624172 All those comparisons to 0 in the code seem to assume that the points are distributed around the origin, as opposed to an arbitrary point. I also think that first condition will sort points below the centre point incorrectly. Thanks for the code though, it's been really helpful!

[RBerteig]

This will work, but it will also have the defect of doing more computation than needed to answer the ordering question. In practice, you don't actually care about either the actual angles or radial distances, just their relative order. ciamej's solution is better because it avoids divisions, square roots, and trig.

[RBerteig]

+1: No atan(), no square root, and even no divisions. This is a good example of computer graphics thinking. Cull off all the easy cases as soon as possible, and even in the hard cases, compute as little as possible to know the required answer.

[Iterator]

I'm not sure what your criterion is for "better". For instance, comparing all points to each other is kind of a waste of computation. Trig isn't something that scares adults, is it?

[Iterator]

But it requires comparing all points to all others. Is there a simple method of inserting new points?

[ciamej]

if the set of points is known a priori it only takes O(n*log n) comparisons. If you want to add points in the meantime then you need to keep them in a sorted set such as a balanced binary search tree. In such a case adding a new point requires O(log n) comparisons and it's exactly the same for the solution involving polar coordinates.

[RBerteig]

It's not that trig is scary. The issue is that trig is expensive to compute, and wasn't needed to determine the relative order of the angles. Similarly, you don't need to take the square roots to put the radii in order. A full conversion from Cartesian to polar coordinates will do both an arc-tangent and a square root. Hence your answer is correct, but in the context of computer graphics or computational geometry it is likely to not be the best way to do it.

[Iterator]

Got it. However, the OP didn't post as comp-geo, that was a tag by someone else. Still, it looks like the other solution is polynomial in the # of points, or am I mistaken? If so, that burns more cycles than trig.

[Iterator]

Excellent. Then your solution is definitely better.

[RBerteig]

I hadn't actually noticed the comp-geo tag, I just assumed that the only rational applications for the question had to be one or the other. After all, the performance question becomes moot if there are only a few points, and/or the operation will be done rarely enough. At that point, knowing how to do it at all becomes important and that is why I agree your answer is correct. It explains how to compute the notion of a "clockwise order" in terms that can be explained to just about anybody.

[Iterator]

We're clearly all of the same mind: every cycle is precious. :)

[Philipp Lenssen]

Thanks so much for this answer. It's for a computer game but the calculation in question is not that time-critical, i.e. it would at most happen once every second or few seconds. A couple of microseconds more won't matter, though of course it shouldn't completely halt the game noticeably. I will give this approach a try!

[Iterator]

I'm glad to help. Thanks for the clarification on the usage & speed interest. My answer was focused on simplicity of understanding, but @ciamej's answer is certainly more computationally efficient. I'm glad this Q&A arose - I didn't realize that a comp-geo community was on SO, and I've learned something. I'll likely tap the comp-geo community expertise for some other problems. :)

[Philipp Lenssen]

Worked perfectly! For reference, I will include the Lua I ended up with based on Ciamej's work.

[Iterator]

Yikes. "Interesting" is an understatement. :)

[static_rtti]

@Iterator: I was quite happy with my idea, I was pretty disappointed to get downvoted for it :-/ Do you think it's valid?

[Iterator]

I didn't downvote, but think about the computational complexity of your suggestion.

[static_rtti]

I was suggesting to use one of the many fast approximations, not the NP-complete original algorithm, of course.

[Philipp Lenssen]

I appreciate the additional angle! To have several valid, if very different answers, might be of great help if someone in the future happens to stumble on this thread looking to brainstorm options.

[static_rtti]

Note that my approach is probably slower, but more correct in complex cases: imagine the case where the points for an "8", for example. Polar coordinates aren't going to help you in that case, and the result you will obtain will heavily depend on the center you chose. The TSP solution is independent of any "heuristic" parameters.

[psy]

any suggestions on what to do if theta is the same?

[Joshua Stachowski]

This worked perfectly! I was a little muffed when I found that the sorted array might be different each time, but it was just that the starting point was different. Once I stored it, I could easily splice a section from the end of the array to the front and get it exactly how I wanted. Thanks again!

[Daniel says Reinstate Monica]

Looks great. Could you edit your post so I can remove downvote?

[ceztko]

The comment on integer type is not entirely clear: in the code where are int det, int d1, int d2 wouldn't just be better to have double instead?

[ciamej]

@ceztko In my opinion it's always preferable to avoid floating-point arithmetic if possible. I assumed that the points' coordinates are given as integers, therefore all calculations are integer as well.

[ceztko]

@ciamej based on the fact that the they are really used for decision, and discarded after, I have the feeling floating point evalutation is better here even when the source data is integral. I may be wrong.

[ciamej]

@ceztko When using floating-point you have no guarantee that the result is computed exactly. Even if you only use it for decision-making, you may still make an erroneous decision. If we assume that 64 bit integer is wide enough to hold the result of computing det, and we substitute it with double we may get a different result. E.g. instead of getting a negative det, we may end up with det equal 0, and vice versa.

[ciamej]

I highly recommend you read "What Every Computer Scientist Should Know About Floating-Point Arithmetic" docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html

[ciamej]

If you want to I can find input that will break with double precision floating-point, but will work just fine with 64 bit integers.

[Tom Martin]

Is this missing the case: if (a.x - center.x < 0 && b.x - center.x >= 0) return false;

[ciamej]

@TomMartin Yes, you're right. That's really strange that nobody's noticed this so far.

[GeoGecco]

sorry, but could someone show me how to sort the List<Point> when using this 'less' method?

[ciamej]

@GeoGecco in which language?

[GeoGecco]

@caimej: A C# implementation would be great

[ciamej]

@GeoGecco Look here: stackoverflow.com/questions/3163922/sort-a-custom-class-list‌​t - it shows how to use a custom comparator. The difference here is that this less method returns true/false when in C# it should return negative/positive integer value.

[Alireza Pir]

thats a rely great method, But what if we have 3 Points at the same x? it dosent work fine for this case

[ciamej]

@Alireza.pir What do you mean by the same x? Can you show an example?

[Alireza Pir]

@ciamej Look At this picture: upload.udk.ir/uploads/Sorting.png in cases Like this, I want the vertices to be sorted as it is numbered in picture, but it sorts in the black Line order (The center Of points is also Point 3)

[Ismoh]

Hey there. It's pretty old, but: "This will order the points clockwise starting from the 12 o'clock." Why 12 o'clock and how can I change it to 6? Can anybody tell me?

[SirGuy]

For anyone looking for more information, this uses the cross-product between vectors.

[unagi]

The two return statements in the switch are mathematically equivalent. Is there a reason for having the switch?