How to Tell Whether a Point Is to the Right or Left Side of a Line

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

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.

How to tell if a point is on the left or right side of a line segment?

(I assumed a Cartesian coordinate system with the positive x and y pointing to the right and up respectively)

Given a line going through the points (a, b), (c, d), its equation is:

Now you have a point (e, f). If you substitute x=e, y=f, and they satisfy the equation, that means the point is on the line.

If the left side of the equation is bigger, that means your point is on the top of the line. If the right side of the equation is bigger, that means your point is below the line.

To figure out left/right, you need to consider the gradient as well. If the gradient is positive, being below the line means you are to the right of it. If the gradient is negative, being below the line means you are to the left of it. Vice versa.

Note that you need to handle vertical lines as a special case.

In Java,

double lhs = e;
double gradient = (b - d)/(a - c);
if (Double.isInfinite(gradient)) {
    // vertical line, compare only x coordinates
    if (e < a) {
        // on the left
    } else if (e > a) {
        // on the right
    } else {
        // on the line
    }
}
double rhs = (gradient * (e - a)) + b;
if (lhs > rhs) {
    if (gradient > 0) {
        // on the left
    } else if (gradient < 0) {
        // on the right
    } else {
        // on the top
    }
} else if (lhs < rhs) {
    if (gradient > 0) {
        // on the right
    } else if (gradient < 0) {
        // on the left
    } else {
        // below
    }
} else {
    // on the line
}

To prove that rearranging the order of the points doesn't change the result of this is quite simple. Changing the order of points produces this equation (a changes to c, b changes to d):

If you expand both the above equation and the one at the start, you will see that they are actually the same equation, which is:

Calculate on which side of a line a point is

Given a directed line from point p0(x0, y0) to p1(x1, y1), you can use the following condition to decide whether a point p2(x2, y2) is on the left of the line, on the right, or on the same line:

value = (x1 - x0)(y2 - y0) - (x2 - x0)(y1 - y0)

if value > 0, p2 is on the left side of the line.

if value = 0, p2 is on the same line.

if value < 0, p2 is on the right side of the line.

And here's a figure to explain it all:

How to tell whether a point is to the right or left side of a line given by point and angle

You have two vectors - direction vector D=(sin(a),cos(a)) and PZ. If their cross product is positive, then Z lies in left semiplane, otherwise - in right semiplane. What semiplane is considered as 'above' - depends on cos(a) sign.

Result = cos(a) * (sin(a) * PZ.Y - cos(a) * PZ.X) > 0

how to find a point is on left or right side of line using Python and DLib?

I would like you to refer to this point on Math StackExchange: https://math.stackexchange.com/questions/274712/calculate-on-which-side-of-a-straight-line-is-a-given-point-located. Simply put, given that you have three points: A point that denotes the beginning of the line, a point that denotes the end of the line and a query point, you can calculate the cross product between these three points and check the sign of the result. In fact, this answer on Stack Overflow uses this to determine if a point is on the left of a line: How to tell whether a point is to the right or left side of a line.

We can use this behaviour to help define if a point is to the left or right and can adjust based on the fact that you're using Python and DLib. Therefore, if the sign of the cross product is positive, the point is to the left of the line. If the sign is negative the point is to the right of the line. If the cross product is 0, then the point is collinear on the line. Because of numerical imprecision, comparing exactly with 0 is very dangerous as in most circumstances, getting exactly 0 is rare so comparing with exactly 0 may give you the wrong results. Therefore you'll want to see if the value is less than a small threshold, say 1e-9 for the collinear check.

With your example line, take note that it's essentially y = x so we can definitely define well-known points that should appear to the left and right of the line.

Therefore:

def where_it_is(line, point):
    aX = line.p1.x
    aY = line.p1.y
    bX = line.p2.x
    bY = line.p2.y
    cX = point.x
    cY = point.y

    val = ((bX - aX)*(cY - aY) - (bY - aY)*(cX - aX))
    thresh = 1e-9
    if val >= thresh:
        return "left"
    elif val <= -thresh:
        return "right"
    else:
        return "point is on the line"

To test this out:

import dlib

a = dlib.point(0, 0)
b = dlib.point(20, 20)
line = dlib.line(a, b)

pt1 = dlib.point(2, -2) # Should appear on the right
pt2 = dlib.point(5, 10) # Should appear on the left
pt3 = dlib.point(2, 2) # Point should be collinear

print(where_it_is(line, pt1))
print(where_it_is(line, pt2))
print(where_it_is(line, pt3))

I've defined points to be on the left, right and collinear on the line. We get:

In [40]: %paste
print(where_it_is(line, pt1))
print(where_it_is(line, pt2))
print(where_it_is(line, pt3))

## -- End pasted text --
right
left
point is on the line

How to tell if a point is left or right of another point

The answer is given to you by the sign of (x1-cx)(y2-cy) - (y1-cy)(x2-cx).

Proof:

Let A be the direction from C to (x1,y1), expressed as an angle measured anticlockwise from the X axis; B be the direction from C to (x2,y2), expressed the same way; and r be the radius of the circle. Then (x2,y2) is to the right of (x1,y1), as seen from C, if A-B lies between 0 and pi or between -2pi and -pi (that is, if sin(A-B) is positive), and to the left if A-B lies between -pi and 0 or between pi and 2pi (that is, if sin(A-B) is negative).

Now,

(x1,y1)=(Cx + r cos A, Cy + r sin A) 
(x2,y2)=(Cx + r cos B, Cy + r sin B)

So

  (x1-Cx)(y2-Cy) - (y1-Cy)(x2-Cy) 
= (r cos A)(r sin B) - (r sin A)(r cos B)    
= - r^2 (sin A cos B - cos A sin B)
= - r^2 (sin (A-B))

which has the opposite sign to sin (A-B).

How to tell whether a point is more to the right of a segment?

You have coordinates AX, AY, BX, BY and PX, PY for every other point.

It is necessary to calculate minimal angle between vectors P-B and A-B among all points P[i]

abx = AX - BX
aby = AY - BY  //calculate once

pbx = PX - BX
pby = PY - BY  //calculated for every point

angle = atan2(-pbx*aby+pby*abx, pbx*abx+pby*aby)
if angle < 0:
    angle += 2*Math.pi  //to make range 0..2*Pi

Calculate angle for every point (uses function atan2, Math.atan2 in some languages and cross product and dot product of vectors), then choose minimum value - it corresponds "the most right turn"

Python code

---

Related Topics