Tell me more ×

I have a set of points. I want to separate them into 2 distinct sets. To do this, I chose two points (a and b) and draw an imaginary line between them. Now I want to have all points that are left from this line in one set and those that are right from this line in the other set.

My question is: How can I tell for any given point z wheter it is in the left or in the right set? I tried to calculate the angle between a-z-b - angles smaller than 180 are on the right hand side, greater than 180 on the left hand side - But because of the definition of ArcCos the calculated angels are always smaller than 180°. Is there a formula to calculate angels greater than 180° (or any other formula to chose right or left side)?

Thanks in advance, Frank

share|improve this question
To clarify, to the second part of your question, you can use atan2() instead of acos() to calculate the correct angle. However, using a cross product is the best solution to this as Eric Bainville pointed out. – dionyziz Sep 4 '11 at 12:20

3 Answers

up vote 32 down vote accepted

Use the sign of the determinant of vectors (AB,AM), where M(X,Y) is the query point:

position = sign( (Bx-Ax)*(Y-Ay) - (By-Ay)*(X-Ax) )

It is 0 on the line, and +1 on one side, -1 on the other side.

share|improve this answer
+1 nice, with one thing to be aware of: rounding error can be a concern when the point is very nearly on the line. Not a problem for most uses, but it does bite people from time to time. – Stephen Canon Oct 13 '09 at 14:18
Great! This is a nice one, without sinus, arccos and such :) Rounding errors are not a problem here, as I use the separating in an algorithm to calculate the convex hull of the pointset and draw a polyline around them. If a point is just outside the hull, it is no big problem. – Aaginor Oct 13 '09 at 14:53
Should you find yourself in a situation where rounding error on this test is causing you problems, you will want to look up Jon Shewchuk's "Fast Robust Predicates for Computational Geometry". – Stephen Canon Oct 13 '09 at 15:13
For clarification, this is the same as the Z-component of the cross product between the the line (b-a) and the vector to the point from a (m-a). In your favorite vector-class: position = sign((b-a).cross(m-a)[2]) – larsm Feb 9 '10 at 22:52

Using the equation of the line ab, get the x-coordinate on the line at the same y-coordinate as the point to be sorted.

  • If point's x > line's x, the point is to the right of the line.
  • If point's x < line's x, the point is to the left of the line.
  • If point's x == line's x, the point is on the line.
share|improve this answer
This is wrong, because as you can see from Aaginor's comment on the first answer, we don't want to figure out whether the point is on the left or right of the DIRECTED line AB, i.e. if you're standing on A and looking towards B is it on your left or on your right? – dionyziz Sep 4 '11 at 12:18
@dionyziz - Huh? My answer does not assign a "direction" to the line through AB. My answer assumes "left" is the -x direction of the corrdinate system. The accepted answer chose to define a vector AB, and define left using cross product. The original question does not specify what is meant by "left". – mbeckish Sep 6 '11 at 19:29

basically, I think that there is a solution which is much easier and straight forward, for any given polygon, lets say consist of four vertices(p1,p2,p3,p4), find the two extreme opposite vertices in the polygon, in another words, find the for example the most top left vertex (lets say p1) and the opposite vertex which is located at most bottom right (lets say ). Hence, given your testing point C(x,y), now you have to make double check between C and p1 and C and p4:

if cx > p1x AND cy > p1y ==> means that C is lower and to right of p1 next if cx < p2x AND cy < p2y ==> means that C is upper and to left of p4

conclusion, C is inside the rectangle.

Thanks :)

share|improve this answer

Your Answer


