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_( ... r_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: Ansicht erweitern :: 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..