How to tell whether a point is to the right or left side of a line

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

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)

equation of line is y-y1 = m(x-x1)

here m is y2-y1 / x2-x1

now put m in equation and put condition on y < m(x-x1) + y1 then it is left side point

eg.

for i in rows:

  for j in cols:

    if j>m(i-a)+b:

      image[i][j]=0

A(x1,y1) B(x2,y2) a line segment with length L=sqrt( (y2-y1)^2 + (x2-x1)^2 )

and a point M(x,y)

making a transformation of coordinates in order to be the point A the new start and B a point of the new X axis

we have the new coordinates of the point M

which are newX = ((x-x1)(x2-x1)+(y-y1)(y2-y1)) / L
from (x-x1)*cos(t)+(y-y1)*sin(t) where cos(t)=(x2-x1)/L, sin(t)=(y2-y1)/L

newY = ((y-y1)(x2-x1)-(x-x1)(y2-y1)) / L
from (y-y1)*cos(t)-(x-x1)*sin(t)

because "left" is the side of axis X where the Y is positive, if the newY (which is the distance of M from AB) is positive, then it is on the left side of AB (the new X axis) You may omit the division by L (allways positive), if you only want the sign