Mathematisches Problem
-
Ja ich habe sämtliche Koordinaten in der Liste. Und muss dann eben prüfen ob:
- der Punkt innerhalb der Außenlinie
- der Punkt außerhalb der Innenlinie
- der Punkt außerhalb von sogenannten "Inseln" istDas ist aber 3 Mal der selbe Algorithmus -> und ich habe 3 Mal keine Ahnung wie ich das bewerkstelligen soll
MfG SideWinder
-
Unterteile das Vieleck in lauter Dreiecke und prüfe dann, üb der Punkt in einem der Dreiecke liegt. Das ist auch wesentlich einfacher.
-
Tja, nur wie einteilen?
Die Anzahl der Außenpunkte hat nichts mit der Anzahl der Innenpunkte zu tun. Somit will ich diese auch in keinen Zusammenhang stellen (und habe sie vorher auch gar nicht erwähnt).
Man muss doch irgendwie überprüfen können ob ein Punkt innerhalb oder außerhalb einer Linie liegt?!
MfG SideWinder
-
Du nimmst irgendeine Halbgerade, die auf deinem Punkt beginnt, und berechnest, wieviele Linien des Polygons sie schneidet. Ist die Anzahl ungerade, liegt der Punkt im Polygon, ansonsten nicht.
[ Dieser Beitrag wurde am 26.06.2003 um 19:44 Uhr von MFK editiert. ]
-
Und wie könnte man sowas programmiertechnisch umsetzen?
MfG SideWinder
-
Du stellst die Gleichung der Geraden auf, die genau waagrecht durch den zu testenden Punkt geht.
Dann schneidest Du die mit allen Begrenzungsstrecken des Vielecks. Von den Schnittpunkten betrachtest Du dann aber nur die, die z.B. rechts vom Punkt liegen.
Klar ist, daß Du mit dem letzten Schnittpunkt (größte x-Koordinate) das Vieleck verläßt (es ist ja geschlossen). Dann mußte einfach noch Schnittpunkte zählen. Bei jedem Schnittpunkt wechelst Du die Seite. Drinnen/draußen...
Nur aufpassen muß Du, wenn Deine Gerade genau in einem Eckpunkt schneidet. Dann gibt es noch Sonderfälle. Da kommt's nämlich drauf an, ob die beiden an den Eckpunkt ankommenden Kanten beide auf der selben Seite der Geraden liegen (kein Seitenwechsel) oder eben auf verschiedenen (=> Seitenwechsel). Oder die Gerade könnte sogar komplett innerhalb einer Randkante verlaufen, das geht dann aber ganz ähnlich.
Am besten einfach mal ne Zeichnung machen und ne Runde probieren.MfG Jester
-
Du bildest die Geradengleichungen "deiner" Halbgeraden sowie jeder Strecke des Polygons und suchst nach dem Schnittpunkt (falls es einen gibt). Das ist jeweils ein lineares Gleichunssystem mit zwei Unbekannten. Danach musst du prüfen, ob der gefunden Schnittpunkt sowohl auf der Halbgeraden liegt (die Halbgerade wird durch eine Koordinate deines Punktes beschränkt sein) als auch auf der Polygonstrecke (hier bilden die Koordinaten der Endpunkt ein Intervall).
Die Anzahl der "echten" Schnittpunkte entscheidet über die Lage des Punktes.Beispiel:
Polygon
A(0|0)
B(3|0)
C(2|2)Punkt:
X(1,5|1)Als Halbgerade wähle ich die Richtung der positiven X-Achse.
Geradengleichung der Halbgeraden y = 0 * x + 1
Bedingung: x >= 1,5Geradengleichung zu AB: y = 0 * x + 0
Bedingung: 0 <= x <= 3Geradengleichung zu BC: y = -2 * x + 6
Bedingung: 2 <= x <= 3Geradengleichung zu CA: y = x
Bedingung: 0 <= x <= 2Schnittpunkt mit AB: Keiner (sind parallel)
Schnittpunkt mit BC: Bei (2,5|1), Bedingungen erfüllt, zählt!
Schnittpunkt mit CA: Bei (1|1), Bedingung der Halbgeraden nicht erfüllt, zählt nicht.Echte Schnittpunkte 1: Punkt liegt innerhalb
Das kann noch knifflig werden, wenn ein Schnittpunkt genau auf einen Punkt des Polygons fällt, oder die Halbgerade genau auf einer Strecke liegt. Vielleicht sollte man einfach die Halbgerade so wählen, dass das nicht passiert.
Nachtrag:
Sehe gerade, dass Jester das gleiche geschrieben hat. Naja, doppelt hält besser
[ Dieser Beitrag wurde am 26.06.2003 um 20:15 Uhr von MFK editiert. ]
-
Danke - damit kann ich schon einmal etwas anfangen :). Mal sehen ob ich das so hinbekomme! Wenn nicht werde ich mich hier wieder melden.
MfG SideWinder
-
Achja, in Java gibt es übrigens ne fertige Funktion, die testet ob ein Punkt in einem Polygin liegt.
-
Sowas gibt es bei Turbo Pascal natürlich nicht
MfG SideWinder