Algoritmo di Bentley-Ottmann per due gruppi di segmenti di segmenti

Question

L'algoritmo di Bentley-Ottmann viene utilizzato per il calcolo dell'intersezione di segmenti di linea.

Tuttavia, anziché trovare i punti intersecanti di tutte le linee tra loro, voglio trovare i punti intersecanti tra due gruppi di linee. Ciò significa che per ogni riga nel gruppo di linee A, desidero conoscere i punti di intersezione tra quelle linee e le righe nel gruppo B.

Esiste comunque la possibilità di estendere il Bentley-Ottmann algorithm per questo? Ho già implementato l'algoritmo Bentley-Ottmann esistente (in the library of CGAL) e non sono propenso a modificarlo. Tuttavia, sono desideroso di trovare modi per riutilizzarlo ed estenderlo.

Modifica: qualsiasi altro algoritmo (non necessariamente basato su Bentley- Ottmann) è il benvenuto. Sarebbe meglio se quegli algoritmi fossero già implementati nella libreria esistente.

Answer 1

È possibile trovare tutte le intersezioni tra tutte le linee in A+B, quindi rimuovere le intersezioni tra le linee nello stesso set. Non stai aumentando la complessità di molto e questo ti permette di usare la funzione di libreria CGAL non modificata con solo una semplice funzione wrapper.

Answer 2

Dove Bentley-Ottman mantiene un albero di segmenti di linea ordinati in base alla loro posizione verticale corrente, non è possibile mantenere due alberi, uno ciascuno per i gruppi A e B? Quindi, dove l'algoritmo originale controlla i vicini sopra e sotto il punto corrente, dovresti controllare il vicino A vicino al lato B vicino e viceversa.

Questo è basato su una rapida panoramica dell'articolo di Wikipedia; Non ho scritto molto codice geometrico negli ultimi dieci anni.

Answer 3

Aggiunta di questa risposta per completezza, anche se potrebbe non essere il metodo più efficiente per 2 dimensioni.

Nella grafica 3D è comune a 2 alberi KD, che possono essere utilizzati per rilevare tutti i nodi sovrapposti (può essere utilizzato per operazioni booleane sulla geometria).

Esempio di lavoro (codice C). https://developer.blender.org/diffusion/B/browse/master/source/blender/blenlib/intern/BLI_kdopbvh.c;3b4a8f1cfa7339f3db9ddd4a7974b8cc30d7ff0b $ 1089

Se ci sono molti piccoli segmenti (come il percorso di una linea disegnata a mano), questo sarà ragionevolmente efficiente. Tuttavia se ci sono molti bordi lunghi (si pensi ai pennarelli) ... questo si comporta male e si vorrebbe dividere i nodi foglia nell'albero BVH per ottenere prestazioni migliori. Tuttavia, se questo è il caso, è probabilmente meglio usare un metodo diverso come suggerito in altre risposte.

Answer 4

Sì, l'algoritmo di Bentley-Ottmann può essere esteso per farlo, insieme ad altri metodi.

In letteratura, l'attività descritta lungo le linee di che segnala le intersezioni tra le linee rosse e blu.

Ecco una carta che estende lo spazzamento B-O a un algoritmo ottimale. http://www.cs.unc.edu/~snoeyink/demos/rbseg/jcdcg25.pdf

Non sarei d'accordo con l'affermazione di @ Marcog sulla complessità. La carta collegata sostiene il tempo ottimale di O (n log (n + k)), se filtri le intersezioni, dovrai eseguire uno sweep B-O su tutte le linee, e sarebbe ((n + k) log n).

Ci sono altri algoritmi simili che non possono richiedere complesse strutture di dati-http://www.cs.swarthmore.edu/~adanner/cs97/s08/pdf/palazzi93counting.pdf

Per meno bordi e meno intersezioni tra bordi, la soluzione in risposta forza lavoro @ di marcog bene. (Ecco un esempio da CGAL http://doc.cgal.org/latest/Arrangement_on_surface_2/Arrangement_on_surface_2_2consolidated_curve_data_8cpp-example.html).

Se è necessario elaborare poligoni complessi (dati GIS ecc.) O è necessario un algoritmo generale, questa classe di algoritmi potrebbe valerne la pena.