Algorithmus zu finden Overlapping Liniensegmente

Question

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

In der obigen ASCII-Art gibt es vier Polygone (P1, P2, P3, P4) mit genau überlappenden Liniensegmente. Zum Beispiel Polygon P2 (durch Liniensegmente zwischen den Knoten n3 gebildet, 10, 9, 12, 15, 14, 13, 8, 7, 6 und 2) und P1 (n1, 2, 5 und 6) überlappen bei der Liniensegment zwischen n2 und n6.

Was ist der schnellste Weg Liniensegmente zu finden, die genau überlappen?

Answer 1

Wenn jede Form eine Liste von Kanten dann:

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

seine O (Kanten), und die nicht besser als das tun wird. diese Lösung möglicherweise nicht zufriedenstellend sein, je nachdem, was Sie wollen, obwohl speziell zu tun.

Answer 2

Da N Zeilensegmente, im schlimmsten Fall kann es O (n ^ 2) Kreuzungen sein. Man denke nur an den Fall, dass Sie N Polygone haben, wo jedes Polygon die gleiche Kante teilt. Es sei denn, es ist eine zusätzliche Einschränkung, diese Situation zu verhindern (die Sie hinzufügen weggelassen), dann der beste Algorithmus Sie können sich mit wird O (N ^ 2) im schlimmsten Fall sein, da einfach die Kreuzungen Auflistung ist O (N ^ 2).

In der Praxis sind die effizientesten Algorithmen in Computational Geometry für Kreuzungen von Liniensegmenten zu finden sind Sweep Linie Algorithmen. Ihr schlimmster Fall Zeit, um alle Kreuzungen finden lief O (k log n), wobei k die Anzahl der interesections (dies kann sein N ^ 2, aber es selten ist).

Sie können eine Beschreibung genau das finden, den Algorithmus Sie in Einführung in den Algorithmen von Thomas H Cormen im Abschnitt über die algorithmische Geometrie.

Answer 3

twolfe18 Algorithmus sieht gut aus. Es kann eine zusätzliche Komplikation jedoch sein, wenn fluchteten Kanten sind nicht identisch beschrieben. In Ihrem Beispiel P1 und P2 beide teilen die n2-n6 Rand. Aber P2 Rand könnte stattdessen durch das Segment n2-n7 beschrieben werden (wenn n2-N6 und N6-N7 kollinear sind). Sie werden dann ein komplizierteres Hashing-Verfahren benötigen, um zu bestimmen, ob zwei Kanten überlappen. Sie können feststellen, ob zwei Kanten durch Mapping Segmente auf Linien überlappen, die Linie in einer Hash-Tabelle nachschlagen, dann testen, ob zwei Segmente auf einer Linie ein Intervall Baum im Parameterraum auf der Linie schneidet verwendet wird.