Einsteigerguide: Der Polygon Filling Algorithmus

Ein Polygon ist eine geordnete Liste von Nodes, wie in der folgenden Abbildung dargestellt:

Um Polygone mit bestimmten Farben zu füllen, müssen Sie bestimmen, welche Pixel auf den Rand des Polygons fallen und welche innerhalb des Polygons liegen. In diesem Beitrag werden wir sehen, wie wir Polygone mit verschiedenen Techniken füllen können.

Scanline Algorithmus.

Dieser Algorithmus arbeitet mit einer Schnittlinie mit Polygonkanten und füllt das Polygon zwischen Paaren von Schnittpunkten. Die folgenden Schritte zeigen, wie dieser Algorithmus funktioniert.

Schritt 1: Ermitteln Sie Ymin und Ymax aus dem angegebenen Polygon.

Schritt 2 – Die Scanline schneidet sich mit jeder Kante des Polygons von Ymin bis Ymax. Benennen Sie jeden Schnittpunkt des Polygons. Wie in der obigen Abbildung dargestellt,können Sie sie als p0, p1, p2, p3 bezeichnen.

Schritt 3 – Sortieren Sie den Schnittpunkt in der zunehmenden Reihenfolge der X-Koordinate, d.h. (p0, p1), (p1, p2) und (p2, p3).

Schritt 4 – Füllen Sie alle Koordinatenpaare, die sich innerhalb von Polygonen befinden und ignorieren Sie die alternativen Paare.

Flood Fill Algorithmus.

Manchmal stoßen wir auf ein Objekt, bei dem wir den Bereich und seine Grenze mit verschiedenen Farben füllen wollen. Wir können solche Objekte mit einer bestimmten Innenfarbe malen, anstatt nach einer bestimmten Randfarbe zu suchen, wie im Boundary Filling Algorithmus.

Anstatt sich auf die Grenze des Objekts zu verlassen, verlässt es sich auf die Füllfarbe. Mit anderen Worten, es setzt die Innenfarbe des Objekts durch die Füllfarbe. Wenn keine Pixel mehr von der ursprünglichen Innenfarbe existieren, ist der Algorithmus abgeschlossen.

Auch dieser Algorithmus basiert auf dem Four-Connect oder Eight-Connect-Verfahren zum Ausfüllen der Pixel. Aber anstatt nach der Randfarbe zu suchen, sucht es nach allen benachbarten Pixeln, die Teil des Innenraums sind.

Boundary Fill Algorithmus.

Der Boundary Fill Algorithmus arbeitet als Name. Dieser Algorithmus wählt einen Punkt innerhalb eines Objekts aus und beginnt zu füllen, bis er die Grenze des Objektes erreicht. Die Farbe der Grenze und die Farbe, die wir füllen, sollten unterschiedlich sein, damit dieser Algorithmus funktioniert.

In diesem Algorithmus gehen wir davon aus, dass die Farbe der Grenze für das gesamte Objekt gleich ist. Der Boundary Fill Algorithmus kann durch 4 verbundene Pixel oder 8 verbundene Pixel implementiert werden.

4-fach verbundenes Polygon.

Bei dieser Technik werden 4-fach verbundene Pixel verwendet, wie in der Abbildung dargestellt. Wir setzen die Pixel über, unter, rechts oder links der aktuellen Pixel und dieser Prozess wird fortgesetzt, bis wir eine Grenze mit unterschiedlicher Farbe finden.

Algorithmus.

Schritt 1 – Initialisieren Sie den Wert vom Seed Point (seedx, seedy), fcolor und dcol.

Schritt 2 – Definieren Sie die Grenzwerte des Polygons.

Schritt 3 – Überprüfen Sie, ob der aktuelle Seed Point die Standardfarbe hat und wiederholen Sie anschließend die Schritte 4 und 5, bis die Randpixel erreicht sind.

Schritt 4 – Ändern Sie die Standardfarbe mit der Füllfarbe im Seed Point.

Schritt 5 – befolgen Sie rekursiv das Verfahren mit vier Nachbarschaftspunkten.

Schritt 6 – Exit.

Es gibt ein Problem mit dieser Technik. Betrachten Sie den Fall wie unten gezeigt, bei dem wir versucht haben, die gesamte Fläche zu befüllen. Hier wird das Bild nur teilweise ausgefüllt. In solchen Fällen kann die Technik der 4 verbundenen Pixel nicht verwendet werden.

8-fach verbundene Polygone.

Bei dieser Technik werden 8 verbundene Pixel verwendet. Wir setzen Pixel über und unter sowie der rechten und linken Seite der aktuellen Pixel, wie wir es bei der 4-fachen Verbindungstechnik getan haben.

Darüber hinaus setzen wir Pixel auch in der Diagonalen, so dass der gesamte Bereich des aktuellen Pixels abgedeckt wird. Dieser Prozess wird so lange fortgesetzt, bis wir eine Grenze mit unterschiedlicher Farbe finden.

Algorithmus.

Schritt 1 – Initialisieren Sie den Wert von Seed Point (seedx, seedy), fcolor und dcol.

Schritt 2 – Definieren Sie die Randwerte des Polygons.

Schritt 3 – Überprüfen Sie, ob der aktuelle Seed Point die Standardfarbe hat und wiederholen Sie anschließend die Schritte 4 und 5, bis die Randpixel erreicht sind.

Schritt 4 – Ändern Sie die Standardfarbe mit der Füllfarbe an dem Seed Point.

Schritt 5 – Befolgen Sie rekursiv das Verfahren mit vier Nachbarschaftspunkten.

Schritt 6 – Exit.

Die 4-fach verbundene Pixeltechnik konnte den in der folgenden Abbildung markierten Bereich nicht ausfüllen, was bei der 8-fach verbundenen Technik nicht der Fall ist.

Inside-Outside-Test.

Diese Methode wird auch als Counting Number Methode bezeichnet. Beim Füllen eines Objekts müssen wir oft feststellen, ob sich ein bestimmter Punkt innerhalb oder außerhalb des Objekts befindet. Es gibt zwei Methoden, mit denen wir feststellen können, ob sich ein bestimmter Punkt innerhalb eines Objekts oder außerhalb befindet:

• Regel für ungerade Fälle
• und die Nonzero Winding Number Rule.

Regel für ungerade Fälle.

Bei dieser Technik werden wir den Kantenübergang entlang der Linie von jedem Punkt (x, y) bis unendlich zählen. Wenn die Anzahl der Interaktionen ungerade ist, dann ist der Punkt (x, y) ein interner Punkt und wenn die Anzahl der Interaktionen gerade ist, dann ist der Punkt (x, y) ein externer Punkt. Das folgende Beispiel veranschaulicht dieses Konzept:

Aus der obigen Abbildung können wir erkennen, dass aus dem Punkt (x, y) die Anzahl der Interaktionspunkte auf der linken Seite 5 und auf der rechten Seite 3 beträgt, während von beiden Seiten die Anzahl der Interaktionspunkte ungerade ist, so dass der Punkt innerhalb des Objekts betrachtet wird.

Nonzero Winding Number Rule.

Diese Methode wird auch bei den einfachen Polygonen verwendet, um zu testen, ob der angegebene Punkt innen liegt oder nicht. Es kann mit Hilfe einer Nadel und eines Gummibandes einfach verstanden werden. Befestigen Sie den Stift an einer der Kanten des Polygons und binden Sie das Gummiband darin fest und dehnen Sie das Gummiband anschließend entlang der Kanten des Polygons.

Wenn alle Kanten des Polygons mit dem Gummiband bedeckt sind, überprüfen Sie den Stift, der an der zu prüfenden Stelle befestigt wurde. Wenn wir mindestens einen Wind an dem Punkt finden, betrachten wir diesen innerhalb des Polygons, sonst können wir sagen, dass der Punkt nicht innerhalb des Polygons liegt.

In einer anderen, alternativen Methode geben Sie Richtungen für alle Kanten des Polygons vor. Zeichnen Sie eine Scanline vom zu prüfenden Punkt in die linke Richtung von der X-Richtung aus.

• Vergeben Sie einen Wert 1 an alle Kanten, die nach oben gehen, und alle anderen -1 als Richtungswerte an.
• Überprüfen Sie die Kantenrichtungswerte, die die Scanline durchlaufen und fassen Sie sie zusammen.
• Wenn die Gesamtsumme dieses Richtungswertes ungleich 0 ist, dann ist dieser zu prüfende Punkt ein Innenpunkt, ansonsten ein Außenpunkt.
• In der obigen Abbildung summieren wir die Richtungswerte, die die Scanline durchlaufen, dann ist die Summe 1-1+1 = 1, also ungleich 0. Der Punkt soll also ein innerer Punkt sein.

Wir hoffen, dass wir Ihnen einen guten Einstieg in den Polygon Fill Algorithmus bieten konnten. Wenn Sie noch Fragen oder Anregungen haben sollten, können Sie sich sehr gerne mit unseren Fachexperten in unserem Forum austauschen.

Vielen Dank für Ihren Besuch.