Polygon mit Bresenham "interpolieren"

Hallo,

ich habe eine 3x2 Matrix K gegeben, in welcher pro Zeile je die x und y Koordinate (natürliche Zahlen) eines Punktes steht.
Dann wird ein ausreichendgroße Matrix D voller 0en erstellt, in welche die drei Punkte aus K hinein geschrieben werden, in dem sie die entsprechenden Einträge von
D mit einer 7 auffüllt (7 ist besser zu lesen als 1 finde ich).

Das geht ohne Problem.

Ich möchte nun diese drei Punkte über Geraden zu einem Dreieck verbinden. Dazu möchte ich "den" Bresenham Algorithmus verwenden.
Auch das funktioniert bis an und für sich.

Danach möchte ich das Dreieck mit 7en ausfüllen,also die Matrix D hat dann eine zusammenhängende Fläche aus 7en und der Rest sind 0en.
Der Sinn der Sache ist dann von einer anderen Matrix, nennen wir sie L,die Matrix D zu subtrahieren um alles was in innerhalb des Dreieckes steht zu Löschen (L hat auch nur 0en und 7en).

Nun das Problem:

Da die Geraden,welche die Kanten des Dreieckes beschreiben meistens nicht nur ganzzahlige Werte annehmen, muss der Bresenham Algorithmus runden. Das soll er natürlich auch.
Nur leider rundet er manchmal "auf ", in dem Sinne,dass er einen vom Schwerpunkt des Dreieckes weiterwegliegenden Punkt markiert, sodass beim Füllen das Dreick dann größer gefüllt wird
als es ist. Da aber das Dreick später von L subtrahiert werden soll, wird dann zuviel subtrahiert. Ich will aber weniger subtrahieren.

Wie könnte ich das machen?

Ich versteh die Problematik nicht. Kannst du es vielleicht mal aufzeichnen, was wo dein Problem liegt?
Du hast du doch das Dreieck mittels drei Linien ermittelt. Das Füllen des Dreiecks ist naiv gesehen eine klassische Rekursion.
Du ermittelst einfach den Mittelpunkt des Dreiecks und gehts von dort in jede Richtung, und schaust, ob der Punkt in deinem Dreieck liegt. Wenn ja, dann wird er gefüllt.
"Naiv gesehen" in dem Sinne, da eine Rekursion bei einer gewissen Dreieck-Größe zu einem sog. Stack overlow führen kann.
Dies ist der sog. Floodfill-Algorithmus

Da du aber schon von Rundungsfehlern sprichst, weiß ich nicht mal so ganz, ob du den Bresenham-Algorithmus überhaupt korrekt implementiert hast, denn der Clou ist, dass dieser Algorithmus die Rundungsfehler minimiert.

Du verstehst überhaupt nicht was das Problem ist.

Zunächst sei hier ein Dreieck gezeichnet,so wie es reell aussehen würde. Die roten Linien sollen das Raster sein, in welchem der Algorithmus arbeitet.

Anhang 21508

Nun kommt der Algorithmus zum Einsatz und schaut welche Quadrate am meisten von den Kanten "enthalten". Diese werden dann aufgefüllt und danach wird alles was innerhalb dieser markierten Quadrate liegt aufgefüllt. Wir erhalten

Anhang 21509

Wir sehen,dass das eigentliche Dreieick von einigen gefüllten Quadraten überlapt wird. Dies mag korrekt in dem Sinne sein,dass die Quadrate durch die am meisten von den Kanten durchläuft von Bresenham markiert und gefüllt wurden,jedoch will ich das nur Quadrate die komplettr im Inneren des Dreieckes liegen gefüllt werden. Das müsste dann so aussehen

Anhang 21510

Der Algorithmus soll also gar nicht die Rundungsfehler minimieren,sondern so runden,dass es mir gefällt. Die Idee wäre nun das was Bresenham berechnet als Referenz zu nehmen und dann den Wert ein Stück weiter ins innere des Dreiecks zu korrigieren. Dazu muss man aber wissen,was das Innere des Dreiecks ist.

Siehe http://de.wikipedia.org/wiki/Rasterung_von_Polygonen

Oh danke. Das sieht schon besser aus. Zwar liegt auch nochn bisschen was auf der Kante in den Beispielbildern,aber das kann man theoretisch auch noch durch ne Dritte abziehen und danach löscht man alle negativen Einträge ^ ^