Füllen eines Polygons

[Firefall]

Habe schon die Boardsuche verwendet und bin auf das gestossen: http://www.coding-board.de/board/showthread.php?t=12594&highlight=polygon
Das scheint allerdings mein Problem nicht zu lösen. Ich habe schon die Methode mit den Scanlines im Netz gesehen, die mir eigentlich sehr gefällt, das Problem sidn nur die Eckpunkte. Selbst wenn ich die gegeben hätte, könnte es doch z.b. folgendes Polygon geben: #
#
# #
# #
# #
#####Wenn man das von oben nach unten durchläuft wird die Linie in der Mitte doch weiss bleiben??? Könnt ihr mir da auf die Sprünge helfen? Das ganze soll für alle Polygone funktionieren und im Idealfall sind die Eckpunkte nicht bekannt sondern nur die Koordinaten der Punkte, die die Kontur bilden.

[gencha]

Naja, dann zeichnest du in Schritt 1 die Kanten mit Hilfe von Bresenham und dann gehst du wie schon erwähnt jede Zeile durch.
Triffst du auf einen schon gefüllten Pixel, dann ist der nächste (wenn er nicht auch gefüllt ist) innerhalb des Polygons. Also kannst du ihn füllen. Wenn du jetzt wieder auf einen gefüllten triffst, dann ist der nächste wieder ausserhalb des Polygons und wird daher nicht gefüllt.
Also da kann eigentlich nix schief gehn :P
Mal abgesehn von Überlappungen...

[Firefall]

Naja, dann zeichnest du in Schritt 1 die Kanten mit Hilfe von Bresenham und dann gehst du wie schon erwähnt jede Zeile durch.
Triffst du auf einen schon gefüllten Pixel, dann ist der nächste (wenn er nicht auch gefüllt ist) innerhalb des Polygons. Also kannst du ihn füllen. Wenn du jetzt wieder auf einen gefüllten triffst, dann ist der nächste wieder ausserhalb des Polygons und wird daher nicht gefüllt.
Also da kann eigentlich nix schief gehn :P
Mal abgesehn von Überlappungen...
Also quasi:
1. switch = false
2. X=1 (Respektive 0)
3. Ist switch = true, dann fülle Pixel X.
4. Ist Pixel X gefüllt und Pixel X + 1 nicht, dann führe eine Not-Operation mit switch durch
5. Erhöhe X und gehe zu 3
???
Dann bleibt das Problem, wenn nur ein Punkt auf einer Scanline leigt, nämlich eine Ecke, oder?
Gibt's auch noch ne Möglichkeit für die Überlappungen?

[gencha]

Wenn ich jetz nix falsch gemacht habe, dann sollte es wohl so in diese Richtung gehn:
unsigned char* pBitmap = ...;
unsigned int uiLength = 1024;
bool bInsidePolygon = false;
while ( uiLength-- ) {
if ( *pBitmap == 1 ) bInsidePolygon = !bInsidePolygon;
if ( bInsidePolygon ) *pBitmap = 1;
pBitmap++;
}

[Firefall]

Wenn ich jetz nix falsch gemacht habe, dann sollte es wohl so in diese Richtung gehn:
unsigned char* pBitmap = ...;
unsigned int uiLength = 1024;
bool bInsidePolygon = false;
while ( uiLength-- ) {
if ( *pBitmap == 1 ) bInsidePolygon = !bInsidePolygon;
if ( bInsidePolygon ) *pBitmap = 1;
pBitmap++;
}
Nimm ein Quadrat und rotiere es um 45°. Dann wird am höchsten Punkt dieses Quadrats ein einzelner Pixel sein. Deine Routine würde dann bei diesem Pixel mit Zeichnen beginnen - und nie damit aufhören.

[gencha]

...das ist natürlich wahr. Dumme Sache :D
Ja dann bleiben halt nur wieder "kompliziertere" Lösungen. So wie in dem anderen Beitrag besprochen. Muss man dann halt errechnen ob sich ein Pixel innerhalb des Polygons befindet.
Aber das geht ja ähnlich, wie dort beschrieben.

[Firefall]

...das ist natürlich wahr. Dumme Sache :D
Ja dann bleiben halt nur wieder "kompliziertere" Lösungen. So wie in dem anderen Beitrag besprochen. Muss man dann halt errechnen ob sich ein Pixel innerhalb des Polygons befindet.
Aber das geht ja ähnlich, wie dort beschrieben.
Geht das genauer? Eine Art Pseudocode wäre sehr hilfreich!

[Firefall]

Ich habe die Lösung... Man muss mit den Kanten arbeiten. Genauere Beschreibung möchte ich mir sparen, verstehe selbst noch nicht alles. Google Suche nach "Active Edge Table" sollte das Thema näher bringen ;)

[Jan Krüger]

Dann wird am höchsten Punkt dieses Quadrats ein einzelner Pixel sein. Deine Routine würde dann bei diesem Pixel mit Zeichnen beginnen - und nie damit aufhören.
Dann lässt du wohl besser alle Zeilen weg, in denen sich nur ein Pixel befindet.

[Firefall]

Dann lässt du wohl besser alle Zeilen weg, in denen sich nur ein Pixel befindet.Würde auch nicht klappen, wenn man so eine Form hätte:

/\
/\/ \
|_____|Beim rechten Berg würde dann auf der Höhe der Spitze des linken Bergs eine Linie fehlen. Wenn man nun ein Polygon so konstruiert, dass der linke Berg nur eine Linie ist, gibt das eine Katastrophe ;) Aber wie gesagt, eine richtige Lösung existiert.