Liniensegment Behälter für schnelle Ray Kreuzung? (2D)

Question

Ich habe einen Strahl, ich brauche das nächste Liniensegment zu finden, die er trifft. Ich denke, es ist möglich, dies in O tun (log n) Zeit, wenn ich die Liniensegmente zuerst sortieren, aber ich kann mich nicht erinnern, wie sie zu sortieren ... Ich denke, eine Art Baum am besten funktionieren würde, aber wie kann ich sortieren sie sowohl Anfangs- und Endpunkt? Ich würde auch schnell Einfügungen in diese Datenstruktur möglichst mag.

Es gibt eine Menge Code für einen Strahl gegen ein Liniensegment, aber ich brauche etwas für einen Strahl vs viele Liniensegmente ... Ich weiß nicht, welche Begriffe Google.

Ein Link zu einem entsprechenden Artikel ist gut, C ++ Code ist noch besser. Vielen Dank! :)

PS: Die Liniensegmente sind eigentlich die Kanten eines nicht-selbstschneidendes Polygon, in CCW Reihenfolge sortiert ... aber ich denke, es gibt einige Vorteil sein kann, sie auf eine andere Art und Weise zum Sortieren

Das ist alles 2D.

---

Am zweiten Gedanken, ich bin nicht ganz sicher, dass diese ist möglich. Irgendeine Art von räumlichen Aufteilung könnte helfen, aber sonst habe ich nicht von irgendeiner Weise denken kann, die Zeilen zu sortieren, so dass sie mit einem beliebigen Strahl verglichen werden könnten.

Answer 1

Sie könnten eine Begrenzungsbox des Polygons nehmen (min-max x, y-Koordinaten) und ein Gitter in der Box bauen. Dann wird für jede Zelle, denken Sie daran, alle Linien, die die Zelle kreuzen.

ein intesection wie diese finden:

• Finden Sie heraus, welche Zelle der Strahl trifft zuerst (O (1))
• Verwenden Grid Traversierungsalgorithmus zu "zeichnen", einen Strahl durch das Gitter . Wenn Sie nicht leere Zelle treffen, überprüfen Sie alle seine Linien, prüfen Sie, ob Kreuzung innerhalb der Zelle ist und die nächste Kreuzung holen. Wenn alle Kreuzungen außerhalb der Zelle sind, fortsetzen (dies ist O (Rasterlänge)).

Sie können auch die Gitter hierarchische machen (dh Quadtree - a. Baum Sie fragten nach), und gehen sie mit dem gleichen Algorithmus. Diese in Raytracing in 3D getan wird und die Zeitkomplexität O (sqrt ( N)).

---

Oder verwenden Sie den Ansatz, den ich in meinem Raytracer tat:

• Erstellen Sie eine Quadtree die Linien (Gebäude Quadtree enthält, wird in der desribed Artikel) - Sie Split Knoten (= Flächen), wenn sie zu viele Objekte in vier Unterknoten (Teilbereiche)
enthalten

• Sammeln alle Blattknoten des Quadtree, die von dem Strahl getroffen werden:

  Berechne ray-Rechteck Kreuzung (nicht schwer) für die Wurzel. Wenn die Wurzel durch den Strahl getroffen wird, gehen mit ihren Kindern rekursiv.

Das kühle daran ist, dass, wenn ein Baumknoten ist nicht Hit, du hast Verarbeitung ganzer Teilbaum übersprungen (möglicherweise ein großer rechteckiger Bereich).

Am Ende ist dies gleichbedeutend mit dem Gitter zu durchqueren - Sie die kleinsten Zellen auf dem Strahl den Weg sammeln, und testen Sie dann alle Objekte in ihnen für Kreuzung. Sie müssen nur alle von ihnen testen und die nächste Kreuzung holen (so Sie alle Linien auf ray Pfad erkunden).

Das ist O (sqrt (N)).

Im Raster-Traversal, wenn Sie eine Kreuzung finden, können Sie aufhören zu suchen. Um dies zu erreichen mit Quadtree Traversal, würden Sie die Kinder in der richtigen Reihenfolge seach müssen - entweder sortieren Sie die 4 rect Kreuzungen durch Abstand oder geschickt durchqueren die 4-Zellen-Gitter (ein wir sind wieder zu Traversal)

.

Dies ist nur ein anderer Ansatz, vergleichsweise gleiche schwierig zu implementieren denke ich, und funktioniert gut (ich es auf reale Daten getestet - O (sqrt (N))). Auch hier würde man nur von diesem Ansatz profitieren, wenn Sie mindestens ein paar Zeilen haben, wenn das Polygon 10 Kanten im Vergleich der Nutzen muss nur alle von ihnen zu testen wäre wenig denke ich.

Answer 2

Suchen Sie Scanline / Aktiv-Edge-Tabelle basierte Methoden? Sie können an dem Wikipedia-Eintrag einen Blick für Scanline Rendering oder die Graphics Gems Verzeichnis für die Algorithmen (meist C, aber einige C ++ Code als auch) .

Answer 3

Beachten Sie, dass Sortieranlage ein O (n log n) Betrieb am besten. Sie können besser dran, die jeweils individuell nur überprüfen.

Answer 4

Wie sind Sie sicher, dass Sie einen von ihnen getroffen werden? Wenn sie Linien sind, ist es unwahrscheinlich.

Wenn es wirklich ein Polygon (dh planar), die Sie zu testen sind versucht, die übliche Art und Weise diese Art der Sache zu tun ist, zunächst mit der Ebene schneiden, dann diesen Punkt testen (in den 2D-Koordinaten) für innen / außen Polygon.

Vielleicht falsch verstand ich, was Sie eigentlich tun.

Im allgemeinen Beschleunigungs Kreuzungen mit komplexen Zahlen mit räumlichen Aufteilung erfolgt (und dann Techniken wie Abholfach, wenn die Tests teuer sind).

[Update: Ich falsch verstehe die ursprüngliche Absicht] Sie können nach wie vor verwenden (2d) räumliche Aufteilung, aber der Aufwand nicht wert sein. Individuelle Test sind billig, wenn Ihr Polys nicht kompliziert sind, kann es günstiger sein, nur sie zu gehen. Hart von Beschreibung zu sagen.

Answer 5

Stellen Sie

Zur Klarstellung ist das richtig?

• Sie haben einen dynamischen Satz von Liniensegmenten L .
• Abfrage: angegeben jede (x, y) und und jede Richtung des Strahls von diesem Punkt mögen Sie die nächste Zeile in L bestimmen, (falls vorhanden)?

So Punkt (x, y) fix ist nicht wahr? (Es könnte jeder Punkt sein, und jede Richtung?)