Intersecção entre dois segmentos

Aqui o problema consiste em dizer se um segmento de reta intercepta outro segmento. Para este problema, poderíamos resolver da maneira mais tradicional, recorrendo a geometria analítica e trabalhando com as equações das retas. Porém, temos a nossa disposição a primitiva Esquerda-Direita, que diz se um ponto está a esquerda de um dado vetor. Então, podemos apresentar uma solução mais elegante que dispensa muitos cálculos. Isto ocorre porque precisamos saber apenas se os segmentos se interceptam e não onde eles se interceptam.

Dado o segmento AB e o segmento CD, existe intersecção entre AB e CD se A estiver de um lado de CD e B do outro, e C estiver de um lado de AB e D do outro. Isso é equivalente a:

XOR(esquerda(C,D,A), esquerda(C,D,B)) AND XOR(esquerda(A,B,C), esquerda(A,B,D)).

Voltar

Para saber mais

Consulte a seguinte bibliografia:

  1. T.H. Cormen, C.E. Leiserson, R.L. Rivest - Introduction to Algorithms
    MIT Press, Cambridge, Mass. (1990).
  2. J. O'Rourke - Computational Geometry in C
    Cambridge University Press (1993).

Last modified: Fri Nov 26 17:15:52 EDT 1999