Algoritmo per trovare segmenti di linea sovrapposti

Question

n4------------------n3--------------------n2--n1
|                    |                    |    |
|                    |                    | P1 |
|                    |                    |    |
|                    |                    n6--n5
|                    |                    |
|              n11--n10                   |
n17      P4     |    |         P2         |
|               | P3 |                    n7
|              n12---n9                   |
|               |                         n8
|               |                         |
n16------------n15---------n14------------n13

Nell'arte ASCII sopra, ci sono quattro poligoni (P1, P2, P3, P4) con segmenti di linea esattamente sovrapposti. Ad esempio, il poligono P2 (formato da segmenti di linea tra i nodi n3, 10, 9, 12, 15, 14, 13, 8, 7, 6 e 2) e P1 (n1, 2, 5 e 6) si sovrappongono alla segmento di linea tra n2 e n6.

Qual è il modo più veloce per trovare segmenti di linea che si sovrappongono esattamente?

Answer 1

Se ogni forma è un elenco di spigoli, allora:

initialize map<edge, list of shapes> map
for each Shape s
  for each Edge e in s
    list l = map.get(e)
    if(l == null) 
      l = new list()
    l.add(s)
    map.put(e, l)

for each <edge, list> in map.entries
  if(list.size > 1)
    do something with this common edge

è la sua O (bordi) e non farai meglio di così. questa soluzione potrebbe non essere soddisfacente a seconda di ciò che si desidera fare in particolare.

Answer 2

Dati N segmenti di linea, nel caso peggiore possono esserci intersezioni O (n ^ 2). Basti pensare al caso in cui hai N poligoni in cui ogni poligono condivide lo stesso bordo. A meno che non vi sia un ulteriore vincolo per impedire che si verifichi questa situazione (che hai omesso di aggiungere), l'algoritmo migliore che puoi trovare sarà O (N ^ 2) nel peggiore dei casi, poiché semplicemente elencare le intersezioni è O (N ^ 2).

In pratica, gli algoritmi più efficienti nella geometria computazionale per trovare intersezioni di segmenti di linea sono algoritmi di sweep line. Il loro peggior tempo di esecuzione per trovare tutte le intersezioni è O (k log n) dove k è il numero di intersezioni (questo può essere N ^ 2, tuttavia raramente lo è.)

Puoi trovare una descrizione esattamente dell'algoritmo di cui hai bisogno in Introduzione agli algoritmi di Thomas H Cormen nella sezione sulla geometria computazionale.

Answer 3

L'algoritmo di twolfe18 sembra buono. Tuttavia, potrebbe esserci un'ulteriore complicazione se i bordi corrispondenti non sono descritti in modo identico. Nel tuo esempio, P1 e P2 condividono entrambi il bordo n2-n6. Ma il bordo di P2 potrebbe essere descritto invece dal segmento n2-n7 (se n2-n6 e n6-n7 sono colinear). Sarà quindi necessario un metodo di hashing più complicato per determinare se due bordi si sovrappongono. Puoi stabilire se due bordi si sovrappongono mappando i segmenti su linee, osservando la linea in una tabella hash, quindi verificando se due segmenti su una linea si intersecano usando un albero intervallo nello spazio dei parametri sulla linea.