Determine which side of a line a point lies [duplicate]

Question

I have a set of points. I want to separate them into 2 distinct sets. To do this, I choose 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.

How can I tell for any given point z whether 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 angles are always smaller than 180°. Is there a formula to calculate angles greater than 180° (or any other formula to chose right or left side)?

Answer 1

Try this code which makes use of a cross product:

public bool isLeft(Point a, Point b, Point c){      return ((b.X - a.X)*(c.Y - a.Y) - (b.Y - a.Y)*(c.X - a.X)) > 0; } 

Where a = line point 1; b = line point 2; c = point to check against.

If the formula is equal to 0, the points are colinear.

If the line is horizontal, then this returns true if the point is above the line.

Answer 2

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.