hello, i am looking for a fast and efficient algorithm to check if two points are on the same side of a line or not. thanks a lot!

Quote: Original post by ehmdjii
hello, i am looking for a fast and efficient algorithm to check if two points are on the same side of a line or not.

thanks a lot!

ok, random idea here...

Find the interception point C of the line connecting your two points A and B with the other line. The fastest way to do this depend on your line representation. If |AC| < |AB|, the points are on different sides. If |AC| = |AB|, one of the points *is* on the line. If |AC| > |AB|, A and B are on the same side. Obviously, this is also the case if AB and the other line are parralel. There may be numerical annoyances...

A line in 2 dimensions is a 2d plane. It can be represented with a normal vector and a distance. Ax + By - D = 0. For an arbitrary point, Ax + By - D will give the signed distance of a point from the line (multiplied by the length of (A,B)). If the sign of the signed distance is the same for both points then they are on the same side of the line.

Another approach is to take the cross product of a vector in the direction of the line and an arbitrary vector from the line to the point. This gives a value proportional to the area of a signed triangle where one side is part of the line and the other sides connect to the point. Once again, just compare the signs to determine if the points are on the same side. This has the advantage of being easy to compute when the line is represented by two points or by a point and a direction vector.

For line AB and points C and D, C and D are on the same side if:

|AC X AB| and |AD X AB| have the same sign. (Those are vector cross-products).

How is your line specified? If you have it in Ax+By+C=0 form, just evaluate Ax+By+C for each point and check that they have the same sign.

If your line is specified by two points on it, this is what I would do. The "Algorithms" books by Robert Sedgewick describe a function called CCW (CounterClockWise) that given three points will return whether they describe a triangle counterclock-wise, clock-wise or whether they are aligned. That function can be trivially used to check if X and Y are on the same side of the line that connects A and B by checking whether CCW(A,B,X) == CCW(A,B,Y).

/* Taken from Robert Sedgewick, Algorithms in C++ *//*  returns whether, in traveling from the first to the second	to the third point, we turn counterclockwise (+1) or not (-1) */ int ccw( Point p0, Point p1, Point p2 ){	int dx1, dx2, dy1, dy2;		dx1 = p1.x - p0.x; dy1 = p1.y - p0.y;	dx2 = p2.x - p0.x; dy2 = p2.y - p0.y;		if (dx1*dy2 > dy1*dx2)		return +1;	if (dx1*dy2 < dy1*dx2)		return -1;	if ((dx1*dx2 < 0) || (dy1*dy2 < 0))		return -1;	if ((dx1*dx1 + dy1*dy1) < (dx2*dx2 + dy2*dy2))		return +1;	return 0;}

EDIT: Thinking about it a little more, you can compute a normal vector to (A-B) by swapping the coordinates and flipping one sign, and then just check if the dot products of that vector with (A-X) and with (A-Y) have the same sign.

The ccw function posted by Alvaro is basically the same as using the 2d cross products. Cross products would be more efficient because less conditional statements would be involved. By 2d cross product, I mean the dot product of one of the vectors and the perpendicular vector of the other. This comes out the same as the magnitude of the cross product if this were in 3 dimensions, with the direction of the cross product being perpendicular to the 2d plane.

Get the normal vector of that line plus any point in that line.

S = <point1 - point_in_line,normal>*<point2 - point_in_line,normal>

Being <a,b> the dot product.

S < 0 => both are on the same side of the line (angle between them is in the interval [0,PI/2)).
S = 0 => at least one is on the line.
S < 0 => both are on different sides of the line (angle between them is in the interval (PI/2,PI]).

bool points_on_same_side_of_line(const Vector2d &p1, const Vector2d &p2,                                 const Vector2d &p_line, const Vector2d &normal){    return normal.dot(p1 - p_line)*normal.dot(p2 - p_line) > 0.0f;}

Simple as that.