Determine which side of a line a point lies.

Question

Hey guys,

I've got a line (x1,y1) and (x2, y2). I'd like to see if point (x3, y3) lies to the "left" or "right" of said line. How would I do so?

Answer 1

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 negatithe on the other (and zero for points on the line itself).

Answer 2

The vector (y1-y2,x2-x1) is perpendicular to the line, and always pointing right (or always pointing left, if you plane orientation is different from mine).

You can then compute the dot product of that vector and (x3-x1,y3-y1) to determine if the point lies on the same side of the line as the perpendicular vector (dot product > 0) or not.

Answer 3

Try this code it make use of cross product

public bool isLeft(Point a, Point b, Point c){
     return ((b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x)) > 0;
}

If the formula is equal to 0 points are colinear.

Answer 4

First check if you have a vertical line:

if (x2-x1) == 0
  if x3 < x2
     it's on the left
  if x3 > x2
     it's on the right
  else
     it's on the line

Then, calculate the slope: m = (y2-y1)/(x2-x1)

Then, create an equation of the line using point slope form: y - y1 = m*(x-x1) + y1. For the sake of my explanation, simplify it to slope-intercept form (not necessary in your algorithm): y = mx+b.

Now plug in (x3, y3) for x and y. Here is some pseudocode detailing what should happen:

if m > 0
  if y3 > m*x3 + b
    it's on the left
  else if y3 < m*x3 + b
    it's on the right
  else
    it's on the line
else if m < 0
  if y3 < m*x3 + b
    it's on the left
  if y3 > m*x3+b
    it's on the right
  else
    it's on the line
else
  horizontal line; up to you what you do

Answer 5

Say if your line is defined as f(x) = ax + b and you want to test it against the point (x1,y1) you can make something like this in pseudo-code:

int test(int x, int y)
 return f(x) - y
end

Negative values are points below the line, positive are above and 0 means the point belongs to the line.

Hope to have helped