Trova tutte le intersezioni dei segmenti di linea

ordina le linee con la X del punto più a sinistra

quindi per ogni riga guarda le righe successive e controlla ognuna di esse finché la x del loro punto più a sinistra è più a destra del punto più a destra della linea corrente

questo sarà n*log n best case (per l'ordinamento) ma degenererà in naive n ^ 2 in set di dati non corretti

Prendiamo un set leggermente diverso, uno con un'intersezione.

[3, 7, 13, 4, 11]

Questogeneral'insiemedilineedi:

{3,7}{7,13}{7,13}{13,4}{13,4}{4,11}{4,11}{11,3}

Assumiamounafunzionepreesistentebooleanintersect(x1,y1,x2,y2)(lamatematicaperquestopuòesseretrovatasu wikipedia , o varie domande di overflow dello stack - si noti che si desidera l'intersezione della riga segmento piuttosto che una generica intersezione della linea).

Prendiamo anche il set di linee e li ordiniamo in base al valore X più a sinistra e quindi al valore X più a destra ( {4,11} {11,3} ordina prima di {4,11}, {13,4} ).

{3,7}  {7,13}
{4,11} {11,3}
{4,11} {13,4}
{7,13} {13,4}

Ora, aggiungendo riga per riga a una coda in ordine ordinato.

Ogni volta che una riga deve essere aggiunta alla coda, controllare le intersezioni con tutte le linee attualmente in coda.

queue: empty
test:  none
add:   {3,7}  {7,13}
----
queue: (1) {3,7}  {7,13}
test:  1: intersects
add:   {4,11} {11,3}
---
queue: (1) {3,7}  {7,13}
       (2) {4,11} {11,3}
test:  1: intersects
       2: does not intersect
add:   {4,11} {13,4}

Inoltre, prima di eseguire i test, se il valore X più a sinistra è uguale o maggiore del valore X più a destra del primo elemento nella coda, rimuovi l'elemento dalla coda.

queue: (1) {3,7}  {7,13}
       (2) {4,11} {11,3}
       (3) {4,11} {13,4}

{7,13} >= {7,13} - drop #1

queue: (2) {4,11} {11,3}
       (3) {4,11} {13,4}

test:  2: does not intersect
       3: does not intersect
add:   {7,13} {13,4}

Questo sta implementando un algoritmo della linea di spazzamento che riguarda solo se stesso con i segmenti di linea che potrebbero intersecarsi con l'elenco di segmenti di linea. Si noti la sezione Applicazioni che menziona Shamos e Hoey con un algoritmo per identificare le intersezioni dei segmenti di linea su un piano (esattamente questo problema). Lo pseudo codice completo è descritto in Intersezioni di un insieme di segmenti . Puoi vedere il codice per questo su CodeReview.SE - È questa implementazione di Shamos-Hoey Algorithm OK? e Stack Overflow - Implementazione di Hoey Shamos algoritmo con C # . Un articolo sull'università di Tufts Intersezione del segmento di linea usando un algoritmo della linea di sweep va in questa e spiega la complessità e alcune altre applicazioni.

Si noti che le strutture qui possono essere semplificate utilizzando la propria lista ordinata. La coda è una visualizzazione utile, ma la lista ordinata può essere utilizzata mantenendo due indici che identificano la finestra dei segmenti di linea da testare. Invece di aggiungere un elemento alla coda, la parte alta del frame viene incrementata. Invece di rimuovere un elemento dalla coda, l'estremità inferiore del frame viene incrementata.

Crea una griglia, mappa tutte le linee sulla griglia. Per ogni cella che contiene più di una linea, convalida l'intersezione.

Ha un'efficienza O (CN), dove C dipende dalle dimensioni della griglia.