[Linha Poligonal]Calcular intersecção numa linha poligonal

[guisaulo]

Pessoal é o seguinte..
Estou fazendo um trabalho de programação que pede o seguinte:

Uma linha poligonal é representada por um sequencia de 2 a 100 vértices (x,y) ao longo da linha.
É preciso fazer um algoritmo que verifica se um linha poligonal é simples (sem intersecção) ou não simples (com intersecção).

São dados as seguintes informações:
Linha 1: Vértices: (2,9), (8,1.5);
Linha 2: Vértices: (-3,-1), (2,3), (5,4), (9,8);
Linha 3: Vértices: (-2,8),(1,5), (2,8), (-2,6)



Porém, pra fazer o algoritmo preciso de alguma fórmula que calcule a intersecção em uma linha poligonal.
Mas o trabalho só dá as coordenadas dos vértices, que dificultou muito...



É isso, qualquer ajuda é bem vinda.

[Russman]

Pensei em calcular analiticamente as retas que ligam dois pontos distintos. Faça isto para todos. Se houver pontos em comum então as linhas se intersectam. Do contrário, não.

Parece meio trabalhoso. Mas foi o que me veio a mente agora.