Polygone als Schnittmenge aus Raster und großes Polygon

[Chromanoid]

Wir reden vom selben Problem.
1. finde die Bounding Box des polygons.
2. Array für jede Pixelzeile einer Reihe im Blockgrid anlegen. Wenn die Blöcke 1000px hoch sind, dann sind das vielleicht 1000x128x4byte (1000 Reihen, max. vielleicht 128 Schnittpunkte pro Reihe mit dem Polygon (was ich schon ziemlich viel finde), und 4byte pro X Stelle des Schnittpunktes in dieser Reihe). (Versatz zwischen oberer Blockkante und höchsten Punkt im Polygon kann man evt. auch noch speichern.)
3. Pro Reihe jede Linie des Polygons durchgehen und die X-Koordinaten der Schnittpunkte speichern und sortieren.
4. Jeden Block in dieser Reihe der Blockgrids nacheinander durchgehen und die Start- und Endstellen pro Zeile durchgehen und die entsprechenden Pixel dazwischen kopieren/verarbeiten.
. Beim Durchgehen kannst du dir gleich noch merken ab welchem Index im Start-Endstellen Array der nächste Block die Punkte überprüfen muss.

Siehe auch http://en.wikipedia.org/wiki/Point_in_p ... _algorithm oder http://www.cs.rit.edu/~icss571/filling/how_to.html

[joggel]

Aaahhh... ich beginne zu verstehen :)...

Angenommen ich taste jetzt Zeile für Zeile das Polygon ab, und ermittel mir immer Linien (definert durch Start und Enpunkt) in denen ich die Pixel auslesen kann. Was ist nun wenn sich der StartPunkt einer Linie in einem anderen Block befindet als der Enpunkt...

Deswegen wollte ich eben das Polygon zerlegen, und innerhalb dieser kleineren Polygone so eine Suche durchführen.

[Chromanoid]

Deswegen wäre es sinnvoll die Schnittpunkte einmal gleich am Anfang für eine ganze Blockreihe zu speichern. Wenn sich der Endpunkt im anderen Block befindet, dann kopierst du eben nur bis zum Ende des Blocks. Also sowas copyPixels(max(x0,0),y,min(x1,blockbreite),y)
Koordinaten wären dann in Blockkoordinaten.

[joggel]

Okay. Danke für Eure Mühe.
Werde mal schauen wie ich das dann umsetze.

Also, wie ich das auch in mein Design umsetze.
Weil ich habe das in etwa bisher so gemacht:
(Oder so wollte ich es machen)

Code: Alles auswählen

//läd aus dem Bild ein Block und macht was damit
bild->doSomethingWithIt( Block aBlock, Polygon aTeilPolygon, PixelFunction aFunction);

[Chromanoid]

Viel Erfolg! und berichte mal ob das ganze tatsächlich für so riesige Bilder ganz gut funktioniert hat :)

[joggel]

Ja, ich werde berichten wie ich es dann tatsächlich umgesetzt habe...
Das mit den riesigen Bildern ist ja nur so ein Wenn-Fall.
Solche riesigen gibt es kaum, soll aber eben unterstützt werden.

[EyDu]

Zu Punkt 3 (Pro Reihe jede Linie des Polygons durchgehen und die X-Koordinaten der Schnittpunkte speichern und sortieren.): Das kann man noch beschleunigen, indem man die Eckpunkte des Polygons vertikal sortiert und dann von oben nach unten durchläuft. Dann muss nicht jede Zeile neu gesucht werden, sondern nur, wenn ein neuer Punkt erreicht wird.

[dot]

Wenn du das Polygon rasterisieren willst, zerlegs einfach in Dreiecke und fertig!?

[Chromanoid]

Weiß nicht ob triangulieren und rasterisieren schneller als die Scanline-Methode ist, wenn man nur die CPU benutzt. Gerade mit der von EyDu erwähnten Optimierung...

[dot]

Ich denk das hängt von der Komplexität der Kontur ab. Bei der allgemeinen Scanline-Rasterisierung musst du halt in einer inneren Schleife Listen von Kanten verwalten...Müsste man natürlich profilen...

Man könnte das Polygon auch nur in irgendwie konvexe Unterpolygone zerteilen, dann gibt es immer nur 2 Kanten. Nur so ein paar Ideen ;)

[joggel]

Sooo... juhu!!
Funktioniert wie es soll! :)
Geschwindigkeit ist auch akzeptabel.
Kann das nur so Ausdrücken, da eine Zeitangabe für den ganzen Vorgang ja auch nix konkretes darüber aussagt, wie schnell das Finden der Punkte im Polygon ist.

Habe das jetzt auch nicht sonderlich optimiert.
Bin wie folgt vorgegangen.
1) einen std::vector<Linie2D> mit Inhalt der Scanlinien für den jeweilige Block im Bild erstellt
2) in der anderen Fkt. dann über den std::vector drüberiteriert und von Start- bis End-Punkt der jeweiligen Linie alle enthaltenen Bildpunkte verarbeitet!