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.
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 thata[i] = atan2(P[i].y - M.y, P[i].x - M.x);
- sort points relative to their
a
value, usingqsort
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