Asymptotisch optimaler Algorithmus zur Berechnung, ob eine Linie ein konvexes Polygon schneidet

lhf ' s Antwort ist fast korrekt. Hier ist eine version, die sollte das problem beheben sein.

Lassen Sie das polygon haben den Eckpunkten v0, v1, ..., vn gegen den Uhrzeigersinn in Ordnung. Lassen Sie die Punkte x0 und x1 auf der Strecke.

Beachten Sie zwei Dinge: Erstens, die Suche nach dem Schnittpunkt von zwei Linien (und Bestimmung seiner Existenz) getan werden kann in konstanter Zeit. Zweitens, zu bestimmen, ob ein Punkt Links oder rechts neben einer Zeile getan werden kann in konstanter Zeit.

Wir Folgen der gleichen Grundidee von lhf, um eine O(log n) - Algorithmus. Die Basis-Fälle sind, wenn das polygon hat 2 oder 3 Knoten. Diese können beide behandelt werden in konstanter Zeit.

Bestimmen, ob die Zeile (v0,v(n/2)) schneidet die Linie (x0,x1).

Fall 1: Sie nicht schneiden.

In diesem Fall die Linie, die wir interessiert sind, ist entweder auf der linken oder der rechten Seite der Linie Aufspaltung des Polygons, und so können wir recurse-in, dass die Hälfte des Polygons. Speziell, wenn x0 auf der linken Seite von (v0,v(n/2)) dann werden alle Eckpunkte in der richtigen "Hälfte", {v0, v1, ... v(n/2)} auf derselben Seite von (x0,x1) und so wissen wir, dass es keine Kreuzung, dass "die Hälfte" des Polygons.

Fall 2: Sie tun sich überschneiden.

Diesem Fall ist ein wenig komplizierter, aber wir können immer noch eng auf der Kreuzung zu einer "Hälfte" des Polygons in konstanter Zeit. Es gibt 3 subcases:

Fall 2.1: Der Schnittpunkt zwischen den Punkten v0 und v(n/2)

Sind wir fertig. Die line schneidet das polygon.

Fall 2.2: Die Kreuzung näher zu v0 (D. H. außerhalb des Polygons auf v0 Seite)

Bestimmen, ob die Linie (x0,x1) schneidet die Linie (v0,v1).

Wenn nicht, dann sind wir fertig, die Linie überschneidet sich nicht mit dem polygon.

Wenn es nicht, suchen Sie den Schnittpunkt p. Wenn p rechts von der Linie (v0, v(n/2)) dann recurse in der rechten "Hälfte" des Polygons, {v0, v1, ..., v(n/2)}, sonst recurse auf der linken "Hälfte" {v0, v(n/2), ... vn}.

Die Grundidee in diesem Fall ist, dass alle Punkte im polygon sind auf der einen Seite der Linie (v0, v1). Wenn (x0, x1) ist divergierenden Weg von (v0, v1) auf der einen Seite seiner Kreuzung mit (v0, v(n/2)). Wir wissen, dass auf dieser Seite kann es keine Schnittpunkte mit dem polygon.

Fall 2.3: Die Kreuzung ist näher an v(n/2)

Diesem Fall wird ähnlich behandelt zu Fall 2.2, sondern mit den entsprechenden Nachbarn von v(n/2).

Sind wir fertig. Für jede Ebene erfordert dies zwei line-Kreuzungen, Links-rechts-schauen, und zu bestimmen, wo ein Punkt auf einer Linie. Jede Rekursion teilt die Anzahl der vertices durch 2 (technisch teilt Sie durch mindestens 4/3). Und so erhalten wir eine Laufzeit von O(log n).

InformationsquelleAutor der Antwort Chris Hopman

Bounding-Boxen könnten sich als nützlich erweisen.

Daran erinnern, dass eine konvexe Teil von einem affinen Raum ist der Schnittpunkt der alle seine Hülle hyperplanes: Sie bekommen konnte eine Annäherung an das polygon (siehe auch "umschließende konvexe polygon") wenn nur der Schnittpunkt einer Teilmenge der Umschlag hyperplanes, test zum Schnittpunkt der Linie mit dieser Näherung und verfeinern, falls nötig.

All das funktioniert besser, wenn Sie erwarten, eine geringe Anzahl von Kreuzungen.

InformationsquelleAutor der Antwort Alexandre C.

nehmen eine zufällige zwei Punkte A und B von convex poligon.

• wenn Sie auf verschiedenen Seiten der geraden, Sie schneiden sich
• wenn Sie auf der gleichen Seite, auf beiden poligon Teile (sagen wir im Uhrzeigersinn AB und BA) tun:
  
  • erstellen Sie eine Linie parallel zur Linie l, die geht durch Eine
  • finden-point bei der maximalen Distanz von l auf die poligon, das gleiche wie der Suche nach maximum in der Funktion, die zuerst monoton nondecreasing, und dann monoton nonincreasing. dies kann durchgeführt werden in O(log n) durch die ternäre Suche

wenn diese beiden entferntesten Punkte sind auf die andere Seite von Ihr, die Linie kreuzt, poligon, sonst nicht

Übrigens finden Sie auch die tatsächlichen Schnittpunkte in O(log n).

InformationsquelleAutor der Antwort Sarmun