Wie kann man feststellen, ob ein Punkt in einem Bereich ist?
Die Eckpunkte für die Bereiche sind bekannt, es können aber beliebig viele sein. Hat jemand eine Idee, wie man feststellen könnte, ob ein Punkt in einem Bereich ist oder nicht?
Bei einem Kreis kann man es ja so machen x² + y² = r² und damit alle Pixel durchgehen und gucken, ob der Pixel dabei ist. Aber wie geht das bei solchen vielecken?
Ist bekannt, wie die Eckpunkte verbunden sind?
ja ist bekannt
2 Antworten
Das lässt sich m.W. nicht mehr allgemein mit einer einfachen Gleichung prüfen.
Es gibt verschiedene algorithmische Ansätze. Einer davon wäre, dass man vom Punkt aus beginnend eine gerade Strecke konstruiert, deren Ende aussserhalb des Polygons liegen muss. Dann zählt man, wieviele Schnittpunkte diese Strecke mit den Polygonkanten hat. Ist die Anzahl ungerade, weiss man, dass der Punkt im Polygon liegen muss - vereinfacht gesagt, denn es gibt noch einige Ausnahmesituationen, die gesondert betrachtet werden müssen.
Hier mehr Infos dazu:
Mein Vorschlag:
Man zieht (in Gedanken) eine Linie vom zu testenden Punkt waagerecht nach rechts (x = +Unendlich).
Dann zählt man die Schnittpunkte mit den Kanten der Polygone. (Vorsicht wenn die Linie durch eine Ecke geht, die darf man nicht doppelt zählen.)
Ist die Anzahl gerade, dann liegt der Punkt außerhalb, ist sie ungerade, liegt er innerhalb.