Ich arbeite an einem JS-Programm, das ich bestimmen muss, wenn Punkte innerhalb von vier Ecken in einem Koordinatensystem sind.Ermitteln, ob ein 2D-Punkt innerhalb eines Vierecks ist
Kann mir jemand in die Richtung einer Antwort zeigen?
Ich schaue, was ich denke, ein konvexes Viereck genannt wird. Das heißt, vier ziemlich zufällig gewählte Eckpositionen mit allen Winkeln kleiner als 180 °.
Danke.
Es gibt zwei relativ einfache Ansätze. Der erste Ansatz besteht darin, einen Strahl von dem Punkt zu "unendlich" (tatsächlich zu irgendeinem Punkt außerhalb des Polygons) zu zeichnen und zu zählen, wie viele Seiten des Polygons der Strahl schneidet. Der Punkt ist genau dann innerhalb des Polygons, wenn der Zählwert ungerade ist.
Der zweite Ansatz ist, um das Polygon herum, um zu gehen und für jedes Paar von Ecken v i und v i + 1 (um auf den ersten Scheitelpunkt ggf. Verpackung), um die Menge zu berechnen (x - x i) * (y i + 1 - y i ) - (x i + 1 - x i ) * (y - y i ). Wenn diese Größen alle das gleiche Vorzeichen haben, befindet sich der Punkt innerhalb des Polygons. (Diese Größen sind die Z-Komponente des Kreuzprodukts der Vektoren (v i + 1 - v i) und (p-v i). Die Bedingung, dass sie alle das gleiche Vorzeichen haben, ist dasselbe wie die Bedingung, dass p auf der gleichen Seite (links oder rechts) jeder Kante ist.)
Beide Ansätze müssen mit dem Fall umgehen, dass der Punkt genau an einer Kante oder an einem Scheitel liegt. Sie müssen zuerst entscheiden, ob Sie solche Punkte als innerhalb des Polygons zählen möchten oder nicht. Dann müssen Sie die Tests entsprechend anpassen. Beachten Sie, dass kleine numerische Rundungsfehler eine falsche Antwort liefern können. Es ist nur etwas, mit dem du leben musst.
Da Sie ein konvexes Viereck haben, gibt es einen anderen Ansatz. Wählen Sie drei beliebige Eckpunkte aus und berechnen Sie den barycentric coordinates des Punkts und des vierten Eckpunkts in Bezug auf das Dreieck, das von den drei ausgewählten Eckpunkten gebildet wird. Wenn die baryzentrischen Koordinaten des Punktes alle positiv und alle kleiner als die baryzentrischen Koordinaten des vierten Eckpunkts sind, liegt der Punkt innerhalb des Vierecks.
P.S. Habe gerade eine nette Seite here gefunden, die eine ganze Reihe von Strategien auflistet. Einige von ihnen sind sehr interessant.
Ich sehe nicht, wie ich einen Strahl wie im ersten Ansatz zeichnen soll, ohne viele (unnötige) Berechnungen zu machen, aber ich schätze, ich werde es mit dem zweiten arbeiten lassen. Vielen Dank! – Henrik
@Henrik - Wählen Sie einfach einen Punkt auf der X-Achse, der weiter entfernt ist als die maximale X-Koordinate der vier Scheitelpunkte. Der Strahl kann dann von Ihrem Testpunkt zu dem Punkt auf der X-Achse gehen. (Sie können natürlich auch die Y-Achse verwenden.) Denken Sie daran, dass Sie den Schnittpunkt der Linie _segmente_, nicht die Linien, testen müssen. –
@ Henrik - Wenn Sie mit dem zweiten Ansatz gehen, beachten Sie, dass ich einen Tippfehler in der Formel hatte. Es ist jetzt behoben. (Ich hatte 0 anstelle von i als einen Index an ein paar Orten verwendet.) –
Sie müssen Wicklung oder die Ray-Trace-Methode verwenden.
Mit der Wicklung können Sie bestimmen, ob sich ein Punkt in einer beliebigen Form mit Liniensegmenten befindet.
Grundsätzlich nehmen Sie das Kreuzprodukt jedes Liniensegments mit dem Punkt, dann addieren Sie alle Ergebnisse. So habe ich es gemacht, um zu entscheiden, ob sich ein Stern in einer Konstellation befindet, mit einer Reihe von Konstellationslinien. Ich kann sehen, dass es andere Wege gibt ..
http://en.wikipedia.org/wiki/Point_in_polygon
Es muss einen Code sein, diese in einigen Plätzen.
Es ist viel einfacher zu sehen, wenn ein Punkt innerhalb eines Dreiecks liegt.
Jedes Viereck kann in zwei Dreiecke unterteilt werden.
Wenn sich der Punkt in einem der zwei Dreiecke befindet, die das Viereck bilden, befindet sich der Punkt innerhalb des Vierecks.
Ich versuchte das hier verwendete Inpolygon-Methon [link] (http://stackoverflow.com/questions/5922027/how-to-determine-if-a-point-is-within-a-quadrilateral?rq=1) , aber es funktioniert nicht. Es gibt mir "Kann Methode nicht in Polygon von undefined aufrufen". 'if (Math.inpolygon (5,6, [1,22,13,1], [1,1,21,31])) { Rückgabe" yep "; } ' – Henrik
und warum können Sie nicht einfach Koordinaten vergleichen? Kannst du das Problem näher beschreiben? Was sind Punkte? Ecke? – 4pie0
Ich habe Tonnen von ziemlich zufällig erzeugten Vierecke. Dann muss ich prüfen, ob einige (auch ganz zufällig generierte) Punkte "verfügbar" sind oder bereits von einem Viereck besetzt sind. – Henrik