Paralelogramo contém Ponto

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

Pergunta

O caminho é o mais rápido de decidir se um ponto está dentro de um paralelogramo / losango?

Foi útil?

Solução

Oi novamente e obrigado por todas as suas respostas. Nesse meio tempo eu mesmo tenho chegar a algo que eu acho que seria bastante rápida:

Imagine que tem um paralelogramo que é atravessado por PQ e PR, onde PQ e PR são vectores (P, Q e R são cantos). Além disso, temos o ponto queremos verificar chamado A.

Sabemos que a Vector PA pode ser dividida em dois vetores paralelo ao PQ e PR: 

PA=n*PQ+m*PR

Agora sabemos que n e m deve estar no intervalo [0; 1], resolvemos n e m: 

n = -det(PA, PQ)/det(PQ, PR)
m = det(PA, PR)/det(PQ, PR)

Onde det (PA, PQ) é o determinante dos vetores PA e PQ: 

det(PA, PQ) = PA.x*PQ.y-PQ.x*PA.y

Se o ponto A é dentro do paralelogramo, em seguida, 0 <= n <= 1 e 0 <= m <= 1, isto dá-nos o pseudocódigo: 

var d:Number = det(PQ, PR);
if (0 <= -det(PA, PQ)/d <= 1 && 0 <= det(PA, PR)/d <= 1)
{
    //inside
}
else
{
    //outside
}

Outras dicas

Imagine um raio que emana do seu ponto em uma direção. Se aquele raio cruza as linhas de sua forma um número ímpar de vezes, é dentro da forma. Se ele cruza um número par de vezes, é fora da forma.

Assim, no seu programa que você acabou de criar uma linha invisível e ver quantas vezes ele cruza. Actionscript provavelmente foi construído em função de fazer isso, eu imagino.

Agora, se você tem uma tonelada de objetos eo ponto só pode ser em um, você pode acelerar as coisas usando um Binary Space Partition para armazenar as localizações dos objetos. Dessa forma, você não tem que comparar seu ponto com cada objeto, apenas aqueles perto dele.

Veja a minha resposta para este questão, que é muito semelhante. Não, eu dou o que eu acho que é um teste muito fácil no caso em que o paralelogramo tem um dos seus cantos em (0,0) porque torna a explicação mais fácil de se olhar, mas não é muito difícil modificá-lo para o trabalho em geral.

EDIT: Uma vez que o proprietário pergunta é familiarizado com vetores, vou basicamente reescrever a minha resposta nessa língua. Suponhamos que o paralelogramo é gerado por vectores PQ e PR, onde P, Q, e R são cantos. O símbolo * vai denotar produto escalar. Escolher um ponto tal que q PQ é perpendicular ao Pq (isto é Pq*PQ=0) e PR*Pq>0 (por exemplo, é possível obter q por rotação em torno Q P por 90 graus). Também escolher um r ponto tal que PR*Pr=0 e PQ*Pr>0. Em seguida, um A ponto é no interior se e somente se (0 < Pr*PA < Pr*PQ) && (0 < Pq*PA < Pq*PR).

Este papel descreve um método para determinar onde um raio e Intersect quadrilátero. Ele pode ser simplificada, o quadrilátero é um paralelogramo.

Se você tem um paralelogramo com lados adjacentes descrita por vetores AB e AC . Qualquer ponto no plano do paralelogramo pode ser descrito pelo seguinte vector 

T(a, b) = A + a * AB + b * AC

Qualquer ray pode ser descrito como uma origem O e direção D 

R(t) = O + t * D

A interseção da 2 é quando T(a, b) == R(t) 

O + t * D = A + a * AB + b * AC

Resolva isso para a e b e verificar que ambos estão entre 0 e 1. Veja o pseudocódigo no final do papel para saber como implementar isso.

A equação padrão de uma linha é dado como ax + bx + c = 0 .. mas, curiosamente, se você tirar esse machado expressão + bx + c, e avaliar pontos x, y dado o a, b, c para o seu em particular linha, você vai achar que as partições de expressão do avião em duas metades, uma metade onde a expressão é maior do que zero, a outra metade onde é menos.

Agora, se você tomar os quatro pontos de seu paralelogramo, e calcular os a, b, coeficientes c para cada linha que compõe um lado do paralelogramo, você pode avaliar cada expressão para o x, y em questão e encontrar para que os lados de cada linha que está em ponto. O dentro do paralelogramo será uma lógica AND dos lados particulares.

ou seja., Uma vez que você tem a a, b, c é para cada uma das quatro linhas, você pode fazer um teste de algo como 

if ( ((a1*x+b1*y+c1)>0) && ((a2*x+b2*y+c2)<0) && 
        ((a3*x+b3*y+c3)<0) && ((a4*x+b4*y+c4)>0) {
    // it's in!
}

.. o truque único remanescente é que você tem que determinar a 'polaridade' de cada teste do sinal, ou seja, maior ou menor que zero. A maneira fácil de fazer isso é avaliar 0,0, e ver se isso está no lado que você quer, o que equivale a dizer que o sinal de 'c' diz-lhe qual o caminho a teste.

Na verdade, é uma espécie de uma forma força bruta para fazê-lo, mas pode ser estendida a obra para qualquer polígono convexo .. ou, remover um ponto e ele funciona para triângulos, também.

A minha primeira observação sobre este problema é que o um retângulo (alinhado com os eixos) é um caso degenerado simples. Se dois cantos desse retângulo são: (x1, y1) e (x2, y2), então você simplesmente teste, dado um ponto (x3, y3), que min (x1, x2)

Esta também pode ser uma otimização útil. Se encontrarmos-eixo alinhado retângulo delimitador da nossa paralelogramo então podemos começar com um teste rápido de qualquer ponto contra isso.

Se os nossos paralelos têm diferente de zero inclinação então calcular as interseções de eixos de nossas linhas delimitadoras e a intersecção das linhas que passam pelo ponto em questão nessas encostas. Se ambos cruzamentos do nosso ponto (definido por ambas as encostas) situa-se entre os nossos as interseções de nossas linhas delimitadoras, em seguida, em que estamos. Se qualquer um isso está fora desses intervalos, em seguida, nós não somos.

Eu não tenho tempo para código se um exemplo, mas computação estas pistas e cruzamentos são de primeira álgebra ano.

[Addenda]

Eu vejo agora que o primeiro post (sobre ray a partir do ponto a ser testado e se estende ao longo de qualquer inclinação arbitrário) é uma referência para a solução geral para este problema para qualquer polígono planar fechada ... ou, de fato, para qualquer curva plana fechada. Ele também pode ser alargado a três dimensões para superfícies fechadas.

Há, no entanto, uma ressalva que se aplicaria a paralelogramos nem rhomboids. No caso de um polígono côncavo (ou algumas outras curvas) se o raio atinge qualquer apex (canto), então é possível que o teste retornar um número par de passagens de "linha". Em outras palavras, qualquer parte da "curva", que é simultaneamente incluída em vários "lados" do polígono poderia retornar um falso positivo.

Duas soluções deste seria: explicitamente teste para cruzamentos em limites segmento de linha (canto / ápices) ou tratar cada segmento de linha como delimitada em uma extremidade pelo (ponto + epsilon) (para que nossos cálculos não vai encontrar qualquer ponto em comum entre quaisquer dois lados).

A minha ideia de encontrar um retângulo delimitador ainda é um teste rápido útil e se estende em geral a todos os polígonos. Nós encontramos o min () e max () x para encontrar os lados esquerdo e direito delimitadoras e o min (max) e e () y para encontrar a parte inferior e superior limites. Isso também pode ser estendido para três dimensões ... e um amigo me diz que as bibliotecas gráficas padrão usar esta extensivamente para detecção de colisão em mais realidade e MMORPGs virtual, etc. Quando as colisões encontrar em caixas delimitadoras, em seguida, eles fazem mais cálculos de grão fino sobre os polígonos que estão nele contidas.

Se o paralelogramo é convexa (e dada a definição de paralelogramo deve ser xD), então qualquer algoritmo para testar se está em seus limites devem fazer, você pode melhorar a eficiência desenrolar o loop, porque você sabe que existem apenas 4 vértices , por exemplo.

Aqui está um algoritmo simples que testa o ponto de estar no mesmo lado de todos os segmentos, com base na regra da mão direita do produto vectorial (você pode otimizá-lo também, substituindo a divisão para normalizar o vetor com um teste simples sinal ):

Como testar se um ponto está dentro de um polígono convexo em 2D inteiro coordenadas?

Outra opção, se você estiver indo para fazer muitas comparações contra o mesmo paralelogramo é normalizar-lo para um quadrado, obter a matriz que faz a transformação e cada vez que você começa um ponto para teste, multiplicá-lo pela matriz e, em seguida, verifique se o ponto transformado é dentro do quadrado normalizado (que deve ser muito mais fácil).

  1. Get contorno do seu polígono
  2. Verifique se as mentiras pontuais no countour

dist1 = cv2.pointPolygonTest(contours[0], (50, 70), True)

retornos dist um dos três seguintes:

  • valor positivo se o ponto está dentro do contorno
  • valor negativo se o ponto está fora do contorno
  • Zero se o ponto é no contorno

Como verificar se o ponto é colocado dentro contorno?

A coordenada y é mais simples, assim que começar com isso. Se a coordenada y do ponto situa-se entre a parte superior e inferior da forma, ir para a coordenada x. Calcular a coordenada X dos lados esquerdo e direito da forma na coordenada y do ponto, e verificar se a coordenada x da questão é entre eles.

Editar:

Dadas as quatro coordenadas do canto superior esquerdo, superior direito, inferior direito e cantos inferior esquerdo: 

if (y >= y1 && y <= y3) {
   var k = (x4 - x1) / (y4 - y1);
   var m = x1 - k * y1;
   if (x >= k * y + m) {
     k = (x3 - x2) / (y3 - y2);
     m = x2 - k * y2;
     if (x <= k * y + m) {
       // inside
     }
   }
}
Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top