Hallo,
eine Frage, vielleicht hat einer von euch 'nen Tip oder 'ne Anregung fuer mich:
In einem zweidimensionalen Koordinatensystem habe ich ein Polygon p, bestehend aus beliebig vielen Nodes n. Wie kann ich feststellen, ob Punkt x sich innerhalb oder ausserhalb des Polygons befindet?
Danke schonmal,
Uwe
Hallo,
die Fläche innerhalb des Polygons ergibt sich als Schnittfläche der Halbebenen der Geraden, die das Polygon beschreiben. Damit ist der Punkt innerhalb (inkl. Rand) des Polygons, wenn er in jeder dieser Halbebenen liegt, ansonsten außerhalb.
Gruss
Enno
Hallo Enno,
aber das trifft nur auf regulaere Polygone zu. Nimm ein irregulaeres, wie … *googling* … hier in dem Bild rechts unten:
http://sis.cmis.csiro.au/svg/results/shapes-polygon-…
und deine Rechnung stimmt nicht mehr.
Gruss,
Uwe
die Fläche innerhalb des Polygons ergibt sich als
Schnittfläche der Halbebenen der Geraden, die das Polygon
beschreiben. Damit ist der Punkt innerhalb (inkl. Rand) des
Polygons, wenn er in jeder dieser Halbebenen liegt, ansonsten
außerhalb.Gruss
Enno
In einem zweidimensionalen Koordinatensystem habe ich ein
Polygon p, bestehend aus beliebig vielen Nodes n. Wie kann ich
feststellen, ob Punkt x sich innerhalb oder ausserhalb des
Polygons befindet?
Du legst eine Halb-Gerade durch den Punkt x. Der Endpunkt der Halbgeraden sei der Punkt x selbst. Dann bestimmst du die Schnittpunkte der Halb-Geraden mit dem Polygon p.
Wenn die Anzahl der Schnittpunkte ungerade ist, liegt x in p; andernfalls liegt x außerhalb.
Die Anzahl an Nodes und ob es sich um was für ein Polygon es sich handelt, ist dabei irrelevant.
Gruß,
Frank
Hallo Frank,
Du legst eine Halb-Gerade durch den Punkt x. Der Endpunkt der
Halbgeraden sei der Punkt x selbst.
Soweit klar. Nur, durch welchen weiteren Punkt soll die Gerade dann ins Unendliche laufen?
Dann bestimmst du die
Schnittpunkte der Halb-Geraden mit dem Polygon p.
Wenn die Anzahl der Schnittpunkte ungerade ist, liegt x in p;
andernfalls liegt x außerhalb.Die Anzahl an Nodes und ob es sich um was für ein Polygon es
sich handelt, ist dabei irrelevant.
Danke, hoert sich gut an. Ich verstehe nur nicht in welchem Winkel du die Halbgerade setzt - kannst du mich da noch aufklaeren?
Gruss,
Uwe
Du legst eine Halb-Gerade durch den Punkt x. Der Endpunkt der
Halbgeraden sei der Punkt x selbst.Soweit klar. Nur, durch welchen weiteren Punkt soll die Gerade
dann ins Unendliche laufen?
Ah… grade gegoogelt, laut dem Jordanischen Kurvensatz kann die Halbgerade in jedem beliebigen Winkel angesetzt werden. Mal ausprobieren…
Vielen Dank!
Hallo,
Du legst eine Halb-Gerade durch den Punkt x. Der Endpunkt der
Halbgeraden sei der Punkt x selbst.Soweit klar. Nur, durch welchen weiteren Punkt soll die Gerade
dann ins Unendliche laufen?
Das sollte egal sein.
[a] Liegt x nicht im Polygon, kann es sein, du bekommst Null Schnittpunkte - dann hast du ja die Lösung (Null sei gerade). Wenn die Gerade durch das Polygon geht, bekommst du immer eine gerade Anzahl Schnittpunkte (die Gerade schneidet immer, wenn’s ins Polygon geht, das Polygon nochmal, wenn’s wieder rausgeht. Wenn das Polygon endlich groß ist, ist der Schnitt nach draußen immer der letzte).
[b] Liegt x im Polygon, schneidet die Halbgerade das Polygon auf jeden Fall mindestens einmal. Danach befindet sie sich ja außerhalb. Ab da gilt das gleiche wie bei [a], d.h., die Anzahl der Schnittpunkte bleibt ungerade.
Hoffe, das war nicht zu wirr.
Gruß
Jochen
Danke, hoert sich gut an. Ich verstehe nur nicht in welchem
Winkel du die Halbgerade setzt - kannst du mich da noch
aufklaeren?
Wie die andern schon sagten, es ist völlig egal, in welchem Winkel die Halbgerade steht.
Um die Sache jedoch nicht unnötig kompliziert zu machen, sollte die Halbgerade keine Eckpunkte berühren, denn berührte Eckpunkte zählen nicht bzw. doppelt (sorry, hab ich vergessen zu erwähnen…)
Gruß,
Frank
