Como saber se um ponto está no lado direito ou esquerdo de uma linha

Eu tenho um conjunto de pontos. Eu quero separá-los em 2 conjuntos distintos. Para fazer isso, eu escolho dois pontos ( um e b ) e desenhar uma linha imaginária entre eles. Agora eu quero ter todos os pontos que restam desta linha em um conjunto e os que estão à direita dessa linha no outro conjunto.

Como posso saber para qualquer ponto z se ele está no conjunto esquerdo ou no conjunto certo? Tentei calcular o ângulo entre azb - ângulos menores que 180 estão no lado direito, maiores que 180 no lado esquerdo - mas, devido à definição do ArcCos, os ângulos calculados são sempre menores que 180 °. Existe uma fórmula para calcular ângulos maiores que 180 ° (ou qualquer outra fórmula para escolher o lado direito ou esquerdo)?

Use o sinal do determinante de vetores (AB,AM), onde M(X,Y)está o ponto de consulta:

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

Está 0na linha, e +1de um lado, -1do outro lado.

Experimente este código que utiliza um produto 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;
}

Onde a = ponto da linha 1; b = ponto da linha 2; c = ponto para verificar.

Se a fórmula for igual a 0, os pontos serão colineares.

Se a linha for horizontal, isso retornará verdadeiro se o ponto estiver acima da linha.

Você olha para o sinal do determinante de

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

Será positivo para pontos de um lado e negativo no outro (e zero para pontos na própria linha).

O vetor (y1 - y2, x2 - x1)é perpendicular à linha e sempre apontando para a direita (ou sempre apontando para a esquerda, se você planeja uma orientação diferente da minha).

Você pode então calcular o produto escalar desse vetor e (x3 - x1, y3 - y1)determinar se o ponto está no mesmo lado da linha que o vetor perpendicular (produto escalar> 0) ou não.

Usando a equação da linha ab , obtenha a coordenada x na linha na mesma coordenada y que o ponto a ser classificado.

• Se x do ponto> x da linha, o ponto está à direita da linha.
• Se x do ponto <linha x, o ponto fica à esquerda da linha.
• Se o ponto x == linha x, o ponto está na linha.

Primeiro verifique se você tem uma linha 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

Em seguida, calcule a inclinação: m = (y2-y1)/(x2-x1)

Em seguida, crie uma equação da linha, utilizando o formulário inclinação ponto: y - y1 = m*(x-x1) + y1. Por uma questão de explicação, simplifique-a para a forma de interceptação de inclinação (não é necessária no seu algoritmo):y = mx+b .

Agora conecte (x3, y3)para xe y. Aqui estão alguns pseudocódigo detalhando o que deve acontecer:

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

Eu implementei isso em java e executei um teste de unidade (fonte abaixo). Nenhuma das soluções acima funciona. Este código passa no teste de unidade. Se alguém encontrar um teste de unidade que não passe, entre em contato.

Código: NOTA: nearlyEqual(double,double)retorna verdadeiro se os dois números estiverem muito próximos.

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

Aqui está o teste de unidade:

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

Assumindo que os pontos são (Ax, Ay) (Bx, By) e (Cx, Cy), você precisa calcular:

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

Isso será igual a zero se o ponto C estiver na linha formada pelos pontos A e B e terá um sinal diferente, dependendo do lado. De que lado isso depende da orientação de suas coordenadas (x, y), mas você pode inserir valores de teste para A, B e C nessa fórmula para determinar se os valores negativos estão à esquerda ou à direita.

Eu queria fornecer uma solução inspirada na física.

Imagine uma força aplicada ao longo da linha e você está medindo o torque da força sobre o ponto. Se o torque for positivo (sentido anti-horário), o ponto será "esquerdo" da linha, mas se o torque for negativo, o ponto será "direito" da linha.

Portanto, se o vetor de força for igual ao intervalo dos dois pontos que definem a linha

fx = x_2 - x_1
fy = y_2 - y_1

você testa o lado de um ponto com (px,py)base no sinal do seguinte teste

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

basicamente, acho que existe uma solução muito mais fácil e direta, para qualquer polígono, digamos, consistir em quatro vértices (p1, p2, p3, p4), encontrar os dois vértices extremos opostos no polígono, em outro palavras, encontre, por exemplo, o vértice superior esquerdo (digamos p1) e o vértice oposto, localizado no canto inferior direito (digamos). Portanto, dado o ponto de teste C (x, y), agora você deve fazer uma verificação dupla entre C e p1 e C e p4:

se cx> p1x AND cy> p1y ==> significa que C é menor e à direita de p1 a seguir se cx <p2x AND cy <p2y ==> significa que C é superior e à esquerda de p4

conclusão, C está dentro do retângulo.

Obrigado :)

@ Resposta do AVB em ruby

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

Se deté positivo é acima, se negativo é abaixo. Se 0, está na linha.

Aqui está uma versão, novamente usando a lógica de produtos cruzados, escrita em 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)))))

Exemplo de uso:

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

O que significa que o ponto (0, 10) fica à esquerda da linha determinada por (-3, -1) e (3, 1).

NOTA: Esta implementação resolve um problema que nenhum dos outros (até agora) resolve! A ordem é importante ao fornecer os pontos que determinam a linha. Ou seja, é uma "linha direcionada", em certo sentido. Portanto, com o código acima, essa invocação também produz o resultado de true:

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

Isso ocorre por causa desse trecho de código:

(sort line)

Finalmente, como nas outras soluções baseadas em produtos cruzados, essa solução retorna um valor booleano e não fornece um terceiro resultado para a colinearidade. Mas dará um resultado que faça sentido, por exemplo:

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

Uma maneira alternativa de obter uma idéia das soluções fornecidas pelos netters é entender algumas implicações geométricas.

Seja pqr = [P, Q, R] pontos que formam um plano dividido em 2 lados pela linha [P, R] . Devemos descobrir se dois pontos no pqr plano , A, B, estão do mesmo lado.

Qualquer ponto T no plano pqr pode ser representado com 2 vetores: v = PQ e u = RQ, como:

T '= TQ = i * v + j * u

Agora as implicações da geometria:

1. i + j = 1: T na linha pr
2. i + j <1: T em Sq
3. i + j> 1: T no Snq
4. i + j = 0: T = Q
5. i + j <0: T em Sq e além de Q.

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

Em geral,

• i + j é uma medida de quão longe T está de Q ou da linha [P, R] e
• o sinal de i + j-1 implica a lateral de T.

Os outros significados geometria de i e j (não relacionadas com esta solução) são os seguintes:

• i , j são os escalares para T em um novo sistema de coordenadas em que v, u são os novos eixos e Q é a nova origem;
• i , j pode ser visto como força de tração para P, R , respectivamente. Quanto maior i , mais longe T está de R (maior tração de P ).

O valor de i, j pode ser obtido resolvendo as equações:

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

Então, recebemos 2 pontos, A, B no avião:

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

Se A, B estiverem do mesmo lado, isso será verdade:

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

Observe que isso se aplica também à pergunta: A, B estão no mesmo lado do plano [P, Q, R] , no qual:

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

e i + j + k = 1 implica que T está no plano [P, Q, R] e o sinal de i + j + k-1 implica sua lateral. A partir disso, temos:

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

e A, B estão do mesmo lado do plano [P, Q, R] se

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