CODEWITHSUNDEEP
javamathprocessingline
user13003226
user13003226

Reputation:

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

If we have a line segment (A.x, A.y, B.x, B.y) and a point (C.x, C.y), how am I able to tell whether the point is on the left or right, or top or bottom, of the line segment? I have tried solutions involving cross products from previous posts, but it led me to another problem. Using cross products made that the order of A and B matter. What other method is there so that the order of A and B does not matter?

Solution from previous posts:

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.

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

Upvotes: 5

Views: 1161

Answers (1)

Sweeper
Sweeper

Reputation: 271545

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

enter image description here

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

enter image description here

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:

enter image description here

Upvotes: 5

Related Questions