(Spiele-/Gra...) Algorithmus zum zeichnen eines Polygons (2D)?

Hallo,

vielleicht hat ja jemand die Lösung für meine Frage.

Ich habe einen Folge von (x,y) - Koordinatenpunkten(kartesisches zweidimensionales Koordinatensystem) und möchte daraus ein gefülltes Polygon zeichnen. Der Haken an der Sache ist, das ich nur einzelne Pixel zeichnen kann.

Ich brauche also einen Algorithmus der mir alle Punkte die zum Polygon gehören liefert.
Zudem kann die Anzahl der Koordinatenpunkte/Eckpunkte variieren.

Eigentlich dürfte das ja nicht so schwer sein, wird ja immerhin oft genug gemacht. Allerdings finde ich im Moment keine vernünftige Lösung.

Schon mal vielen Dank für jeden Tip.

MfG Neo

DocJunioR

Du brauchst also einen Linienalgorithmus, der sämtliche Punkte miteinander verbindet und einen Füllalgorithmus, der die Inhalte füllt (man kann auch beides kombinieren.

Also Linienfunktion kannst du etwas in der Art nehmen (einfach aber langsam)

int POL (int A, int B, int Pos)
{ // A ist der Anfang, B das Ende der Linie, Pos der atkuelle Punkt
 return ( A + ((B-A) / Pos) * (B-A));
}

void Line (int Xa, int Ya, int Xb, int Yb, Color Col)
{
 int Nx = Xb - Xa;
 int Ny = Yb - Ya;
 int Count;
  if ( Ny > Nx ) Count = Ny;
  else Count = Nx;

 for (; Count > 0; Count++)
 {
   SetPoint (POL (Xa, Xb, Count), POL (Ya, Yb, Count), Col);
 } 
}

Für den Füllalgorithmus muss Du dir einen Punkt suchen, von dem aus Du (am elegantesten rekursiv ) nach allen richtungen schaust, ob sich die Hintergrundfarbe ändert. Ist dies nicht der Fall, dann wird ein Punkt gesetzt, ansonsten nicht.

cYa
DjR

[ Dieser Beitrag wurde am 11.03.2003 um 08:39 Uhr von DocJunioR editiert. ]

Hallo,

danke für die Antwort.
Das Zeichen der Umrisslinien habe ich mittlerweile hinbekommen.

Der Ansatz beim Füllen die Hintergrundfarbe zu prüfen ist eine gute Idee,
gibt aber Probleme falls der Hintergrund nicht einfarbig ist. Am besten
zeichne ich wohl solang die Punkt, wie die Hintergrundfarbe ungleich der Linienfarbe ist.
Das die Hintergrundfarbe teilweise gleich der Linienfarbe ist schließe ich der
Einfachheit halber mal aus.

MfG Neo

WebFritzi

Naja, IMHO bräuchte man eine Ungleichung, in die man einen Punkt einsetzt. Wenn die Ungleichung dann stimmt, dann ist der Punkt im Polygon, wenn nicht, dann eben nicht. Aber nichtmal mir als Mathematiker ist eine solche Ungleichung bekannt. Ist allerdings auch nicht mein Gebiet.

Super, bin echt beruhigt.
Habs zuerst auch über Ungleichungen versucht, bin da aber kläglich daran gescheitert und hab schon an mir gezweifelt. Vor allem da ich ja Polygone mit unterschiedlich vielen Ecken zeichnen will ist der Ansatz mit den Ungleichungen gar nicht so einfach.

Oder bekommts jemand von Euch hin?

MfG Neo

rüdiger

ich denke, so etwas passt besser in das Grafikprogrammier Forum