Order array of points in counter clockwise

Question

I happened to see an answer to "Sort array of points in clockwise", could you please elaborate the 4th point of that answer:

• sort points relative to their a value, using qsort for instance.

How do I do the above step?

I'm looking for an algorithm to sort list of points in counter-clockwise.

Answer 1

Not familiar with the referenced article, but what I would do is:

1. Find the center of the point cloud
2. Use atan2 with the difference between each point and the center to find the angle each makes with the center
3. Sort by angle. You can either store the angle calculated in step 2 with each point (a Z value in a 3d coordinate created from each 2d coordinate is a convenient way to do this) or just skip step 2 and recalculate the angle in your sort comparer
4. Done!

Answer 2

The full quote from that answer is (I added the numbers for easy reference):

1. let P[0], P[1], ... P[n-1] be the list of points to sort
2. let M be the barycenter of all points
3. compute a[0], a[1], ... a[n-1] such that a[i] = atan2(P[i].y - M.y, P[i].x - M.x);
4. sort points relative to their a value, using qsort for instance.

The "a value" part of step 4 is referencing step 3. So, in step 4 it's saying "sort the points array based on the values in the array you made in step 3 (using something like quick sort)."

Now, if sorting that array of values will get you the clockwise order of points, then sorting it in reverse order will give you the points in a counter-/anti-clockwise direction.

Hopefully that clears it up a bit for you.