Intersecção linha-linha - Line–line intersection

A interseção de linhas.

Na geometria euclidiana , a interseção de uma linha e uma linha pode ser o conjunto vazio , um ponto ou uma linha. Distinguir esses casos e encontrar o ponto de intersecção tem uso, por exemplo, em computação gráfica , planejamento de movimento e detecção de colisão .

Na geometria euclidiana tridimensional , se duas linhas não estão no mesmo plano, elas são chamadas de linhas oblíquas e não têm ponto de intersecção. Se eles estão no mesmo plano, há três possibilidades: se eles coincidem (não são linhas distintas), eles têm uma infinidade de pontos em comum (ou seja, todos os pontos em qualquer um deles); se forem distintos, mas tiverem a mesma inclinação, são considerados paralelos e não têm pontos em comum; caso contrário, eles têm um único ponto de intersecção.

As características distintivas da geometria não euclidiana são o número e as localizações de possíveis interseções entre duas linhas e o número de linhas possíveis sem interseções (linhas paralelas) com uma determinada linha.

Fórmulas

Uma condição necessária para que duas linhas se cruzem é que elas estejam no mesmo plano - ou seja, não sejam linhas inclinadas. A satisfação dessa condição é equivalente ao tetraedro com vértices em dois dos pontos de uma linha e dois dos pontos da outra linha sendo degenerados no sentido de ter volume zero . Para a forma algébrica dessa condição, consulte Linhas de inclinação § Teste de assimetria .

Dados dois pontos em cada linha

Primeiro consideramos a intersecção de duas linhas e no espaço bidimensional, com a linha sendo definida por dois pontos distintos e , e a linha sendo definida por dois pontos distintos e .

A intersecção da linha e pode ser definida usando determinantes .

Os determinantes podem ser escritos como:

onde o denominador é:

Quando as duas linhas são paralelas ou coincidentes, o denominador é zero. Se as linhas forem quase paralelas, uma solução de computador pode encontrar problemas numéricos ao implementar a solução descrita acima: o reconhecimento dessa condição pode exigir um teste aproximado em uma aplicação prática. Uma abordagem alternativa pode ser girar os segmentos de linha de modo que um deles seja horizontal, de onde a solução da forma paramétrica girada da segunda linha é facilmente obtida. É necessária uma discussão cuidadosa dos casos especiais (linhas paralelas / linhas coincidentes, intervalos sobrepostos / não sobrepostos).

Dados dois pontos em cada segmento de linha

Observe que o ponto de interseção acima é para as linhas infinitamente longas definidas pelos pontos, em vez dos segmentos de linha entre os pontos, e pode produzir um ponto de interseção não contido em nenhum dos dois segmentos de linha. Para encontrar a posição da interseção em relação aos segmentos de linha, podemos definir linhas e em termos de parâmetros de Bézier de primeiro grau :

(onde t e u são números reais). O ponto de intersecção das linhas é encontrado com um dos seguintes valores de t ou u , onde

e

com:

Haverá uma interseção se 0,0 ≤  t  ≤ 1,0 e 0,0 ≤  u  ≤ 1,0. O ponto de interseção cai dentro do primeiro segmento de linha se 0,0 ≤  t  ≤ 1,0, e cai dentro do segundo segmento de linha se 0,0 ≤  u  ≤ 1,0. Essas desigualdades podem ser testadas sem a necessidade de divisão, permitindo a determinação rápida da existência de qualquer interseção de segmento de linha antes de calcular seu ponto exato.

Dadas duas equações de linha

As coordenadas e do ponto de intersecção de duas linhas não verticais podem ser facilmente encontradas usando as seguintes substituições e rearranjos.

Suponha que duas linhas tenham as equações e onde e são as inclinações (gradientes) das linhas e onde e são os interceptos y das linhas. No ponto onde as duas linhas se cruzam (se o fizerem), ambas as coordenadas serão as mesmas, daí a seguinte igualdade:

Podemos reorganizar essa expressão para extrair o valor de ,

e entao,

Para encontrar a coordenada y , tudo o que precisamos fazer é substituir o valor de x em qualquer uma das duas equações de linha, por exemplo, na primeira:

Portanto, o ponto de intersecção é

Observe se a = b então as duas linhas são paralelas . Se cd também, as linhas são diferentes e não há interseção, caso contrário, as duas linhas são idênticas.

Usando coordenadas homogêneas

Usando coordenadas homogêneas , o ponto de interseção de duas linhas implicitamente definidas pode ser determinado com bastante facilidade. Em 2D, cada ponto pode ser definido como uma projeção de um ponto 3D, dado como o triplo ordenado . O mapeamento de coordenadas 3D para 2D é . Podemos converter pontos 2D em coordenadas homogêneas definindo-os como .

Suponha que queremos encontrar a interseção de duas linhas infinitas no espaço bidimensional, definido como e . Podemos representar essas duas linhas em coordenadas de linha como e ,

A interseção de duas linhas é então simplesmente dada por,

Se as linhas não se cruzam.

Mais de duas linhas

A interseção de duas linhas pode ser generalizada para envolver linhas adicionais. A existência e a expressão do problema de interseção de n linhas são as seguintes.

Em duas dimensões

Em duas dimensões, mais de duas linhas quase certamente não se cruzam em um único ponto. Para determinar se eles fazem e, em caso afirmativo, para encontrar o ponto de interseção, escreva a i -ésima equação ( i = 1, ..., n ) como e empilhe essas equações em forma de matriz como

onde a i -ésima linha da matriz n × 2 A é , w é o vetor 2 × 1 ( x, y ) T , e o i- ésimo elemento do vetor coluna b é b i . Se A tem colunas independentes, sua classificação é 2. Então se e somente se a classificação da matriz aumentada [ A | b ] também é 2, existe uma solução da equação da matriz e, portanto, um ponto de interseção das n retas. O ponto de intersecção, se existir, é dado por

onde é o inverso generalizado Moore-Penrose de (o qual tem a forma mostrada porque Um tem posto coluna cheio). Alternativamente, a solução pode ser encontrada resolvendo em conjunto quaisquer duas equações independentes. Mas se a classificação de A for apenas 1, então se a classificação da matriz aumentada for 2, não há solução, mas se sua classificação for 1, todas as linhas coincidem entre si.

Em três dimensões

A abordagem acima pode ser facilmente estendida a três dimensões. Em três ou mais dimensões, mesmo duas linhas quase certamente não se cruzam; pares de linhas não paralelas que não se cruzam são chamados de linhas inclinadas . Mas se existe uma interseção, ela pode ser encontrada, como segue.

Em três dimensões, uma linha é representada pela interseção de dois planos, cada um dos quais tem uma equação da forma. Assim, um conjunto de n linhas pode ser representado por 2 n equações no vetor de coordenadas tridimensional w = ( x , y , z ) T :

onde agora A é 2 n × 3 eb é 2 n × 1. Como antes, há um único ponto de interseção se e somente se A tiver classificação de coluna completa e a matriz aumentada [ A | b ] não, e a interseção única, se existir, é dada por

Pontos mais próximos para distorcer as linhas

Em duas ou mais dimensões, geralmente podemos encontrar um ponto que é mutuamente mais próximo de duas ou mais linhas no sentido de mínimos quadrados .

Em duas dimensões

No caso bidimensional, primeiro, representam linha i como um ponto, , na linha e uma unidade de vetor normal , perpendicular a essa linha. Ou seja, se e são pontos na linha 1, então deixe e deixe

que é o vetor unitário ao longo da linha, girado em 90 graus.

Observe que a distância de um ponto, x à linha, é dada por

E então a distância ao quadrado de um ponto, x , a uma linha é

A soma das distâncias ao quadrado para muitas linhas é a função de custo :

Isso pode ser reorganizado:

Para encontrar o mínimo, diferenciamos em relação ax e definimos o resultado igual ao vetor zero:

tão

e entao

Em mais de duas dimensões

Embora não seja bem definido em mais de duas dimensões, isso pode ser generalizado para qualquer número de dimensões, observando que é simplesmente a matriz (simétrica) com a unidade de todos os valores próprios, exceto por um valor próprio zero na direção ao longo da linha, fornecendo um seminário sobre a distância entre e outro ponto que dá a distância para a linha. Em qualquer número de dimensões, se for um vetor unitário ao longo da i- ésima linha, então

torna-se

onde I é a matriz de identidade, e assim

Derivação geral

Para encontrar o ponto de intersecção de um conjunto de retas, calculamos o ponto com distância mínima a elas. Cada linha é definida por uma origem e um vetor de direção unitária ,. O quadrado da distância de um ponto a uma das linhas é dado a partir de Pitágoras:

Onde: é a projeção de na linha . A soma das distâncias do quadrado para todas as linhas é:

Para minimizar essa expressão, nós a diferenciamos em relação a .

Isso resulta:

Onde está a matriz de identidade. Esta é uma matriz , com solução , onde é o pseudo-inverso de .

Veja também

Referências

  1. ^ "Weisstein, Eric W." Line-Line Intersection. "From MathWorld" . Um recurso da Web da Wolfram . Página visitada em 2008-01-10 .
  2. ^ Antonio, Franklin (1992). "Capítulo IV.6: Intersecção de segmento de linha mais rápida". Em Kirk, David (ed.). Gemas Gráficas III . Academic Press, Inc. pp. 199-202. ISBN 0-12-059756-X.
  3. ^ "Coordenadas homogêneas" . robotics.stanford.edu . Página visitada em 18/08/2015 .
  4. ^ Traa, Johannes. "Intersecção de Linhas de Mínimos Quadrados" (PDF) . Retirado em 30 de agosto de 2018 .

links externos