Thursday, September 13, 2018

2d - Sorting array of points in clockwise order


Is there such an algorithm to sort an array of 2D points in clockwise order?
I'm specifically dealing with right triangle in my case so only 3 points.


However I'm interested in knowing if such an algorithm exist, if not what is a simple way to return the 3 points of my triangle in clockwise order?


Edit: I am trying to compute the points clockwise relative to the centroid of the polygon, which is convex.


Update: This is the implementation I ended up using based on the chosen answer, it's not performance critical and only happens once in a while so it works out.


ArrayList pointList = new ArrayList();
pointList.add(A);
pointList.add(B);

pointList.add(C);
Collections.sort( pointList, new TriangleVectorComparator(origin) );

return pointList;

// Comparator
package triangleeditor;

import java.util.Comparator;


import processing.core.PVector;

public class TriangleVectorComparator implements Comparator {
private PVector M;
public TriangleVectorComparator(PVector origin) {
M = origin;
}

public int compare(PVector o1, PVector o2) {
double angle1 = Math.atan2(o1.y - M.y, o1.x - M.x);

double angle2 = Math.atan2(o2.y - M.y, o2.x - M.x);

//For counter-clockwise, just reverse the signs of the return values
if(angle1 < angle2) return 1;
else if (angle2 < angle1) return -1;
return 0;
}

}

Answer




Your question is not precise enough. An array of points is only « clockwise » or « anti-clockwise » relative to a reference point. Otherwise, any array of three points can always be either CW or CCW. See the following picture: on the left, the points are ordered clockwise; on the right, the exact same points are ordered anticlockwise.


clockwise or anticlockwise


In your case, I believe using the barycenter of the points as a reference point is reasonable.


A good method for an unknown number of points could be the following one:



  • let P[0], P[1], ... P[n-1] be the list of points to sort

  • let M be the barycenter of all points

  • compute a[0], a[1], ... a[n-1] such that a[i] = atan2(P[i].y - M.y, P[i].x - M.x);

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



However, you can be sure that a good sorting algorithm will perform poorly with three input values compared to an ad-hoc method. Using atan2 is still valid, but just don't use qsort.


No comments:

Post a Comment

Simple past, Present perfect Past perfect

Can you tell me which form of the following sentences is the correct one please? Imagine two friends discussing the gym... I was in a good s...