Koordinatensystem: Punkt innerhalb eines Polygons oder nicht?

14.08.2011, 13:12	Franticc	Auf diesen Beitrag antworten »
Koordinatensystem: Punkt innerhalb eines Polygons oder nicht? Meine Frage: Hey there, Meine Problemstellung ist, siehe Titel: Ich möchte einen Punkt im Koordinatensystem darauf überprüfen ob er innerhalb eines Polygons,von welchem ich ausschließlich die Eckpunkte kenne, liegt, oder nicht. Dummerweise ist mein Mathe-Schulwissen nicht das beste und dazu noch einige Zeit her, deswegen weiß ich nichtmal so richtig wo ich anfangen soll. EDIT: Eine Lösung, die auch auf konkave Polygone anwendbar ist, wäre optimal. Im Notfall tuts aber auch eine für konvexe only. Ich vermute das wäre deutlich simpler? Meine Ideen: Soweit ich das bisher glaube verstanden zu haben, muss die Basis meiner Berechnung wohl der Schwerpunkt des Polygons sein. Abgesehen davon daß mich dazu schon die Formel leicht überfordert, bin ich mir aber auch noch nicht im klaren wohin genau mich das führen soll. Muss ich die Distanz zu den Polygon-Seiten berechnen? Und wie hilft mir das dann widerum weiter? Wie ihr seht, bin ich Mathe-Depp und etwas lost. Über Hilfe dankbar! Gruß
14.08.2011, 15:34	Gualtiero	Auf diesen Beitrag antworten »
Eine Formel dafür ist mir nicht bekannt, die Aufgabe läßt sich aber gut mit einem Programm lösen. Z. B. mit den Punkten 1, 2, 3, 4 und 5 des abgebildeten Polygons stellst Du Geraden auf, die im gleichen Sinn "orientiert" sind, also Gerade12, Gerade23, Gerade34 usw. Dann prüfst Du, auf welcher Seite der Geraden jeweils der Punkt liegt. Wenn Du ausnahmslos gleiche Ergebnisse bekommst, liegt der Punkt innerhalb. Ein konkaves Gebilde könnte man z. B. in zwei oder mehrere konvexe Teilpolygone zerlegen. Zugegeben, ist keine schöne mathematische Lösung, aber vielleicht weiß die ja jemand anders. [attach]20845[/attach]
14.08.2011, 15:37	Grouser	Auf diesen Beitrag antworten »
Meine spontane Idee wäre es: Du suchst von jeder Verbindungsstrecke den minimalen Abstand zu dem untersuchenden Punkt. Durch die erhaltenden Ergebnisse lässt sich dann (abhängig vom Polygon) leicht darauf schließen, wo sich der Punkt befindet.
14.08.2011, 15:44	Airblader	Auf diesen Beitrag antworten »
Ich gehe mal davon aus, es geht hier um ein Programm, das entwickelt werden soll. Ich gehe auch davon aus, dass solche Abfragen mehr als nur einmal durchgeführt werden soll. Dann ist es ein Ziel der Numerik, nicht nur Algorithmen zu finden, sondern auch möglichst schnelle. Unter Umständen ist es ja sogar gar nicht wichtig, ob das Ergebnis "100%-ig" stimmt. Ohne Rahmendaten, woher die Aufgabe kommt, ist das schwierig zu beurteilen. Genau aus dem Grund wäre Recherche hier vielleicht eine gute Idee. Ganz spontanes Suchen liefert zum Beispiel das hier. Gelesen habe ich es nicht, aber es scheint zumindest schonmal Einiges drinzustehen. air
14.08.2011, 16:55	Franticc	Auf diesen Beitrag antworten »
wow, vielen Dank erstmal für die Antworten. Insbesondere der Link den Airblader da aus dem Hut gezogen hat ist sehr interessant. Der Ansatz der Winkelsummierung müsste, wenn ich keinem Denkfehler erlegen bin genau das sein was ich suche. Sobald der summierte Winkel zwischen dem Punkt A und den verschiedenen Polygon-ecken auf exakt 360° kommt, sollte der Punkt innerhalb des Polygons liegen. Ich bin nur nicht sicher ob das nicht unter speziellen Umstädenn auch vorkommen könnte obeohl der Punkt ausserhalb liegt. Wenn es so einfach ist, wäre ich begeistert. Werde das nun mal zu testen versuchen. Achja und es geht wie richtig vermutet um ein Software-Projekt. Allerdings sind sowohl Performance als auch Genauigkeit zwar wichtig, aber nicht derart daß es nur mit einer superschlanken Lösung ginge. Gruß
15.08.2011, 16:04	Franticc	Auf diesen Beitrag antworten »
Hey, Falls jemanden die Lösung interessiert: Man messe jeweils den Winkel zwischen Punkt A und zwei nebeneinanderliegenden Eckpunten des Polygons. Das wiederholt mit allen Eckpunkten ergibt in der Summe immer exakt 360° falls der Punkt innerhalb des Polygons liegt. Wenn er ausserhalb liegt, sind es <360, bzw im Falle eines konkaven Polygons auch mal >360. siehe Bilder 1 und 2 Das funktioniert leider nur für konvexe Polygone perfekt. Bei einem konkaven Polygon werden einzig alle Punkte auf einer "theoretischen konvexen Aussenlinie" ebenfalls als "innerhalb des Polygons" also EXAKT 360° erkannt. Möglicherweise lässt sich das Szenario aber noch relativ einfach abfangen. siehe bild 3 Vielen Dank allerseits für die Hilfe! 1. [attach]20854[/attach] 2. [attach]20855[/attach] 3. [attach]20856[/attach]
Anzeige

15.08.2011, 18:48	Dopap	Auf diesen Beitrag antworten »
In analytischer Geometrie wird manchmal gefragt, ob ein Dreieck im Raum ( z. b. dreieckiges Verkehrsschild ) eine Sichtlinie abdeckt, sprich der Schnittpunkt der Ebene des Dreiecks mit der Sichtgeraden ( S ) im Dreieck liegt. Wir erarbeiten dann folgende Lösung: 2 Kanten samt "Schenkelpunkt" bilden ein Koordinatensystem. Sind nun die neuen Koordinaten von S beide positiv und die Summe kleiner 1 , dann liegt S im Dreieck. nun könnte man ja ein beliebiges Polygon in lauter Dreiecke zerlegen... Vermutlich ist der Programmieraufwand samt Laufzeit als ungünstig anzusehen.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »