Polygone als Schnittmenge aus Raster und großes Polygon

[joggel]

Hi ho,

mal wieder habe ich es geschafft. Ich habe mich selbst in eine Lage manövriert in der ich nicht weiter weiß.
Es geht um folgendes:
Ich habe ein Raster und in dieses Raster wurde ein Polygon gezeichnet. Jetzt muss ich für jedes Raster ein Polygon extrahieren und zwar anhand wie das große Polygon dann über das Raster liegt.

Hier mal ein Skizze:

Ich muss also für jedes Rastersegment prüfen, ob das Polygon dieses Raster-Segment schneidet. Und dann anhand der Schnittpunkte ein Polygon erzeugen.
Auch die Rastersegmente die im Inneren liegen müssen generiert werden (also es würden dann dabei eben Rechtecke enstehen).

Also als Ausgabe brauche ich eine Liste/Array von Polygonen.

Ich weiß da im Moment irgendwie überhaupt nicht weiter...
Hoffe habe mich einigermaßen verständlich ausgedrückt.

Frage:
Gibt es da einen Algorithmus für so etwas?
Etwas wonach ich suchen könnte?

Gruß


(p.s.: ist leider nicht für den HobbySektor)

[Chromanoid]

Schau mal hier: http://www.cs.man.ac.uk/~toby/gpc/ Ist allerdings nicht frei für kommerzielle Benutzung. Ansonsten http://en.wikipedia.org/wiki/Clipping_( ... _graphics)

Wenn das ganze nicht unbedingt automatisch ablaufen muss, kannst du auch mal Inkscape usw. anschauen und dort die entsprechenden boolschen Operationen ausführen und dann die SVGs in deinem Programm einlesen. Es sollte aber eigentlich auch für kommerzielle Projekte taugliche Bibliotheken geben "boolean operations polygons" sollten dazu gute Stichwörter sein.

[eXile]

Ja, man kann natürlich für jede Rasterzelle einen Sutherland-Hodgman draufhauen. Aber das ist etwas langsam (du hast leider nicht gesagt, wie effizient das sein soll).

Schneller geht's: Wenn alle vier Eckpunkte vollständig im oder vollständig außerhalb des Polygons liegen (schnell testbar via ausgerichteter Polygonkantennormalen), gib eine Nullmenge oder das ganze Rasterzellenrechteck zurück. Wenn die aktuelle Zelle partiell bedeckt ist, einmal Sutherland-Hodgman mit den vier Rasterzellenkanten machen.

[joggel]

Also schnell muss es nicht sein.
Ich möchte mir halt die einzelnen Pixel holen die sich in den Teil-Polygonen befinden. Diese Pixel werden dann weiterverarbeitet.
Ist also nicht allzu zeitkritisch!

[Chromanoid]

Machs doch dann gleich auf Pixelbasis?

[joggel]

Wie meinst Du das?

[Chromanoid]

Naja Polygon in ein großes Bild zeichnen und dann das Bild in kleine Bilder aufteilen. Oder kleine Bilder malen wo immer nur ein Teil des Polygons gerendert wird, das Clipping kann dann ja der Renderer erledigen.

[joggel]

Ne... das kann ich leider so nicht machen, wenn ich dich da richtig verstanden haben.
Mal kurz der Grund:
Ich habe ein großes Bild (bspw: 50000x50000 Pixel).
Der Benutzer markiert darüber ein Polygon.
Nun kann ich aber nicht das ganze Bild laden, sondern eben nur "Raster-weise" (z.B. in Blöcken zu je 1000x1000).
Nun wird intern so ein Block geladen und die Pixel die darin eben durch das große Polygon markiert wurden, sollen weiterverarbeitet werden.
Sie werden aber nicht irgendwie gezeichnet, sondern mit ihnen wird eben Weiteres durchgeführt...

[Chromanoid]

Ich bin mir da nicht sicher, aber ich würde behaupten, dass es schneller ist das Polygon bzw. das invertierte Polygon einfach einmal auf den Bildausschnitt zu klatschen. Wenn du da die GPU benutzen kannst, wäre der Stencil-Buffer/Z-Buffer vielleicht ein geeignetes Mittel.

[joggel]

Ich benutze da leider nicht die GPU.
Der Grund warum ich die Teil-Polygone brauche, ist der das ich den Bereich in den Blöcken brauche, in denen sich die markierten Bildpunkte befinden. Diese Bildpunkte müssen dann zB exportiert werden o.ä.
Mit Grafik hat das leider nix zu tun (obwohl ich das echt toll finden würde ^^).

Was aber zu lange dauern würde, wenn ich jeden Bildpunkt teste, ob er sich in dem großen Polygon befindet.
Deswegen dachte ich mir, ich zerlege das Große Polygon in kleinere die sich in einem geladenen Block befinden.
Dann gehe ich Zeile für Zeile ( Start- und Endpunkte der Zeilen sind dabei die Schnittpunkte der Zeile mit dem Polygonrand ) über den Bild-Block, der sich im Arbeitsspeicher befindet, und hole mir die Bildpunkte und führe mit den dann die gewünschte Funktion aus.

[Alexander Kornrumpf]

Dann gehe ich Zeile für Zeile ( Start- und Endpunkte der Zeilen sind dabei die Schnittpunkte der Zeile mit dem Polygonrand ) über den Bild-Block, der sich im Arbeitsspeicher befindet, und hole mir die Bildpunkte und führe mit den dann die gewünschte Funktion aus.

Um den Anteil der Pixel zu reduzieren, für den du bestimmst ob er im Polyygon liegt oder nicht, musst du das Polygon aber doch gar nicht clippen.

[Chromanoid]

Genau.
Wenn der Polygon extrem viele Punkte hat, verstehe ich dein vorhaben. Ansonsten sollte es einfacher sein pro Bildreihe einfach die unwichtigen/nicht im Block liegenden Start und Endpunkte zu überspringen. Mit dem ray casting sollte es übrigens auch ziemlich unkompliziert möglich sein, das Polygon in dein Grid auf zu teilen. Also Gridreihe für Reihe und dann die Reihen noch mal vertikal pro Spalte.

Ich würde jeden Block in der Bounding Box des Polygons einfach so einmal durchgehen. Ggf. so dass die Start und Endpunkte pro Pixelreihe vor dem Laden aller Blöcke ermittelt werden, dann spart man sich leere Blöcke zu laden...:

Code: Alles auswählen

for (pixelY=imgTop; pixelY<imgBot; pixelY++) {
	nodeX=[];
	//  Build a list of nodes.
	nodes = 0; 
	j = poly.length - 1;					
	for (i=0; i<poly.length; i++) {
		if (poly[i].y<pixelY && poly[j].y>=pixelY ||  poly[j].y< pixelY && poly[i].y>=pixelY) {
			nodeX[nodes++] = Math.round(((poly[i].x + (pixelY - poly[i].y) / (poly[j].y - poly[i].y) * (poly[j].x - poly[i].x)))); 
		}
		j = i; 
	}
	if (invert){
		nodeX.push(imgLeft);
		nodeX.push(imgRight);
		nodes += 2;
	}
	nodeX.sort(Array.NUMERIC);
	//  Fill the pixels between node pairs.
	for (i=0; i<nodes; i+=2) {
		if   (nodeX[i  ] >= imgRight) 
			break;
		if   (nodeX[i+1]> imgLeft ) {
			if (nodeX[i  ] < imgLeft ) 
				nodeX[i  ]=imgLeft ;
			if (nodeX[i + 1] > imgRight) 
				nodeX[i+1]=imgRight;
			for (j = nodeX[i]; j < nodeX[i + 1]; j++) 
				_bmp.setPixel32(j,pixelY,color); 
		}
	}				
}

[joggel]

Ich weiß nicht ob wir vom selben Problem reden...
Ich teile das in Blöcken (Raster/Grid) auf, da eben das gesamte Bild nie im ganzen angezeigt werden kann und auch nicht in den Arbeitsspeicher passt und weil es eben von Grund auf so designd wurde...
Es kann zwar herausgezoomt werden, aber selbst wenn ich da einen Bereich markiere und diese Pixel verarbeiten will, muss ich in die höchste Auflösungsstufe herein und mir die Bilddaten da holen. Deswegen zerlege ich mir das Bild in Blöcke, die eben locker in den Arbeitsspeicher passen...
Dann suche ich mir die Pixel die im, vom Nutzer markierten, Polygon sind.
Ja, ich kann auch jeden Punkt testen ob er im großen Polygon liegt, das wäre jedoch zu sehr Performancelastig... habe es auch schon probiert ;)

@Chromanoid
Deinen Code verstehe ich leider nicht ganz :(

[Alexander Kornrumpf]

Ja, ich kann auch jeden Punkt testen ob er im großen Polygon liegt, das wäre jedoch zu sehr Performancelastig... habe es auch schon probiert

Und wenn du nur die Kanten berücksichtigst, die ganz oder teilweise im jeweiligen Block liegen, ohne sie jedoch zu clippen?

[joggel]

Mist.. so langsam wirds kompliziert ohne Skizze für mich zu verstehen was ihr meint.

Und wenn du nur die Kanten berücksichtigst, die ganz oder teilweise im jeweiligen Block liegen, ohne sie jedoch zu clippen?

Wenn ich nur die Kanten des großen Polygons im jeweiligen Block berücksichtige, dann habe ich doch so ein Polygon was sich eben maximal über den jeweiligen Block erstreckt..

[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!