How to tell whether a point is to the right or lef

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

Assuming the points are (Ax,Ay) (Bx,By) and (Cx,Cy), you need to compute:

(Bx - Ax) * (Cy - Ay) - (By - Ay) * (Cx - Ax)

This will equal zero if the point C is on the line formed by points A and B, and will have a different sign depending on the side. Which side this is depends on the orientation of your (x,y) coordinates, but you can plug test values for A,B and C into this formula to determine whether negative values are to the left or to the right.

Answer 2

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 :)

Answer 3

An alternative way of getting a feel of solutions provided by netters is to understand a little geometry implications.

Let pqr=[P,Q,R] are points that forms a plane that is divided into 2 sides by line [P,R]. We are to find out if two points on pqr plane, A,B, are on the same side.

Any point T on pqr plane can be represented with 2 vectors: v = P-Q and u = R-Q, as:

T' = T-Q = i * v + j * u

Now the geometry implications:

1. i+j =1: T on pr line
2. i+j <1: T on Sq
3. i+j >1: T on Snq
4. i+j =0: T = Q
5. i+j <0: T on Sq and beyond Q.

i+j: <0 0 <1 =1 >1 ---------Q------[PR]--------- <== this is PQR plane ^ pr line

In general,

• i+j is a measure of how far T is away from Q or line [P,R], and
• the sign of i+j-1 implicates T's sideness.

The other geometry significances of i and j (not related to this solution) are:

• i,j are the scalars for T in a new coordinate system where v,u are the new axes and Q is the new origin;
• i, j can be seen as pulling force for P,R, respectively. The larger i, the farther T is away from R (larger pull from P).

The value of i,j can be obtained by solving the equations:

i*vx + j*ux = T'x
i*vy + j*uy = T'y
i*vz + j*uz = T'z

So we are given 2 points, A,B on the plane:

A = a1 * v + a2 * u B = b1 * v + b2 * u

If A,B are on the same side, this will be true:

sign(a1+a2-1) = sign(b1+b2-1)

Note that this applies also to the question: Are A,B in the same side of plane [P,Q,R], in which:

T = i * P + j * Q + k * R

and i+j+k=1 implies that T is on the plane [P,Q,R] and the sign of i+j+k-1 implies its sideness. From this we have:

A = a1 * P + a2 * Q + a3 * R B = b1 * P + b2 * Q + b3 * R

and A,B are on the same side of plane [P,Q,R] if

sign(a1+a2+a3-1) = sign(b1+b2+b3-1)

Answer 4

I wanted to provide with a solution inspired by physics.

Imagine a force applied along the line and you are measuring the torque of the force about the point. If the torque is positive (counterclockwise) then the point is to the "left" of the line, but if the torque is negative the point is the "right" of the line.

So if the force vector equals the span of the two points defining the line

fx = x_2 - x_1
fy = y_2 - y_1

you test for the side of a point (px,py) based on the sign of the following test

var torque = fx*(py-y_1)-fy*(px-x_1)
if  torque>0  then
     "point on left side"
else if torque <0 then
     "point on right side"  
else
     "point on line"
end if

Answer 5

You look at the sign of the determinant of

| x2-x1  x3-x1 |
| y2-y1  y3-y1 |

It will be positive for points on one side, and negative on the other (and zero for points on the line itself).

Answer 6

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.