Hallo!
Ich habe mehrere Punkte (x/y) in einem 2D-Koordinatensystem, die zusammen ein Polygon bilden. Dann habe ich noch einen gegebenen Punkt P und nun möchte ich bestimmen, ob dieser Punkt P innerhalb des Polygons liegt oder außerhalb. Wie ist das möglich, wer kann mir dabei weiterhelfen. Bitte um möglichst einfache Erklärung, da ich kein Mathematiker bin.
Danke und liebe Grüße
Daniel
Ich habe mehrere Punkte (x/y) in einem 2D-Koordinatensystem,
die zusammen ein Polygon bilden. Dann habe ich noch einen
gegebenen Punkt P und nun möchte ich bestimmen, ob dieser
Punkt P innerhalb des Polygons liegt oder außerhalb.
Hallo Daniel,
Polygone werden durch mehrere Ungleichungen beschrieben. Du gehst folgendermaßen vor.
Du nimmst die ersten beiden deiner gegebenen Punkte P1(x1|y1) und P2(x2|y2) und legst dadurch eine Gerade der Form
ax+by=c. a,b und c kannst du folgendermaßen berechnen.
a=y1-y2
b=x2-x1
c=x2y1-x1y2
Aus der entstandenen Gleichung musst du jetzt eine Ungleichung machen. Um zu entscheiden ob aus dem = ein ≥ oder ≤ werden muss setzt du irgendeinen weiteren deiner gegebenen Punkte ein, z.B. P3(x3|y3) und änderst das Relationszeichen so um, dass der Punkt die Ungleichung erfüllt.
Diesen ganzen Prozess wiederholst du mit P2 und P3, dann mit P3 und P4 usw., zum Schluss mit dem letzten und dem ersten Punkt. Insgesamt kriegst du so genauso viele Ungleichungen wie du Punkte hast. Jede Ungleichung repräsentiert eine Seite des Polygons.
Wenn ein Punkt alle Ungleichungen gleichzeitig erfüllt liegt er im Polygon drin, ansonsten liegt er außerhalb.
Damit es etwas klarer wird noch ein Beispiel.
P1(1|2), P2(5|3), P3(4|6)
Das ergibt ein Dreieck (logisch bei drei Punkten).
erste Ungleichung:
a=2-3=-1
b=5-1=4
c=5⋅2-1⋅3=7
Daraus entsteht -x+4y=7
≥ oder ≤ mit P3 entscheiden: -4+6⋅6=32≥7
Die erste Ungleichung ist also -x+4y≥7
zweite Ungleichung: -3x-y≥-18
dritte Ungleichung: 4x-3y≥-2
Punkte innerhalb des Dreiecks erfüllen alle drei Ungleichungen gleichzeitig. Wird eine Ungleichung sogar mit = erfüllt, dann liegt der Punkt auf der entsprechenden Seite des Dreiecks. Wird mindestens eine Ungleichung nicht erfüllt, dann liegt der Punkt außerhalb des Dreiecks.
Ich hoffe, das war verständlich genug für eine Nichtmathematiker.
Grüße
hendrik
Ein riesen Dankeschön für die Mühe und die tolle Antwort!
Ja, das war denke ich schon verständlich. Ich muss also immer so viele Ungleichungen bilden, wie mein Polygon Punkte hat, oder? Nur noch was wegen dem Relationszeichen:
Es ist ganz egal, welchen dritten Punkt ich nehme, um zu entscheiden ob ≥ oder ≤?
Danke nochmal,
liebe Grüße
Daniel
Es ist ganz egal, welchen dritten Punkt ich nehme, um zu
entscheiden ob ≥ oder ≤?
Ja, das ist egal, es muss nur ein Punkt sein, von dem du weißt, dass er innerhalb des Polygons (oder auf einer der Kanten) liegt.
Allerdings ist es wichtig, dass man um eine Gerade aufzustellen immer zwei Punkte nimmt die durch eine Kante des Polygons verbunden sind, also quasi immer zwei benachbarte Ecken.
Wenn du einfach nur ein paar Punkte ohne Reihenfolge gegeben hast wird das Problem ein Polygon herzuleiten (beziehungsweise die konvexe Hülle zu finden) sehr schnell sehr viel schwieriger.
Gruß
hendrik
Ich habe mehrere Punkte (x/y) in einem 2D-Koordinatensystem,
die zusammen ein Polygon bilden. Dann habe ich noch einen
gegebenen Punkt P und nun möchte ich bestimmen, ob dieser
Punkt P innerhalb des Polygons liegt oder außerhalb. Wie ist
das möglich, wer kann mir dabei weiterhelfen. Bitte um
möglichst einfache Erklärung, da ich kein Mathematiker bin.
Wenn die Anzahl der Schnittpunkte eines vom Punkt ausgehenden Strahls mit den Seiten des Polygons geradzahlig ist, liegt der Punkt außerhalb des Polygons. Das funktioniert nicht nur mit Polygonen, sonden auch mit Körpern. Da zählt man dann die Anzahl der Schnittpunkte mit den Seitenflächen. Das Prinzip wird z.B. beim Raytracing verwendet, um zu entscheiden, ob der Strahl auf die Innen- oder Außenseite eines Körpers trifft.