How to sort vertices of a polygon in counter clockwise order?

Question

How to sort vertices of a polygon in counter clockwise order?

I want to create a function (algorithm) which compares two vectors $\vec v$ and $\vec u$ which are vertices in a polygon. It should choose the vertex which counter clockwise index inside the polygon is higher. The first index should be the bottom left vertex.

I this example it should choose $\vec u$.

For the first quadrant I can say that $\vec u > \vec v$ if $|\vec u| > |\vec v|$ and $\forall\vec u > \forall\vec v$. The length should be weighted more than the angle in order that vertex 1 gets a lower index than vertex 2. But this rule only works for the first quadrant. I could first move the whole polygon into the first quadrant but I want to find a better solution. Any ideas?

Answer 1

If your polygon is convex, take any point in the interior of the polygon, e.g. the average of all the vertices. Then you can compute the angle of each vertex to the center point, and sort according to the computed angles. This will work for any point inside the polygon. Note you will get a circular ordering.

Answer 2

A faster alternative to the previous java answer doesn't require any trig functions and works with an array where every even index has an x coordinate and every odd one has a y coordinate.

float[] elements = ...;
Arrays.quickSort(0, elements.length / 2, (k1, k2) -> {
    int a = k1 * 2, b = k2 * 2;
    float ax = elements[a], ay = elements[a+1], bx = elements[b], by = elements[b+1];
    float aa = ax / ay, ab = bx / by;
    return ((int)Math.signum(ay * by)) * Float.compare(aa, ab);
}, (a, b) -> {
    int ai = a * 2, bi = b * 2;
    float bx = elements[bi], by = elements[bi+1];
    elements[bi] = elements[ai];
    elements[bi+1] = elements[ai+1];
    elements[ai] = bx;
    elements[ai+1] = by;
});