Polygone als Schnittmenge aus Raster und großes Polygon
Forumsregeln
Wenn das Problem mit einer Programmiersprache direkt zusammenhängt, bitte HIER posten.
Wenn das Problem mit einer Programmiersprache direkt zusammenhängt, bitte HIER posten.
- Chromanoid
- Moderator
- Beiträge: 4260
- Registriert: 16.10.2002, 19:39
- Echter Name: Christian Kulenkampff
- Wohnort: Lüneburg
Re: Polygone als Schnittmenge aus Raster und großes Polygon
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
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
Zuletzt geändert von Chromanoid am 09.11.2011, 17:23, insgesamt 1-mal geändert.
Re: Polygone als Schnittmenge aus Raster und großes Polygon
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.
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
- Moderator
- Beiträge: 4260
- Registriert: 16.10.2002, 19:39
- Echter Name: Christian Kulenkampff
- Wohnort: Lüneburg
Re: Polygone als Schnittmenge aus Raster und großes Polygon
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.
Koordinaten wären dann in Blockkoordinaten.
Zuletzt geändert von Chromanoid am 09.11.2011, 17:38, insgesamt 3-mal geändert.
Re: Polygone als Schnittmenge aus Raster und großes Polygon
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)
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);
Zuletzt geändert von joggel am 09.11.2011, 17:38, insgesamt 1-mal geändert.
- Chromanoid
- Moderator
- Beiträge: 4260
- Registriert: 16.10.2002, 19:39
- Echter Name: Christian Kulenkampff
- Wohnort: Lüneburg
Re: Polygone als Schnittmenge aus Raster und großes Polygon
Viel Erfolg! und berichte mal ob das ganze tatsächlich für so riesige Bilder ganz gut funktioniert hat :)
Re: Polygone als Schnittmenge aus Raster und großes Polygon
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.
Das mit den riesigen Bildern ist ja nur so ein Wenn-Fall.
Solche riesigen gibt es kaum, soll aber eben unterstützt werden.
Re: Polygone als Schnittmenge aus Raster und großes Polygon
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
- Establishment
- Beiträge: 1734
- Registriert: 06.03.2004, 18:10
- Echter Name: Michael Kenzel
- Kontaktdaten:
Re: Polygone als Schnittmenge aus Raster und großes Polygon
Wenn du das Polygon rasterisieren willst, zerlegs einfach in Dreiecke und fertig!?
- Chromanoid
- Moderator
- Beiträge: 4260
- Registriert: 16.10.2002, 19:39
- Echter Name: Christian Kulenkampff
- Wohnort: Lüneburg
Re: Polygone als Schnittmenge aus Raster und großes Polygon
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
- Establishment
- Beiträge: 1734
- Registriert: 06.03.2004, 18:10
- Echter Name: Michael Kenzel
- Kontaktdaten:
Re: Polygone als Schnittmenge aus Raster und großes Polygon
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 ;)
Man könnte das Polygon auch nur in irgendwie konvexe Unterpolygone zerteilen, dann gibt es immer nur 2 Kanten. Nur so ein paar Ideen ;)
Re: Polygone als Schnittmenge aus Raster und großes Polygon
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!
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!