Sorting a List of 3d coplanar points to be clockwise or counterclockwise

12
votes

I have a list of 3D points. I know they are all coplanar. I have the center that I want to sort them around and the normal to the plane on which the points and the center lie. How can I test if one point is right (or left) of another point?

I understand how to do it in 2D. Sort points in clockwise order? explains how to compare 2d points. So I think I need to somehow covert all the points and the center to local 2d plane coordinates. How can I do that? Is it the most efficient way to solve this problem?

//from link:
// a and b are points
//center is the center around which to determine order
//int num = (a.x-center.x) * (b.y-center.y) - (b.x - center.x) * (a.y - center.y);
//if num=0 then they're on the same line
//if num <0 or num>0 then a is to the left or right of b

How would I adapt this to handle 3d coplanar points?

1
mathgeometrylinear-algebra
"Clockwise" has no meaning in 3-d, since it depends on which way you look at the plane. Flip the plane around, and suddenly clockwise is counter-clockwise. - user85109
@woodchips The problem is not unique to 3-d. Not all 2-d coordinate systems are defined the same way either. In both cases, you just need to define what is meant by "clockwise". - DuckMaestro
I see what you are saying, that it a good thing to know. Do you think that specifying the plane's normal direction would clear this up? Clockwise doesn't mean a whole lot to me right now either, but I still need to order the points in some consistent direction. - AAB
Yes, if you specify the normal direction, then this will give you a consistent definition of clockwise. - user85109

1 Answers

20
votes

There's no need to convert everything to 2D.

You have the center C and the normal n. To determine whether point B is clockwise or counterclockwise from point A, calculate dot(n, cross(A-C, B-C)). If the result is positive, B is counterclockwise from A; if it's negative, B is clockwise from A.