Algorithmus zum Füllen von Polygonen

Polygon ist eine geordnete Liste von Scheitelpunkten, wie in der folgenden Abbildung dargestellt. Um Polygone mit bestimmten Farben zu füllen, müssen Sie die Pixel bestimmen, die auf den Rand des Polygons fallen, und diejenigen, die in das Polygon fallen. In diesem Kapitel werden wir sehen, wie wir Polygone mit verschiedenen Techniken füllen können.

Scan Line Algorithmus

Dieser Algorithmus schneidet die Scanlinie mit Polygonkanten und füllt das Polygon zwischen Schnittpaaren. Die folgenden Schritte zeigen, wie dieser Algorithmus funktioniert.

Step 1 - Ermitteln Sie Ymin und Ymax aus dem angegebenen Polygon.

Step 2- ScanLine schneidet mit jeder Kante des Polygons von Ymin nach Ymax. Benennen Sie jeden Schnittpunkt des Polygons. Gemäß der oben gezeigten Figur werden sie als p0, p1, p2, p3 bezeichnet.

Step 3 - Sortieren Sie den Schnittpunkt in aufsteigender Reihenfolge der X-Koordinaten, dh (p0, p1), (p1, p2) und (p2, p3).

Step 4 - Füllen Sie alle Koordinatenpaare innerhalb der Polygone aus und ignorieren Sie die alternativen Paare.

Hochwasserfüllalgorithmus

Manchmal stoßen wir auf ein Objekt, bei dem wir den Bereich und seine Grenze mit verschiedenen Farben füllen möchten. Wir können solche Objekte mit einer bestimmten Innenfarbe malen, anstatt nach einer bestimmten Grenzfarbe wie beim Grenzfüllungsalgorithmus zu suchen.

Anstatt sich auf die Grenze des Objekts zu verlassen, stützt es sich auf die Füllfarbe. Mit anderen Worten, es ersetzt die Innenfarbe des Objekts durch die Füllfarbe. Wenn keine Pixel mehr der ursprünglichen Innenfarbe vorhanden sind, ist der Algorithmus abgeschlossen.

Wiederum basiert dieser Algorithmus auf der Four-Connect- oder Eight-Connect-Methode zum Ausfüllen der Pixel. Anstatt nach der Grenzfarbe zu suchen, werden alle benachbarten Pixel gesucht, die Teil des Innenraums sind.

Grenzfüllungsalgorithmus

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 Objekts erreicht. Die Farbe der Grenze und die Farbe, die wir füllen, sollten unterschiedlich sein, damit dieser Algorithmus funktioniert.

In diesem Algorithmus nehmen wir an, dass die Farbe der Grenze für das gesamte Objekt gleich ist. Der Grenzfüllungsalgorithmus kann durch 4 verbundene Pixel oder 8 verbundene Pixel implementiert werden.

4-verbundenes Polygon

Bei dieser Technik werden 4 verbundene Pixel verwendet, wie in der Figur gezeigt. Wir platzieren die Pixel über, unter, rechts und links von den aktuellen Pixeln. Dieser Vorgang wird fortgesetzt, bis wir eine Grenze mit einer anderen Farbe finden.

Algorithmus

Step 1 - Initialisieren Sie den Wert von Seed Point (Seedx, Seedy), Fcolor und Dcol.

Step 2 - Definieren Sie die Grenzwerte des Polygons.

Step 3 - Überprüfen Sie, ob der aktuelle Startpunkt die Standardfarbe hat, und wiederholen Sie die Schritte 4 und 5, bis die Grenzpixel erreicht sind.

If getpixel(x, y) = dcol then repeat step 4 and 5

Step 4 - Ändern Sie die Standardfarbe mit der Füllfarbe am Startpunkt.

setPixel(seedx, seedy, fcol)

Step 5 - Folgen Sie dem Verfahren rekursiv mit vier Nachbarschaftspunkten.

FloodFill (seedx – 1, seedy, fcol, dcol)
FloodFill (seedx + 1, seedy, fcol, dcol)
FloodFill (seedx, seedy - 1, fcol, dcol)
FloodFill (seedx – 1, seedy + 1, fcol, dcol)

Step 6 - Beenden

Bei dieser Technik gibt es ein Problem. Betrachten Sie den unten gezeigten Fall, in dem wir versucht haben, die gesamte Region zu füllen. Hier wird das Bild nur teilweise ausgefüllt. In solchen Fällen kann die 4-verbundene Pixel-Technik nicht verwendet werden.

8-verbundenes Polygon

Bei dieser Technik werden 8 verbundene Pixel verwendet, wie in der Figur gezeigt. Wir platzieren Pixel über, unter, rechts und links von den aktuellen Pixeln, wie wir es in 4-verbundener Technik getan haben.

Darüber hinaus setzen wir Pixel in Diagonalen, sodass der gesamte Bereich des aktuellen Pixels abgedeckt wird. Dieser Prozess wird fortgesetzt, bis wir eine Grenze mit einer anderen Farbe finden.

Algorithmus

Step 1 - Initialisieren Sie den Wert von Seed Point (Seedx, Seedy), Fcolor und Dcol.

Step 2 - Definieren Sie die Grenzwerte des Polygons.

Step 3 - Überprüfen Sie, ob der aktuelle Startpunkt die Standardfarbe hat, und wiederholen Sie die Schritte 4 und 5, bis die Grenzpixel erreicht sind

If getpixel(x,y) = dcol then repeat step 4 and 5

Step 4 - Ändern Sie die Standardfarbe mit der Füllfarbe am Startpunkt.

setPixel(seedx, seedy, fcol)

Step 5 - Folgen Sie dem Verfahren rekursiv mit vier Nachbarschaftspunkten

FloodFill (seedx – 1, seedy, fcol, dcol)
FloodFill (seedx + 1, seedy, fcol, dcol)
FloodFill (seedx, seedy - 1, fcol, dcol)
FloodFill (seedx, seedy + 1, fcol, dcol)
FloodFill (seedx – 1, seedy + 1, fcol, dcol)
FloodFill (seedx + 1, seedy + 1, fcol, dcol)
FloodFill (seedx + 1, seedy - 1, fcol, dcol)
FloodFill (seedx – 1, seedy - 1, fcol, dcol)

Step 6 - Beenden

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

Innen-Außen-Test

Diese Methode ist auch bekannt als counting number method. Beim Füllen eines Objekts müssen wir häufig 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 oder außerhalb eines Objekts befindet.

Ungerade-Gerade-Regel
Wicklungsnummernregel ungleich Null

Ungerade-Gerade-Regel

Bei dieser Technik zählen wir den Kantenübergang entlang der Linie von einem beliebigen Punkt (x, y) bis unendlich. Wenn die Anzahl der Wechselwirkungen ungerade ist, ist der Punkt (x, y) ein innerer Punkt; und wenn die Anzahl der Wechselwirkungen gerade ist, dann ist der Punkt (x, y) ein äußerer Punkt. Das folgende Beispiel zeigt dieses Konzept.

Aus der obigen Abbildung können wir ersehen, dass ab dem Punkt (x, y) die Anzahl der Interaktionspunkte auf der linken Seite 5 und auf der rechten Seite 3 beträgt. An beiden Enden ist die Anzahl der Interaktionspunkte ungerade Der Punkt wird innerhalb des Objekts berücksichtigt.

Wicklungsnummernregel ungleich Null

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

Wenn alle Kanten des Polygons vom Gummiband bedeckt sind, überprüfen Sie den Stift, der an der zu testenden Stelle befestigt wurde. Wenn wir mindestens einen Wind am Punkt finden, betrachten Sie ihn innerhalb des Polygons, andernfalls können wir sagen, dass der Punkt nicht innerhalb des Polygons liegt.

Geben Sie bei einer anderen alternativen Methode allen Kanten des Polygons Anweisungen. Zeichnen Sie eine Scanlinie vom zu testenden Punkt ganz links in der X-Richtung.

Geben Sie allen Kanten, die nach oben weisen, den Wert 1 und allen anderen -1 den Wert als Richtungswert.
Überprüfen Sie die Kantenrichtungswerte, von denen die Scanlinie verläuft, und fassen Sie sie zusammen.
Wenn die Gesamtsumme dieses Richtungswerts ungleich Null ist, ist dieser zu testende Punkt ein interior point, sonst ist es ein exterior point.
In der obigen Abbildung fassen wir die Richtungswerte zusammen, aus denen die Scanlinie verläuft, dann beträgt die Summe 1 - 1 + 1 = 1; das ist nicht Null. Der Punkt soll also ein innerer Punkt sein.