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

StackOverflow https://stackoverflow.com/questions/1560492

  •  21-09-2019
  •  | 
  •  

Pergunta

Eu tenho um conjunto de pontos. Eu quero separá -los em 2 conjuntos distintos. Para fazer isso, eu escolho dois pontos (uma e b) e desenhe uma linha imaginária entre eles. Agora, quero ter todos os pontos que são deixados nesta linha em um conjunto e aqueles que estão diretamente a partir desta linha no outro conjunto.

Como posso dizer para qualquer ponto z Seja na esquerda ou no conjunto direito? Eu tentei calcular o ângulo entre azb - Os ângulos menores que 180 estão no lado direito, maiores que 180 no lado esquerdo - mas, devido à definição de 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)?

Foi útil?

Solução

Use o sinal do determinante dos vetores (AB,AM), Onde M(X,Y) é o ponto de consulta:

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

Isso é 0 na linha, e +1 de um lado, -1 por outro lado.

Outras dicas

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 uma = ponto de linha 1; b = ponto de linha 2; c = aponte 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 do 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ê o avião, a orientação é diferente da minha).

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

Implementei isso em Java e fiz 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 passa, 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));
}

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

  • Se x> da linha de Point, o ponto está à direita da linha.
  • Se x <linha de ponto, o ponto está à esquerda da linha.
  • Se x == da linha do ponto, 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 usando a forma de inclinação de ponto: y - y1 = m*(x-x1) + y1. Por causa da minha explicação, simplifique-a para a forma de interceptação de inclinação (não é necessário no seu algoritmo): y = mx+b.

Agora conecte (x3, y3) por x e y. Aqui estão alguns pseudocódigos 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

Basicamente, acho que existe uma solução que é muito mais fácil e direta, para qualquer polígono, digamos que consistem em quatro vértices (p1, p2, p3, p4), encontre os dois vértices extremos opostos no polígono, em outro Palavras, encontre o vértice mais superior esquerdo (digamos P1) e o vértice oposto que está localizado no máximo direito (digamos). Portanto, dado o seu 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 e cy> p1y ==> significa que c é menor e à direita de p1 a seguir se cx <p2x e cy <p2y ==> significa que c é superior e à esquerda de p4

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

Obrigado :)

Supondo que os pontos sejam (ax, ay) (bx, por) 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 formado pelos pontos A e B e terá um sinal diferente, dependendo do lado. Qual lado isso depende da orientação das suas coordenadas (x, y), mas você pode conectar valores de teste para A, B e C nessa fórmula para determinar se os valores negativos estão à esquerda ou à direita.

@Resposta de 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 produto cruzado, escrito 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

Ou seja, 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! Pedidos importantes Ao dar 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 é por causa deste trecho de código:

(sort line)

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

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

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 (no sentido anti -horário), o ponto será para a "esquerda" da linha, mas se o torque for negativo, o ponto é o "direito" da linha.

Portanto, se o vetor de força é igual ao período dos dois pontos que definem a linha 

fx = x_2 - x_1
fy = y_2 - y_1

Você testa o lado de um ponto (px,py) com 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

Uma maneira alternativa de obter uma sensação de soluções fornecidas pelos Netters é entender um pouco de implicações de geometria.

Deixar PQR= [P, q, r] são pontos que formam um plano que é dividido em 2 lados por linha P, R. Devemos descobrir se dois pontos em PQR O plano, a, b, está do mesmo lado.

Qualquer ponto T No plano PQR, pode ser representado com 2 vetores: v = PQ e você = Rq, como:

T '= tq = eu * V + j * você

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

No geral,

  • i+j é uma medida de quão longe T está longe de Q ou linha [P, R, e
  • o sinal de I+J-1 Implica a liderança de T.

Os outros significados de geometria de eu e j (não relacionados a esta solução) estão:

  • eu,j são os escalares para t em um novo sistema de coordenadas onde v, u são os novos eixos e Q é a nova origem;
  • eu, j pode ser visto como força de tração por P, r, respectivamente. O maior eu, quanto mais t está longe de R (atração maior de P).

O valor de eu 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: Estão a, b do mesmo lado do plano [p, q, r, no qual:

T = eu * 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 liderança. 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)

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top