Intersecção
Ponto de interseção de linhas
a1, b1, c1 - coeficientes da primeira linha,
a2, b2, c2 - coeficientes da segunda linha,
x, y - ponto de interseção.
\(x = {-(c1 \cdot b2 - c2 \cdot b1) \over (a1 \cdot b2 - a2 \cdot b1)} \\ y = {-(a1 \ cdot c2 - a2 \cdot c1) \over (a1 \cdot b2 - a2 \cdot b1)} \)
Já sabemos como verificar a interseção de linhas (elas não são paralelas) e encontrar seu ponto de interseção.
Agora vamos aprender como fazer isso com segmentos.
Primeiro, vamos aprender como simplesmente verificar a interseção deles.
Segmentos se cruzam se as extremidades de um estiverem em lados opostos do outro e vice-versa (isso é facilmente verificado pelo produto vetorial). O único caso em que isso não funcionará - os segmentos estão em uma linha reta. Para isso, você precisa verificar a interseção dos chamados. bounding box (caixa delimitadora do segmento) - verifique a interseção da projeção dos segmentos no X e no Y.
eixos.
Agora que sabemos como verificar segmentos de interseção, vamos aprender como encontrar o ponto (ou segmento) de sua interseção:
- se eles não se cruzam, é claro que tal ponto não existe;
- caso contrário, construiremos linhas retas nas quais esses segmentos se encontram.
Se forem paralelos, os segmentos estão na mesma linha e precisamos encontrar o segmento de interseção - do máximo das bordas esquerdas dos segmentos ao mínimo das bordas direitas (o ponto é menor que o outro ponto, se for à esquerda, em caso de igualdade X-coordenadas - se for inferior).
Se as linhas não forem paralelas, encontre o ponto de interseção e retorne-o.