Kreisschnitt mit Sweep-Line-Algorithmus

Leider verstehe ich den Sweep-Line-Algorithmus immer noch nicht so gut . Alle Artikel und Lehrbücher zum Thema sind bereits gelesen, das Verständnis ist jedoch noch weit entfernt. Nur um es klarer zu machen, versuche ich so viele Übungen wie möglich zu lösen. Aber wirklich interessante und wichtige Aufgaben sind für mich immer noch eine Herausforderung.

Die folgende Übung habe ich in den Vorlesungsunterlagen von Line Segment Intersection des allmächtigen Jeff Erickson gefunden.

Aufgabe 2. Beschreiben und analysieren Sie einen Sweepline-Algorithmus, um bei Kreisen in der Ebene zu bestimmen, ob sich zwei in überschneiden . Jeder Kreis wird durch seinen Mittelpunkt und seinen Radius spezifiziert, sodass die Eingabe aus drei Arrays und . Stellen Sie sicher, dass Sie die Grundelemente auf niedriger Ebene korrekt implementieren. $n$ $O(n \log n)$ $X[1.. n], Y [1.. n]$ $R[1.. n]$

Versuchen wir, eine komplexe Sache zu vereinfachen. Was wissen wir über die Überschneidung von Kreisen? Welches Analogon kann mit Schnittpunkt von Linien gefunden werden. Zwei Linien können sich kreuzen, wenn sie benachbart sind. Welche Eigenschaft sollten zwei Kreise haben, um sich zu kreuzen? Sei der Abstand zwischen dem Mittelpunkt der Kreise, und Mittelpunkt der Kreise. Betrachten Sie einige Fälle: $d$ $r_{0}$ $r_{1}$

Fall 1: Wenn dann gibt es keine Lösungen, die Kreise sind getrennt. $d > r_{0} + r_{1}$
Fall 2: Wenn dann gibt es keine Lösungen, weil ein Kreis im anderen enthalten ist. $d < |r_{0} - r_{1}|$
Fall 3: Wenn und die Kreise zusammen und es gibt unendlich viele Lösungen. $d = 0$ $r_{0} = r_{1}$

Es sieht also so aus, als wären die Kreuzungsbedingungen bereit. Natürlich kann es sich um falsche Bedingungen handeln. Bitte korrigieren Sie, wenn es so ist.

Algorithmus. Jetzt müssen wir etwas gemeinsam zwischen zwei sich überschneidenden Kreisen finden. Bei einem Schnittpunkt analog zur Linie müssen die Einfügebedingung und die Löschbedingung für die Ereigniswarteschlange vorhanden sein. Angenommen, der Ereignispunkt ist die x-Koordinate des ersten und des letzten Punkts, den die vertikale Sweep-Linie berührt. Beim ersten Punkt fügen wir einen Kreis in den Status ein und prüfen, ob sich die drei oben genannten Fälle mit den nächstgelegenen Kreisen überschneiden. Beim letzten Punkt löschen wir den Kreis aus dem Status .

Es sieht so aus, als ob es für den Sweep-Line-Algorithmus ausreicht. Wenn etwas nicht stimmt oder wenn etwas nicht stimmt, können Sie uns gerne Ihre Gedanken mitteilen.

Nachtrag :

Ich füge einen Kreis ein, wenn die vertikale Sweep-Linie den Kreis zum ersten Mal berührt, und entferne einen Kreis aus dem Status, wenn die Sweep-Linie den Kreis zum letzten Mal berührt. Die Prüfung auf Schnittpunkte sollte für den nächsten vorherigen Kreis erfolgen. Wenn wir einen Kreis zum Status hinzugefügt haben und es bereits einen anderen Kreis gab, den wir zuvor hinzugefügt haben und der noch vorhanden war, wurde der durchlässige Kreis nicht "geschlossen", sodass möglicherweise eine Kreuzung vorliegt.

algorithms computational-geometry com
quelle

allmächtig [Zitieren benötigt]

JeffE

@com was meinst du mit "nächster vorheriger Kreis"?

Joe

Ich nehme an, dass statusdie Kreise, die derzeit die Sweep-Linie schneiden , beibehalten werden. Angenommen, Sie haben zurzeit 100 Kreise in status, verarbeiten ein Einfügeereignis und fügen den 101. Kreis ein. Wie viele Kreise vergleichen Sie, um die Schnittmenge zu ermitteln? Wie wählen Sie die zu vergleichenden Kreise aus?

Joe

y

$y$

y

$y$

y

$y$

y

$y$

y

$y$

y

$y$

Antworten:

Sie sind definitiv auf dem richtigen Weg. Die große Frage ist: Wenn Sie einen Kreis einfügen, welche anderen Kreise prüfen Sie auf Schnittpunkte? Wie führen Sie diese Prüfung durch?

In dem Liniensegment-Schnittfall sind die Liniensegmente bei jeder gegebenen x-Koordinate vollständig geordnet. (Sie können sie von der niedrigsten zur höchsten Y-Koordinate auflisten). Auf diese Weise können Sie die Liniensegmente in einem binären Suchbaum verwalten. Wenn Sie ein neues Segment hinzufügen, müssen Sie nur herausfinden, wo es in den binären Suchbaum gehört, und die Nachbarn auf Schnittpunkte überprüfen.

Im Kreise-Fall ist nicht sofort klar, welche Kreise überprüft werden sollen. Wenn Ihre Antwort "alle von ihnen" ist, dann muss Ihr Algorithmus etwas arbeiten.

Können Sie eine Möglichkeit finden, die Kreise so darzustellen, dass sie genau wie die Liniensegmente geordnet sind?

Versuchen Sie, die Kreise als zwei Halbkreise darzustellen. Jedes Einfügeereignis besteht aus zwei Ereignissen: der oberen Hälfte und der unteren Hälfte.

Joe
quelle

Leider habe ich keine Ahnung von Halbkreisen. Vielleicht betrachten Sie Halbkreis als minimale Einheit des Kreises, der geschnitten werden kann (3 Fälle von Schnitt: Schnitt liegt auf dem oberen Halbkreis, auf dem unteren oder auf beiden). Zu Beginn werden alle Kreise nach x-Koordinate ihrer linken und rechten Begrenzung geordnet. Wir sollten also nicht davon ausgehen, dass x im Status koordiniert ist , da alle Kreise bereits in x-Koordinatenreihenfolge vorliegen. Daher erscheint es logischer, die y-Koordinate des Zentrums (des Halbkreises) oder eine beliebige Kombination von y und Radien zu berücksichtigen. Deine Meinung?

com

@com Sie benötigen Mittelpunkt und Radius, um zu bestimmen, ob sich zwei Kreise schneiden, wie Sie es in Ihren eigenen Schnittpunktprüfungen getan haben. Nur die y-Koordinate und der Radius geben die Grenze des Kreises nicht vollständig an. Es scheint etwas Grundlegendes an Sweep-Line-Algorithmen zu sein, das Sie nicht verstehen, aber es fällt mir schwer zu sagen, was es ist.

Joe

Ich könnte mir diesen Ansatz analog zum Bentley-Ottmann-Sweep vorstellen, der in O ((n + k) logn) -Zeit abläuft.

Ich könnte das Problem der Kreiskreuzung auf eine Liniensegmentkreuzung reduzieren. Ich werde den vertikalen Durchmesser parallel zur Y-Achse für jeden der Kreise betrachten. Der Algorithmus verwendet eine horizontale Linie, die die Ebene von unten nach oben überstreicht.

Jetzt haben wir für jeden Kreis einen oberen und einen unteren Endpunkt. Außerdem müssen wir das Intersection-Prädikat so ändern, dass zwei Segmente sich genau dann schneiden, wenn die Sweep-Linie beide Kreise an einem Punkt durchschneidet.

Da das Linienschnittproblem in O ((n + k) logn) gelöst werden kann, folgt die gleiche Schranke auch für den Kreisschnitt.

Ich bin ziemlich davon überzeugt, dass dies funktionieren würde, aber wenn ihr auf jeden Fall darauf hinweisen könntet, dass dies im Allgemeinen nicht funktioniert, lasst es mich wissen.

TheGT
quelle