13

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?

Community
  • 1
  • 1
AAB
  • 674
  • 3
  • 14
  • 27
  • "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. –  Jan 17 '13 at 01:54
  • @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 Jan 17 '13 at 01:57
  • 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 Jan 17 '13 at 02:00
  • 1
    Yes, if you specify the normal direction, then this will give you a consistent definition of clockwise. –  Jan 17 '13 at 02:16

1 Answers1

21

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.

Beta
  • 96,650
  • 16
  • 149
  • 150
  • How would I get the angle between A and B? I added this but it seems too complicated: `sign(dot(n, cross(A-C, B-C)) * cos^{-1} { dot(A-C, B-C) / (|| A-C||_2 * ||B-C||_2) }` – stephanmg Oct 10 '19 at 08:27
  • 1
    @stephanmg: Yes, that seems overcomplicated. I'd probably define two new vectors `CA=A-C; CB=B-C;`, normalise `CA/=||CA||; CB/=||CB||;` and then use [`atan2`](https://en.wikipedia.org/wiki/Atan2). – Beta Oct 10 '19 at 17:11
  • Thanks. I thought I'd want to use atan2, however people have concerns usign atan2. Why? I couldn't quickly find one convincing argument. – stephanmg Oct 11 '19 at 07:40
  • This approach will fail if A and B are co-linear. – stephanmg Oct 23 '19 at 16:43
  • 1
    @stephanmg: Do you mean A and B are colinear with C? (Obviously A and B are always colinear.) If so, then the result is zero, which I would argue is the correct answer; in that case B is neither clockwise nor counterclockwise from A. (Or both, if you like.) – Beta Oct 24 '19 at 00:23
  • Beta: Well, in this case you are right. I had a slightly different underlying problem, where this would be not the behaviour I want. But this depends on the problem. Sorry for the confusion. – stephanmg Oct 24 '19 at 12:52
  • My point is actually that I'm getting the same value from dot(. , .) if I use for instance these points: B = [ -7.04462 -21.606552 -14.272003 ] and B' = [ -5.13538 -21.606552 -14.272003 ] A = [ -6.09 -19.84723 -14.785682 ] and the center C = [ -6.09, -21.0437, -14.4402 ]. Then dot(. , .) will give me the same value for B and B'. I'm not sure why. – stephanmg Oct 24 '19 at 13:22
  • @stephanmg: What are you using for n? – Beta Oct 24 '19 at 16:59
  • For n I calculate the cross product by cross(A-C, B-C). – stephanmg Oct 25 '19 at 07:43
  • Should I actually be calculating n = cross(A, B) and normalize n by n / ||n||? This yields the correct/expected behaviour. – stephanmg Oct 25 '19 at 10:38
  • @stephanmg: n is the normal. You can't just combine different vectors with different operations at random until you get the result you expected; You have go back and understand the mathematics before you write code, or you'll keep having these problems. – Beta Oct 25 '19 at 22:45
  • 1
    Beta: Thanks for the suggestion, it seems working through the maths again helped spot the problem. – stephanmg Oct 28 '19 at 10:12
  • If you came here to sort a polygon CCW or CW then one can proceed with the check @Beta mentioned. Make sure you iteratively repeat this and make sure to always pick the positive or negative value. – stephanmg Aug 06 '20 at 15:12