Cómo saber si un punto está a la derecha o a la izquierda de una línea

Question

Tengo un conjunto de puntos.Quiero separarlos en 2 conjuntos distintos.Para hacer esto, puedo elegir dos puntos (un y b) y trace una línea imaginaria entre ellos.Ahora quiero tener todos los puntos que están a la izquierda de esta línea en un conjunto y los que están a la derecha de esta línea en el otro conjunto.

¿Cómo puedo saber para cualquier punto dado z si es en la izquierda o en el conjunto de la derecha?Traté de calcular el ángulo entre a-z-b – ángulos menores de 180 están en el lado derecho, de más de 180 en el lado izquierdo, pero a causa de la definición de ArcCos, el calculado los ángulos son siempre menores que 180°.Existe una formula para calcular los ángulos de más de 180° (o cualquier otra fórmula que eligió a la derecha o a la izquierda)?

Answer 1

Utilice el signo del determinante de vectores (AB,AM), donde M(X,Y) es el punto de consulta:

position = sign((Bx - Ax) * (Y - Ay) - (By - Ay) * (X - Ax))

Es 0 en la línea, y +1 en un lado, -1 en el otro lado.

Answer 2

Trate de este código que hace uso de un producto vectorial :

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

Donde a = punto 1 línea; punto 2 b = línea; c = punto para comprobar en contra.

Si la fórmula es igual a 0, los puntos son colineales.

Si la línea es horizontal, entonces este devuelve verdadero si el punto está por encima de la línea.

Answer 3

Te ves en el signo del determinante de

| x2-x1  x3-x1 |
| y2-y1  y3-y1 |

Será positivo para los puntos en un lado, y negativo en el otro (y cero para puntos de la línea en sí).

Answer 4

El (y1 - y2, x2 - x1) vector es perpendicular a la línea, y siempre apunta hacia la derecha (o siempre apunta hacia la izquierda, si orientación del plano es diferente de la mina).

A continuación, puede calcular el producto escalar de ese vector y (x3 - x1, y3 - y1) para determinar si el punto se encuentra en el mismo lado de la línea como el vector perpendicular (dot producto> 0) o no.

Answer 5

I implementado esta en java y se pasó una prueba de la unidad (fuente a continuación). Ninguna de las soluciones de trabajo por encima. Este código pasa la prueba de la unidad. Si alguien encuentra una prueba de unidad que no pasa, por favor hágamelo saber.

Código: NOTA:. nearlyEqual(double,double) devuelve verdadero si los dos números están muy cerca

/*
 * @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;
}

Aquí está la prueba de unidad:

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

Answer 6

Uso de los href="http://en.wikipedia.org/wiki/Linear_equation" de la línea ab , obtener el coordenada x en la línea en la misma coordenada y como el punto a clasificar.

• Si del punto x> x de la línea, el punto está a la derecha de la línea.
• Si el punto de x
• Si x del punto == x de la línea, el punto está en la línea.

Answer 7

En primer lugar comprobar si tiene una línea vertical:

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

A continuación, calcular la pendiente: m = (y2-y1)/(x2-x1)

A continuación, crear una ecuación de la línea utilizando la forma pendiente punto: y - y1 = m*(x-x1) + y1. Por el bien de mi explicación, simplificarlo a la forma pendiente-intersección (no es necesario en su algoritmo): y = mx+b

.

Ahora conecte (x3, y3) para x y y. Aquí hay alguna pseudocódigo que detalla lo que debe suceder:

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 8

Básicamente, creo que hay una solución que es mucho más fácil y sencillo, para cualquier polígono dado, digamos que constará de cuatro vértices (p1, p2, p3, p4), encontrar los dos vértices opuestos extremos en el polígono , en otras palabras, encontrar el por ejemplo el vértice más arriba a la izquierda (digamos p1) y el vértice opuesto que se encuentra en la mayor parte inferior derecha (digamos). Por lo tanto, teniendo en cuenta su punto de prueba C (x, y), ahora usted tiene que hacer doble control entre C y C y p1 y p4:

si cx> P1X y Cy> P1Y ==> significa que C es más baja y a la derecha del p1 próximo si cx significa que C es superior y a la izquierda del p4

conclusión, C está dentro del rectángulo.

Gracias :)

Answer 9

Suponiendo que los puntos son (Ax, Ay) (Bx, By) y (Cx, Cy), es necesario calcular:

(Bx - Ax) * (Cy - Ay) - (Al - Ay) * (Cx - Ax)

Esta será igual a cero si el punto C se encuentra en la línea formada por los puntos A y B, y tendrá un signo diferente dependiendo de la cara. Qué lado esto es depende de la orientación de su (x, y) las coordenadas, pero se puede enchufar valores de prueba para A, B y C en esta fórmula para determinar si los valores negativos están a la izquierda o a la derecha.

Answer 10

@AVB la respuesta en rubí

det = Matrix[
  [(x2 - x1), (x3 - x1)],
  [(y2 - y1), (y3 - y1)]
].determinant

Si det es positivo que su anterior, si su negativa a continuación.Si es 0, su en la línea.

Answer 11

Aquí hay una versión, utilizando de nuevo la lógica de producto cruzado, escrito en 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)))))

Ejemplo de uso:

(is-left? [[-3 -1] [3 1]] [0 10])
true

es decir, que el punto (0, 10) es a la izquierda de la línea determinada por (-3, -1) y (3, 1).

NOTA: Esta aplicación resuelve un problema que ninguno de los otros (hasta ahora) hace! asuntos Solicitar al dar los puntos que determinan la línea. Es decir, se trata de una "línea dirigida", en un cierto sentido. Así que con el código anterior, esta invocación también produce el resultado de true:

(is-left? [[3 1] [-3 -1]] [0 10])
true

Esto se debe a este fragmento de código:

(sort line)

Finalmente, como con las otras soluciones basadas producto cruzado, esta solución devuelve un valor booleano, y no da un tercer resultado de la colinealidad. Pero va a dar un resultado que tiene sentido, por ejemplo:.

(is-left? [[1 1] [3 1]] [10 1])
false

Answer 12

quería proporcionarle una solución inspirada en la física.

Imagine una fuerza aplicada a lo largo de la línea y que está midiendo el par de la fuerza sobre el punto. Si el par es positivo (hacia la izquierda), entonces el punto está a la "izquierda" de la línea, pero si el par es negativo, el punto es el "derecho" de la línea.

Así que si el vector de fuerza es igual a la duración de los dos puntos que definen la línea

fx = x_2 - x_1
fy = y_2 - y_1

se prueba por el lado de una (px,py) punto a partir de la señal de la siguiente prueba

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

Answer 13

Una forma alternativa de conseguir una sensación de soluciones proporcionadas por las rederas es entender un poco de geometría implicaciones.

Vamos pqr=[P,Q,R] son los puntos que forma un plano que está dividido en 2 partes por la línea de [P,R].Vamos a averiguar si dos puntos en pqr plano, a,B, están en el mismo lado.

Cualquier punto de T en pqr plano se puede representar con 2 vectores: v = P-Q y u = R-P, como:

T' = T-P = yo * v + j * u

Ahora la geometría implicaciones:

1. i+j =1:T en la línea de pr
2. i+j <1:T Sq
3. i+j >1:T en Snq
4. i+j =0:T = P
5. i+j <0:T en Sq y más allá de P.

i+j: <0 0 <1 =1 >1 ---------Q------[PR]--------- <== this is PQR plane ^ pr line

En general,

• i+j es una medida de hasta qué punto T es la distancia de P o de la línea de [P,R], y
• el signo de i+j-1 implica T sideness.

Los otros significados de la geometría yo y j (no relacionados con esta solución):

• yo,j son los escalares T en un nuevo sistema de coordenadas donde v,u son los nuevos ejes y Q es el nuevo origen;
• yo, j puede ser visto como la fuerza de tracción para P,R, respectivamente.El más grande yo, cuanto más lejos está lejos de T R (mayor extracción de P).

El valor de i,j puede ser obtenida mediante la resolución de las ecuaciones:

i*vx + j*ux = T'x
i*vy + j*uy = T'y
i*vz + j*uz = T'z

Así se nos da 2 puntos, a,B en el plano:

A = a1 * v + a2 * u B = b1 * v + b2 * u

Si a,B están en el mismo lado, esto será cierto:

sign(a1+a2-1) = sign(b1+b2-1)

Tenga en cuenta que esto se aplica también a la pregunta: Son a,B en el mismo lado del plano [P,Q,R], en la que:

T = yo * P + j * Q + k * R

y i+j+k=1 implica que T es en el plano [P,Q,R] y la señal de i+j+k-1 implica su sideness.A partir de esto tenemos:

A = a1 * P + a2 * Q + a3 * R B = b1 * P + b2 * Q + b3 * R

y a,B, están en el mismo lado del plano [P,Q,R] si

sign(a1+a2+a3-1) = sign(b1+b2+b3-1)