Como saber se um ponto é para o lado direito ou esquerdo de uma linha

Eu tenho um conjunto de pontos. Eu quero separá-los em dois conjuntos distintos. Para fazer isso, escolho dois pontos ( aeb ) e desenho uma linha imaginária entre eles. Agora quero ter todos os pontos que restam dessa linha em um conjunto e aqueles que estão certos nessa linha no outro conjunto.

Como posso dizer para qualquer ponto z se está à esquerda ou no conjunto certo? Eu tentei calcular o ângulo entre azb ângulos menores que 180 estão no lado direito, maior que 180 no lado esquerdo – mas por causa da 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) é o ponto de consulta:

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

É 0 na linha e +1 em um lado, -1 no outro lado.

Tente este código que faz uso de um produto cruzado :

 public bool isLeft(Point a, Point b, Point c){ return ((bX - aX)*(cY - aY) - (bY - aY)*(cX - aX)) > 0; } 

Onde a = ponto de linha 1; b = ponto de linha 2; c = ponto para checar.

Se a fórmula for igual a 0, os pontos sã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 para o outro (e zero para pontos na própria linha).

O vetor (y1 - y2, x2 - x1) é perpendicular à linha e sempre está apontando para a direita (ou sempre apontando para a esquerda, se a orientação do plano for diferente da minha).

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

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 da unidade. Se alguém encontrar um teste de unidade que não passe, por favor me avise.

Código: NOTA: nearlyEqual(double,double) retorna true 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 da 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)); } 

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

  • Se o ponto x x da linha, o ponto está à direita da linha.
  • Se x do ponto
  • Se o ponto x = = x da linha, 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 

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

Em seguida, crie uma equação da linha usando a forma de declive de pontos: y - y1 = m*(x-x1) + y1 . Para o bem da minha explicação, simplifique-a para a forma de interseção de inclinação (não necessária em seu algoritmo): y = mx+b .

Agora conecte (x3, y3) para x e y . Aqui está um pseudocódigo detalhando o que deveria 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 

Basicamente, eu acho que existe uma solução que é muito mais fácil e direta, para qualquer polígono dado, digamos que consiste em quatro vértices (p1, p2, p3, p4), encontrar os dois vértices extremos opostos no polígono, em outro palavras, encontre o vértice mais superior à esquerda (digamos p1) e o vértice oposto que está localizado no canto inferior direito (digamos). Assim, dado o seu ponto de teste C (x, y), agora você tem que fazer dupla checagem entre C e p1 e C e p4:

se cx> p1x AND cy> p1y ==> significa que C é menor e à direita de p1 próximo se cx significa que C é superior e esquerdo de p4

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

Obrigado 🙂

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

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

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

@ 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 quer dizer que o ponto (0, 10) está à esquerda da linha determinada por (-3, -1) e (3, 1).

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

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

Isso é por causa desse trecho de código:

 (sort line) 

Finalmente, como acontece com as outras soluções baseadas em produtos cruzados, essa solução retorna um valor booleano e não fornece um terceiro resultado para colinearidade. Mas vai dar um resultado que faz sentido, por exemplo:

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