Zeigen Sie, dass bei einem Abfragepunkt q in der Zeit O (log n) getestet werden kann, ob q innerhalb P

Question

liegt. Ich versuche, einige Übungen des Buches "Algorithmische Berechnungsalgorithmen und Anwendungen, 3rd - de berg et al "von Kapitel 6 - Punkt Standort. Leider habe ich keine Ahnung, wie die folgende Übung zu lösen:

Given a convex polygon P as an array of its n vertices in sorted order 
along the boundary. Show that, given a query point q, it can be tested in 
time O(log n) whether q lies inside P.

Meine Idee so weit: Der einzige Weg, ich weiß, zu bestimmen, ob ein Punkt innerhalb p in O liegt (log n) verwenden ein gerichteter azyklischer Graph. Um einen gerichteten azyklischen Graphen zu verwenden, muss ich ihn konstruieren, was in O unmöglich ist (log n). Also, irgendwie muss ich das geordnete Array verwenden, aber die einzige Lösung, die ich mit einem Array kenne, kostet O (N).

Ich hoffe, dass mir jemand helfen könnte.

Answer 1

Die Idee ist im Grunde eine binäre Suche zu machen, um herauszufinden, zu welchem ​​'Segment' der Punkt gehört. Die Annahme hier ist, dass das Polygon um einen festen Ursprung O gewickelt wird, der notwendig ist, um eine Winkelsortierroutine zu definieren.

Um herauszufinden, ob q liegt auf der ‚linken‘ oder ‚rechts‘ von P[n/2] (womit ich einen gegen den Uhrzeigersinn oder im Uhrzeigersinn Drehdifferenz über O bedeuten), tun wir das 2D Kreuzprodukt:

Dies ist ein reeller Skalar. Wenn dies positiv ist, dann ist a rechts von b und umgekehrt. In unserem Code a = q - O und b = P[i] - O, wobei i der Index des Punktes auf dem Polygon ist, testen wir gegen.

Wir können dann diesen Test verwenden, das ‚Segment‘ oder ‚Keil‘ q ist, das heißt, die Punkte des Polygons zu finden q zwischen (diese auf dem Diagramm sind P[n/2 - 1] und P[n/2]) ist, eine binäre Suche verwendet, die ist O (log n). (Ich nehme an, Sie wissen, wie man das macht)

Sobald wir das wissen, müssen wir wissen, ob q innerhalb der "Keil" ist.

Von https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection, für zwei durch Paare von Punkten definiert Linien [(x1, y1), (x2, y2)] und [(x3, y3), (x4, y4)] bzw. deren Schnittpunkt (Px, Py) gegeben durch

Compute den Schnittpunkt zwischen [Pl, Pr] und [q, O] s zu geben, und berechnet den Abstand |s - O|. Wenn dies größer als |q - O| ist, dann ist q innerhalb des Polygons P und umgekehrt.

(Dieser Schritt ist natürlich O (1).Es kann jedoch elegantere Möglichkeiten geben, dies zu tun - ich veranschauliche nur die Logik dahinter.

Die Gesamtkomplexität ist dann O (log n) + 0 (1) = O (log n).