How to tell whether a point is to the right or lef

问题:

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

回答1:

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.

回答2:

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

回答3:

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

回答4:

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.

回答5:

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));
}

回答6:

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

回答7:

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

回答8:

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 < p2x AND cy < p2y ==> means that C is upper and to left of p4

conclusion, C is inside the rectangle.

Thanks :)

回答9:

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.

回答10:

@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.

回答11:

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]
    (> (* (- 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

回答12:

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

回答13:

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)