Trova i punti di intersezione di tutti i segmenti di linea

Question

Dato un elenco di segmenti di linea, il modo più semplice per trovare i punti di intersezione consiste nel scorrere l'elenco dei segmenti di linea, controllare se si intersecano e registrare il punto di intersezione.

Ma il tempo di esecuzione di questo metodo è O(n^2), che è molto inefficiente. C'è qualche altro algoritmo che potrebbe accelerare questo processo?

Answer 1

Il Bentley-Ottmann Algorithm può essere quello che stai cercando.