Berechnung der inneren Gitter-Punkte eines Polygons

mtx

Hallo zusammen!

Ich habe ein Polygon und ein darüberliegendes Gitter. Jetzt möchte ich wissen, welche der Gitterpunkte in dem Polygon liegen, wie kann man das möglichst performant lösen?

- Von dem Gitter kenne ich die Gitterpunkte
- Von dem Polygon kenne ich die Eckpunkte

Ich hab irgendwas im Kopf, dass man das über die Kanten des Polygons machen kann und dann mit der Determinante weiter kommt, aber ob ich auf dem richtigen Weg bin weiß ich nicht.

Wär super, wenn ihr mir helfen könntet!

MfG
mtx

Jester

Willst Du konkret die Punkte haben? Oder willste nur wissen wieviele es sind?

mtx

Ich bräuchte schon die Koordinaten der Punkte bzw. die Indizes des Gitters, wo ich die Punkte finde (kommt ja auf´s selbe raus).

brute force: einen punkt außerhalb des polygons wählen, damit eine linie zu jedem gitterpunkt bilden und deren schnittpunkte mit den kanten des polygons zählen.
ist das ergebnis eine ungerade zahl, liegt der punkt innerhalb des polygons, ansonsten nicht.

pumuckl

Zur Reduzierung des Problems:

Teile konkave Polygone an ihren konkaven Ecken so, dass du eine Menge von (moeglichst grossen) pur konvexen Polygonen erhaelst.
-> Problem reduziert auf konvexe Polynome
Bilde aus jeweils 3 benachbarten Eckpunkten des konvexen Polynoms ein Dreieck und bestimme dessen innere Gitterpunkte. Insgesamt erhaelst du eine Reihe von Gitterpunkten, die nahe den Raendern des Polygons liegen. Alle Punkte, die zwischen diesen Gitterpunkten liegen, liegen ebenfalls innerhalb des Polygons.
-> Problem Reduziert auf Dreiecke.

Fuer n Gitterpunkte muessen fuer Schritt 2) n Dreiecke berechnet werden bzw ihre inneren Punkte. Problematisch wirds, wenn man zwei benachbarte sehr stumpfe Winkel hat, da dann die Dreiecke sehr schmal werden und nicht alle Punkte in Naehe des Rands abgedeckt werden. Dann wird das "zwischen" den erfassten Gitterpunkte nicht mehr ueberall anwendbar.

Alternative zu 2): Sei vorausgesetzt, dass der Abstand der Gitterpunkte kleiner ist als die Kantenlaengen des Polygons.
a) Nehme alle Eckpunkte des Ursprungspolygons. Suche zu jedem die 4 umgebenden Gitterpunkte (oder 8, sollte ein Eckpunkt bereits auf einem Gitterpunkt liegen), und schaue, ob diese sich innerhalb des Polygons befinden. Bilde aus der Menge der so gefundenen inneren Gitterpunkte ein neues Polygon.
b)Betrachte jeden Eckpunkt des Polygons. Wenn die anliegenden Kanten nicht bereits waagerecht oder senkrecht sind, fuehre Schritt a) hierfuer aus, und packe die erhaltenen Gitterpunkte zum Polygon hinzu.
c) wenn am Ende alle Kanten waagerecht oder senkrecht sind, hat man ein Polygon der Gitterpunkte, die am naechsten innen am Ursprungspolygon sind. Dessen innere Punkte zu bestimmen sollte sehr einfach sein.

mtx

hm, danke euch! Das hört sich schon mal gut an! Ich melde mich, wenn´s Schwierigkeiten geben sollte! Vielen Dank!

MfG
mtx

Du könntest einfach einen Scanline Rasterizer anwenden, wie man ihn auch für Grafik benutzt. Die Pixel entsprechen den Gitterpunkten.

Ich weiß wie das geht da gibt es ein standart Testverfahren. Sag mir aber erst wofür du das brauchst.

Hallo zusammen,

ich habe ein ähnliches Problem: Ich habe ein regelmäßiges Gitter, in das ein Polygon gelegt wird. Ich möcht nun wissen, welche Gitterzellen innerhalb des Polygon liegen, da diese in einer Simulation hart sein sollen, während eine Testpartikel sich in den anderen Zellen frei bewegen können soll. Ich habe daher eine Frage zu der Antwort von "brutale kraft": Er schrieb, dass man sich einen Punkt ausserhalb wählen soll, woher weiss ich denn, dass mein Punkt ausserhalb liegt? Noch eine weitere Frage: Hat jemand einen Tip, in welchem Buch oder wo im Netz ich so was nachlesen kann und solche Probleme behandelt werden?

Vielen Dank im Voraus
Gruss
Lodo2209

Für was genau ist das für eine Simualtion ?

CStoll

Lodo2209 schrieb:

Er schrieb, dass man sich einen Punkt ausserhalb wählen soll, woher weiss ich denn, dass mein Punkt ausserhalb liegt?

Du nimmst die Bounding Box des Polygons als Ausgangpunkt und wählst deinen Startpunkt außerhalb davon (alle Kandidaten für innere Punkte liegen auch im Inneren der Bounding Box).

("Testpartikel", das kommt mir irgendwie bekannt vor - was hast du eigentlich vor?)