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

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  ndash  angles smaller than 180 are on the right hand side  greater than 180 on the left hand side  ndash  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

User · Answer

I implemented this in java and ran a unit test (source below). None of the above solutions work. This code passes the unit test. If anyone finds a unit test that does not pass, please let me know.

Code: NOTE: nearlyEqual(double,double) returns true if the two numbers are very close.

/*
 * @return integer code for which side of the line ab c is on.  1 means
 * left turn, -1 means right turn.  Returns
 * 0 if all three are on a line
 */
public static int findSide(
        double ax, double ay, 
        double bx, double by,
        double cx, double cy) {
    if (nearlyEqual(bx-ax,0)) { // vertical line
        if (cx < bx) {
            return by > ay ? 1 : -1;
        }
        if (cx > bx) {
            return by > ay ? -1 : 1;
        } 
        return 0;
    }
    if (nearlyEqual(by-ay,0)) { // horizontal line
        if (cy < by) {
            return bx > ax ? -1 : 1;
        }
        if (cy > by) {
            return bx > ax ? 1 : -1;
        } 
        return 0;
    }
    double slope = (by - ay) / (bx - ax);
    double yIntercept = ay - ax * slope;
    double cSolution = (slope*cx) + yIntercept;
    if (slope != 0) {
        if (cy > cSolution) {
            return bx > ax ? 1 : -1;
        }
        if (cy < cSolution) {
            return bx > ax ? -1 : 1;
        }
        return 0;
    }
    return 0;
}

Here's the unit test:

@Test public void testFindSide() {
    assertTrue("1", 1 == Utility.findSide(1, 0, 0, 0, -1, -1));
    assertTrue("1.1", 1 == Utility.findSide(25, 0, 0, 0, -1, -14));
    assertTrue("1.2", 1 == Utility.findSide(25, 20, 0, 20, -1, 6));
    assertTrue("1.3", 1 == Utility.findSide(24, 20, -1, 20, -2, 6));

    assertTrue("-1", -1 == Utility.findSide(1, 0, 0, 0, 1, 1));
    assertTrue("-1.1", -1 == Utility.findSide(12, 0, 0, 0, 2, 1));
    assertTrue("-1.2", -1 == Utility.findSide(-25, 0, 0, 0, -1, -14));
    assertTrue("-1.3", -1 == Utility.findSide(1, 0.5, 0, 0, 1, 1));

    assertTrue("2.1", -1 == Utility.findSide(0,5, 1,10, 10,20));
    assertTrue("2.2", 1 == Utility.findSide(0,9.1, 1,10, 10,20));
    assertTrue("2.3", -1 == Utility.findSide(0,5, 1,10, 20,10));
    assertTrue("2.4", -1 == Utility.findSide(0,9.1, 1,10, 20,10));

    assertTrue("vertical 1", 1 == Utility.findSide(1,1, 1,10, 0,0));
    assertTrue("vertical 2", -1 == Utility.findSide(1,10, 1,1, 0,0));
    assertTrue("vertical 3", -1 == Utility.findSide(1,1, 1,10, 5,0));
    assertTrue("vertical 3", 1 == Utility.findSide(1,10, 1,1, 5,0));

    assertTrue("horizontal 1", 1 == Utility.findSide(1,-1, 10,-1, 0,0));
    assertTrue("horizontal 2", -1 == Utility.findSide(10,-1, 1,-1, 0,0));
    assertTrue("horizontal 3", -1 == Utility.findSide(1,-1, 10,-1, 0,-9));
    assertTrue("horizontal 4", 1 == Utility.findSide(10,-1, 1,-1, 0,-9));

    assertTrue("positive slope 1", 1 == Utility.findSide(0,0, 10,10, 1,2));
    assertTrue("positive slope 2", -1 == Utility.findSide(10,10, 0,0, 1,2));
    assertTrue("positive slope 3", -1 == Utility.findSide(0,0, 10,10, 1,0));
    assertTrue("positive slope 4", 1 == Utility.findSide(10,10, 0,0, 1,0));

    assertTrue("negative slope 1", -1 == Utility.findSide(0,0, -10,10, 1,2));
    assertTrue("negative slope 2", -1 == Utility.findSide(0,0, -10,10, 1,2));
    assertTrue("negative slope 3", 1 == Utility.findSide(0,0, -10,10, -1,-2));
    assertTrue("negative slope 4", -1 == Utility.findSide(-10,10, 0,0, -1,-2));

    assertTrue("0", 0 == Utility.findSide(1, 0, 0, 0, -1, 0));
    assertTrue("1", 0 == Utility.findSide(0,0, 0, 0, 0, 0));
    assertTrue("2", 0 == Utility.findSide(0,0, 0,1, 0,2));
    assertTrue("3", 0 == Utility.findSide(0,0, 2,0, 1,0));
    assertTrue("4", 0 == Utility.findSide(1, -2, 0, 0, -1, 2));
}

User · Answer

Here s a version  again using the cross product logic  written in Clojure      defn is-left   line point     let    x1 y1   x2 y2    sort line           x-pt y-pt  point        gt      - x2 x1   - y-pt y1       - y2 y1   - x-pt x1        Example usage    is-left    -3 -1   3 1    0 10   true   Which is to say that the point  0  10  is to the left of the line determined by  -3  -1  and  3  1    NOTE   This implementation solves a problem that none of the others  so far  does    Order matters when giving the points that determine the line   I e   it s a  directed line   in a certain sense   So with the above code  this invocation also produces the result of true    is-left    3 1   -3 -1    0 10   true   That s because of this snippet of code    sort line    Finally  as with the other cross product based solutions  this solution returns a boolean  and does not give a third result for collinearity  But it will give a result that makes sense  e g     is-left    1 1   3 1    10 1   false

User · Answer

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  lt  p2x AND cy  lt  p2y     means that C is upper and to left of p4  conclusion  C is inside the rectangle   Thanks

User · Answer

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 gt 0  then       point on left side  else if torque  lt 0 then       point on right side    else       point on line  end if

User · Answer

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  lt  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

User · Answer

AVB s answer in ruby  det   Matrix      x2 - x1    x3 - x1        y2 - y1    y3 - y1     determinant   If det is positive its above  if negative its below  If 0  its on the line

User · Answer

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

User · Answer

Try this code which makes use of a 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    gt  0      Where a   line point 1  b   line point 2  c   point to check against   If the formula is equal to 0  the points are colinear   If the line is horizontal  then this returns true if the point is above the line

User · Answer

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  lt  m x-x1    y1 then it is left side point eg  for i in rows     for j in cols       if j gt m i-a  b         image i  j  0

User · Answer

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    i j  1  T on pr line i j  lt 1  T on Sq i j  1  T on Snq i j  0  T   Q  i j  lt 0  T on Sq and beyond Q         i j   lt 0  0    lt 1   1     gt 1    ---------Q------ PR ---------  lt    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

User · Answer

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

User · Answer

First check if you have a vertical line   if  x2-x1     0   if x3  lt  x2      it s on the left   if x3  gt  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  gt  0   if y3  gt  m x3   b     it s on the left   else if y3  lt  m x3   b     it s on the right   else     it s on the line else if m  lt  0   if y3  lt  m x3   b     it s on the left   if y3  gt  m x3 b     it s on the right   else     it s on the line else   horizontal line  up to you what you do

User · Answer

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

User · Answer

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  quot left quot  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

User · Answer

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

[c#] How to tell whether a point is to the right or left side of a line

Examples related to c#

Examples related to math

Examples related to geometry

Examples related to convex-hull