Algorithmus für disjunktes Segmentsichtbarkeitsproblem

Bedenken Sie, wir haben $n$ disjunkte Segmente und ein Punkt $P$Das ist in keinem Segment. Ich möchte einen finden$O(n \log n)$ Algorithmus, um zu überprüfen, von welchen Segmenten aus sichtbar ist $P$. Ein Segment ist sichtbar von$P$ wenn es einen Punkt hat, der von sichtbar ist $P$.

Meine Idee ist es, eine Sweep-Halblinie mit einem Endpunkt zu verwenden $P$, sortiere Punkte im Uhrzeigersinn nach Grad und beginne von einem Endpunkt auf dem nächsten sichtbaren Segment (das ich nicht zu finden weiß), drehe und erkenne jeweils ein sichtbares und einige mögliche unsichtbare Segmente. Ich kann nur daran denken$O(n^2)$bisher. Kann mir jemand einen vorschlagen$O(n \log n)$ Algorithmus.

Wolg könnten wir annehmen $P$ ist der Ursprungspunkt $(0,0)$.

1. Listen Sie die Endpunkte aller Segmente auf und stellen Sie sie in Polarkoordinaten dar $(\theta,\rho) \in [0,2\pi) \times [0,\infty)$ und sortieren Sie sie nach ihrem Grad.
2. Stellen Sie sich vor, es gibt einen Strahl von $P$ Wir zeigen nach rechts und fegen es eine Runde lang (indem wir seine Richtung allmählich ändern $\alpha$ von 0 bis $2\pi$). Lassen$R(\alpha)$ bezeichnet den Strahl von $P$ in Richtung $\alpha$. Wir fragen uns, was die Segmente sind$R(\alpha)$ Treffer, und was ist ihre Reihenfolge auf $R(\alpha)$.
3. Finden Sie heraus, welche Segmente getroffen wurden $R(0)$und sortieren Sie sie nach ihrer Reihenfolge auf $R(0)$. Speichern Sie sie in einem ausgeglichenen binären Suchbaum (z. B. rot-schwarzer Baum).
4. Durchlaufen Sie die Punkte, die wir in Schritt 1 gefunden (und sortiert) haben: Jeder Punkt $(\theta,\rho)$ zeigt an, dass ein Segment den Strahl treffen / stoppen würde $R(\alpha)$ wann $\alpha$ steigern zu $\theta$. Aktualisieren Sie den binären Suchbaum entsprechend.
5. Die Elemente, die einst die kleinsten im binären Suchbaum waren, sind die Segmente, von denen aus sie sichtbar sind $P$.

Es ist einfach zu überprüfen, ob die Laufzeit des obigen Algorithmus ist $O(n \log n)$.

Wir können einen radialen Linien-Sweep durchführen, um das Problem zu lösen -

Sortieren Sie die Endpunkte der Liniensegmente nach dem Winkel, in dem die Linie verbunden ist $P$ und der Endpunkt $Q$ machen, brechen Krawatten wrt Abstand von $P$. Wenn wir nun radial (im Uhrzeigersinn) fegen, behalten wir zwei Arten von Ereignissen bei: "Öffnen" und "Schließen", die dem Öffnen und Schließen eines neuen Liniensegments entsprechen. Verfolgen Sie, wie viele Liniensegmente zu einem bestimmten Zeitpunkt "aktiv" sind ("aktiv" bedeutet, dass wir auf den Endpunkt gestoßen sind, der dem "offenen" Ereignis des Liniensegments entspricht, aber nicht auf den anderen Endpunkt im noch fegen). Wenn wir zu irgendeinem Zeitpunkt genau ein 'aktives' Liniensegment haben, ist dieses Segment von sichtbar$P$.

Wir sollten darauf achten, dass wir zu Beginn des Sweeps immer bei einem „offenen“ Event beginnen.

Es wird____geben $2n$Solche Ereignisse und das Verfolgen der Anzahl aktiver Segmente können in konstanter Zeit pro Segment durchgeführt werden (über eine Hash-Tabelle oder eine Logarithmus-Zeit unter Verwendung einer ausgeglichenen BST). Daher ist der dominierende Schritt in diesem Algorithmus die Sortierung, die dauert$\mathcal{O}(n)$ Zeit nach Bedarf.

Wie bei allen Problemen mit der rechnerischen Geometrie kann es einige Eckfälle geben, die ich übersehen habe, aber die allgemeine Vorstellung, dass wenn zu einem bestimmten Zeitpunkt während des radialen Liniendurchlaufs genau ein aktives Liniensegment vorhanden ist, es von sichtbar ist $P$ ist der springende Punkt, um dieses Problem zu lösen.