Schnellste horizontale Linie <-> konvexer Polygonschnitt Algorithmus?

Question

Ich brauche eine relativ einfache Sache zu lösen - ich habe n-Ecken konvex 2D-Polygon und eine horizontale Linie mit einigem ‚y‘ Koordinaten (!). Ich brauche nur eines:. Zu überprüfen, ob das Polygon mit dieser Linie (d haben zwei Kreuzungen) oder nicht

überschritten wird

die schnellste I denken kann, ist min / max y Koordinaten innerhalb eines Polygons zu finden (Schleife wiederholt n-mal mit zwei vergleicht und zwei Speicher), und dann, wenn der min y <= y

Irgendwie fühle ich dies mehr gelöst werden könnte „mathematisch“ aber ich habe immer mit langsamer Code enden (zB Vektor Art und Weise - ich brauche Unterschiede für n berechnen [i] und n [i + 1], dann multiplizieren sie, hinzufügen usw. - viel langsamer als 2 cmps + Speicher)

.

Answer 1

Sie müssen nur überprüfen, ob Ihr Polygon einen Punkt mit y1 y. Sobald Sie eine solche zwei Punkte gefunden haben, sind Sie fertig. Wenn Sie indizieren können Sie Ihre Punkte durch die Y-Koordinate, dass ein schnelles Nachschlagen sein sollte.

Answer 2

Wenn es eine horizontale Linie 2d ist dann ja, die Methode, die Sie beschrieben haben, ist wahrscheinlich die schnellste. Sie könnten Kurzschluss es so gut, als ob Sie teilweise durch den Scheck erhalten und haben einen min + max, die> und

Answer 3

Wenn Sie es auf dem rohen jeder Zeit zu tun haben, dann sind Sie wahrscheinlich nicht jeden Trick zu finden, geht es schneller zu machen als das.

Wenn Sie den Min- / Max-Y-Wert mit der Polygon-Cache können, dann können Sie Zeit, nicht Looping jede Ecke jedes Mal, wenn Sie den Test durchführen speichern.

Wenn Ihr Polygon einen ausgerichteten Begrenzungsrahmen zugeordnet ist, können Sie es gegen die Box Ausdehnungen anstelle des Polygons testen können und das gleiche Ergebnis schneller.

Answer 4

Ein weiterer Ansatz, ist hier beschrieben: optimaler Algorithmus, wenn Linien konvexes Polygon schneidet. Aber weil Sie mit orthogonalen Linien sind Handling, können Sie es ein wenig :) vereinfachen. Somit ist die Gesamtkomplexität N log ohne Werte zu speichern.