c# - Cómo saber si un punto está en el lado derecho o izquierdo de una línea

math geometry

Question

Tengo un conjunto de puntos. Quiero separarlos en 2 conjuntos distintos. Para hacer esto, elijo dos puntos ( ayb ) y dibujo una línea imaginaria entre ellos. Ahora quiero tener todos los puntos que quedan de esta línea en un conjunto y los que están bien desde esta línea en el otro conjunto.

¿Cómo puedo saber si un punto dado z está en el conjunto izquierdo o derecho? Intenté calcular el ángulo entre azb : ángulos más pequeños que 180 en el lado derecho, mayor que 180 en el lado izquierdo, pero debido a la definición de ArcCos, los ángulos calculados siempre son menores que 180 °. ¿Hay una fórmula para calcular ángulos mayores de 180 ° (o cualquier otra fórmula para elegir el lado derecho o izquierdo)?

Answer 1

Aquí hay una versión, otra vez usando la lógica de productos cruzados, escrita 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

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

NOTA: ¡Esta implementación resuelve un problema que ninguno de los otros (hasta ahora) hace! El orden importa al dar los puntos que determinan la línea. Es decir, es una "línea dirigida", en cierto sentido. Entonces, con el código anterior, esta invocación también produce el resultado de true :

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

Eso es por este fragmento de código:

(sort line)

Finalmente, al igual que con las otras soluciones basadas en productos cruzados, esta solución devuelve un valor booleano y no da un tercer resultado para la colinealidad. Pero dará un resultado que tenga sentido, por ejemplo:

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

Answer 2

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

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 que el vector perpendicular (producto de puntos> 0 ) o no.

Answer 3

Implementé esto en Java y ejecuté una prueba unitaria (fuente a continuación). Ninguna de las soluciones anteriores funciona. Este código pasa la prueba de unidad. Si alguien encuentra una prueba unitaria que no se aprueba, házmelo 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 la 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 4

La respuesta de @ AVB en ruby

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

Si det es positivo es anterior, si es negativo, está debajo. Si es 0, está en la línea.

Answer 5

Miras el signo del determinante de

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

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

Answer 6

Primero comprueba si tienes 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

Luego, calcule la pendiente: m = (y2-y1)/(x2-x1)

Luego, crea una ecuación de la línea usando la forma de la pendiente del punto: y - y1 = m*(x-x1) + y1 . Por el bien de mi explicación, simplifíquela a la forma pendiente-intersección (no necesaria en su algoritmo): y = mx+b .

Ahora conecte (x3, y3) para y . Aquí hay un pseudocódigo que detalla lo que debería 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 7

Pruebe este código que hace uso de un producto cruzado :

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 de línea 1; b = punto de línea 2; c = punto para verificar.

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

Si la línea es horizontal, esto devuelve verdadero si el punto está sobre la línea.

Answer 8

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

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

Esto será igual a cero si el punto C está en la línea formada por los puntos A y B, y tendrá un signo diferente dependiendo del lado. De qué lado depende depende de la orientación de las coordenadas (x, y), pero puede conectar 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 9

Usando la ecuación de la línea ab , obtenga la coordenada x en la línea en la misma coordenada y que el punto que se va a ordenar.

• Si el punto x> line es x, el punto está a la derecha de la línea.
• Si el punto es x <line''s x, el punto está a la izquierda de la línea.
• Si el punto es x == línea x, el punto está en la línea.

Answer 10

básicamente, creo que hay una solución que es mucho más fácil y directa, para cualquier polígono dado, digamos que consta de cuatro vértices (p1, p2, p3, p4), encuentra los dos vértices opuestos extremos en el polígono, en otro palabras, encuentre el vértice superior superior izquierdo (digamos p1) y el vértice opuesto que se encuentra en la parte inferior derecha (digamos). Por lo tanto, dado su punto de prueba C (x, y), ahora tiene que hacer una doble comprobación entre C y p1 y C y p4:

si cx> p1x AND cy> p1y ==> significa que C es menor y a la derecha de p1 luego si cx <p2x AND cy <p2y ==> significa que C es superior y a la izquierda de p4

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

Gracias :)

Answer 11

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