Schnellste horizontale Linie <-> konvexer Polygonschnitt Algorithmus?
-
06-07-2019 - |
Frage
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)
Lösung
Sie müssen nur überprüfen, ob Ihr Polygon einen Punkt mit y1
Andere Tipps
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
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.
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.