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.