Punktmenge eines N-Ecks

[BenjaminH]

Hallo,
ich habe folgende Frage, die eigentlich eher etwas Mathematisches ist:
Wie kann ich die Menge der ganzzahligen Punkt eines beliebigen n-Ecks im Koordinatensystem herausbekommen?
Das Problem ist, dass das n-Eck auch konkav sein kann.

Ich hatte die Idee das Problem in zwei Teilprobleme zu zerlegen:

• Ich zerlege das n-Eck in verschiedene Teildreiecke
• und berechne die Punktmenge jedes Teildreiecks

Daraus ergeben sich zwei Fragen (soll ich die in zwei Threads stellen, eigentlich hängen die doch aber zusammen, oder?):

• Gibt es einen Algorithmus zum zerteilen des n-Ecks in dreiecke?(Einfach nur jeden zweiten Punkt mit dem übernächsten verbinden geht nicht, da die n-Ecke ja auch konkav sein können)
• Wie bekomme ich die Menge der Punkte in einem Dreieck?

Vielen Dank!! Benjamin
P.S:Ich speichere die Punkte des N-Ecks in einem Array of TPoint;
[Edit]Das Problem

Zitat von BenjaminH:

Wie bekomme ich die Menge der Punkte in einem Dreieck?

hab ich gelöst: Ich finde die drei Funktionsgleichungen zu den Dreiecksseiten heraus, lege ein Rechteck über das Dreieck und überprüfe jeden ganzzahligen Punkt des Rechtecks, ob er im Dreieck liegt.
Wenn das jemand genauer will soll er sich melden [/Edit]
[Edit=2]Die Koordinaten der Eckpunkte des N-Ecks sind bekannt.

[dizzy]

Ich denke, dass das genau das ist, was du suchst. (C-Code inklusive )
(Das ist dort ohne Zerlegung in Dreiecke gemacht.)

Schönen Gruß,
Fabian

[BenjaminH]

Vielen Dank!
Ich denke, dass ist genau das, was ich will.
Ich werd mir die Seite morgen Mittag ansehen, jetzt mach ich erstmal Hausaufgaben.
Wie hast du das gefunden?

Grüße Benjamin

P.S: Jeah mein 100. Beitrag

[sniper_w]

Ich weiss nicht, ist das was du brauchst...

[BenjaminH]

@sniper_w: Nein, das legt ein Polygon um eine Menge von Punkten, also Punkte € Polygon (Euro als Element misbraucht)
Was ich will ist: If Punkt €Polygon Then
Ohne, dass das Polygon extra um den Punkt herum gelegt wurde
[Edit]Aber die Lösung von dizzy scheint genial zu sein!! Nochmal vielen Dank. Trotzdem auch vielen Dank an dich Sniper, für die Mühe[/Edit]

[dizzy]

Zitat von BenjaminH:

Wie hast du das gefunden?

Nenn es "Erfahrung" . Ich hab mich mal (und werds wieder tun) sehr viel mit Fraktalen und 3D beschäftigt, und bin darüber mal auf die Seite von Paul Bourke gekommen, so mitten im Google-Wühlen. Und da man dort zu sehr vielen mathematischen bzw. geometrischen Problemen sehr schöne und interessante Lösungen findet, dachte ich mir: "Ach guck mal eben, ob da nicht was passendes für den Kollegen bei ist; Der Paul hat ja fast alles."

[sniper_w]

Zitat:

Was ich will ist: If Punkt €Polygon Then

Das dürfte wohl das Richtige sein....Klik