Esiste un modo efficace per contare il numero di intersezioni tra un determinato insieme di segmenti di linea?

Question

Supponiamo di avere n segmenti di linea in posizione generale. Come posso contare rapidamente, per ciascuno dei miei n segmenti, quanti altri n-1 interseca?

Posso fare questo in modo ingenuo in tempo O (n). Posso trovare tutte le intersezioni usando un algoritmo di linea di sweep abbastanza semplice (Bentley-Ottmann) in O ((n + k) log n) tempo, dove k è il numero di tali intersezioni, e quindi aggregare le intersezioni che ho trovato in un gruppo di conta.

Non ho bisogno di trovare le intersezioni, però; Voglio solo sapere quanti ce ne sono. Non vedo come modificare l'algoritmo della linea di scorrimento per essere più veloce poiché è necessario riordinare due elementi in un albero per ogni intersezione, e non riesco a pensare a nessun'altra tecnica che non soffra dello stesso problema.

Sono anche interessato a sapere come contare quante intersezioni totali ci sono.

Answer 1

Ho difficoltà a credere che si possa fare meglio di Bentley Ottman nel caso generale. Puoi semplificare un po 'il calcolo se non ti interessa dove i segmenti della linea si intersecano, ma non vedo come potresti contare gli incroci senza trovarli.

In sostanza, Bentley Ottman è un modo per semplificare lo spazio di ricerca per le intersezioni. Ci sono altri modi, che potrebbero funzionare per particolari disposizioni di segmenti di linea, ma a meno che non ci sia una relazione geometrica prevedibile tra i tuoi segmenti, non sarai in grado di fare meglio di prima usando un modo intelligente per trovare le intersezioni candidate combinate con un verifica individuale di ciascun candidato.

A meno che il dominio del problema non abbia alcune caratteristiche specifiche che potrebbero fornire una sottostruttura sfruttabile, penso che la soluzione migliore per la velocità sarebbe quella di adattare Bentley Ottman (o un algoritmo di sweeping simile) per l'esecuzione parallela. (Tagliare i segmenti della linea in bande è semplice, anche la determinazione di un insieme ottimale di bande sarebbe interessante). Naturalmente, questo è un esercizio pratico piuttosto che accademico; l'algoritmo parallelo potrebbe finire per fare più lavoro in totale; sfrutta l'hardware per eseguire il lavoro (un fattore costante) meno tempo.