Sorting a List of 3d coplanar points to be clockwi

问题:

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:

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.