Algoritmo de relleno de polígono
Polígono es una lista ordenada de vértices como se muestra en la siguiente figura. Para rellenar polígonos con colores particulares, debe determinar los píxeles que caen en el borde del polígono y los que caen dentro del polígono. En este capítulo, veremos cómo podemos rellenar polígonos utilizando diferentes técnicas.
Algoritmo de línea de exploración
Este algoritmo funciona mediante la intersección de la línea de exploración con los bordes del polígono y llena el polígono entre pares de intersecciones. Los siguientes pasos describen cómo funciona este algoritmo.
Step 1 - Descubra Ymin e Ymax del polígono dado.
Step 2- ScanLine se cruza con cada borde del polígono desde Ymin hasta Ymax. Nombra cada punto de intersección del polígono. Según la figura que se muestra arriba, se denominan p0, p1, p2, p3.
Step 3 - Ordene el punto de intersección en el orden creciente de la coordenada X, es decir, (p0, p1), (p1, p2) y (p2, p3).
Step 4 - Rellena todos esos pares de coordenadas que están dentro de polígonos e ignora los pares alternos.
Algoritmo de relleno por inundación
A veces nos encontramos con un objeto en el que queremos rellenar el área y su límite con diferentes colores. Podemos pintar tales objetos con un color interior específico en lugar de buscar un color de límite particular como en el algoritmo de relleno de límites.
En lugar de depender del límite del objeto, se basa en el color de relleno. En otras palabras, reemplaza el color interior del objeto con el color de relleno. Cuando ya no existen más píxeles del color interior original, se completa el algoritmo.
Una vez más, este algoritmo se basa en el método de cuatro conexiones o ocho conexiones para rellenar los píxeles. Pero en lugar de buscar el color del límite, busca todos los píxeles adyacentes que forman parte del interior.
Algoritmo de relleno de límites
El algoritmo de relleno de límites funciona como su nombre. Este algoritmo selecciona un punto dentro de un objeto y comienza a llenarse hasta que llega al límite del objeto. El color del límite y el color que rellenamos deben ser diferentes para que este algoritmo funcione.
En este algoritmo, asumimos que el color del límite es el mismo para todo el objeto. El algoritmo de relleno de límites se puede implementar mediante 4 píxeles conectados u 8 píxeles conectados.
Polígono 4 conectados
En esta técnica se utilizan 4 píxeles conectados como se muestra en la figura. Estamos poniendo los píxeles arriba, abajo, a la derecha y al lado izquierdo de los píxeles actuales y este proceso continuará hasta que encontremos un límite con un color diferente.
Algoritmo
Step 1 - Inicializar el valor del punto de semilla (seedx, seedy), fcolor y dcol.
Step 2 - Definir los valores de los límites del polígono.
Step 3 - Verifique si el punto de semilla actual es del color predeterminado, luego repita los pasos 4 y 5 hasta alcanzar los píxeles del límite.
If getpixel(x, y) = dcol then repeat step 4 and 5Step 4 - Cambie el color predeterminado con el color de relleno en el punto inicial.
setPixel(seedx, seedy, fcol)Step 5 - Seguir de forma recursiva el procedimiento con cuatro puntos de vecindad.
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 - Salir
Hay un problema con esta técnica. Considere el caso que se muestra a continuación donde intentamos llenar toda la región. Aquí, la imagen se llena solo parcialmente. En tales casos, no se puede utilizar la técnica de 4 píxeles conectados.
Polígono de 8 conectados
En esta técnica se utilizan 8 píxeles conectados como se muestra en la figura. Estamos colocando píxeles arriba, abajo, lado derecho e izquierdo de los píxeles actuales como lo estábamos haciendo en la técnica de 4 conectados.
Además de esto, también colocamos píxeles en diagonales para cubrir el área completa del píxel actual. Este proceso continuará hasta que encontremos un límite con diferente color.
Algoritmo
Step 1 - Inicializar el valor del punto de semilla (seedx, seedy), fcolor y dcol.
Step 2 - Definir los valores de los límites del polígono.
Step 3 - Verifique si el punto de semilla actual es del color predeterminado y luego repita los pasos 4 y 5 hasta que se alcancen los píxeles de límite
If getpixel(x,y) = dcol then repeat step 4 and 5Step 4 - Cambie el color predeterminado con el color de relleno en el punto inicial.
setPixel(seedx, seedy, fcol)Step 5 - Seguir de forma recursiva el procedimiento con cuatro puntos vecinos
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 - Salir
La técnica de 4 píxeles conectados no logró llenar el área marcada en la siguiente figura, lo que no sucederá con la técnica de 8 conectados.
Prueba interior-exterior
Este método también se conoce como counting number method. Mientras llenamos un objeto, a menudo necesitamos identificar si un punto en particular está dentro o fuera del objeto. Hay dos métodos mediante los cuales podemos identificar si un punto en particular está dentro o fuera de un objeto.
- Regla de pares impares
- Regla de número de bobinado distinto de cero
Regla de pares impares
En esta técnica, contaremos el borde que cruza la línea desde cualquier punto (x, y) hasta el infinito. Si el número de interacciones es impar, entonces el punto (x, y) es un punto interior; y si el número de interacciones es par, entonces el punto (x, y) es un punto exterior. El siguiente ejemplo describe este concepto.
De la figura anterior, podemos ver que desde el punto (x, y), el número de puntos de interacción en el lado izquierdo es 5 y en el lado derecho es 3. Desde ambos extremos, el número de puntos de interacción es impar, entonces el punto se considera dentro del objeto.
Regla de número de bobinado distinto de cero
Este método también se usa con los polígonos simples para probar si el punto dado es interior o no. Se puede entender simplemente con la ayuda de un alfiler y una goma elástica. Fije el alfiler en uno de los bordes del polígono y ate la goma elástica y luego estire la goma a lo largo de los bordes del polígono.
Cuando todos los bordes del polígono estén cubiertos por la banda elástica, revise el pasador que se ha fijado en el punto a probar. Si encontramos al menos un viento en el punto considérelo dentro del polígono, de lo contrario podemos decir que el punto no está dentro del polígono.
En otro método alternativo, dé direcciones a todos los bordes del polígono. Dibuje una línea de exploración desde el punto que se va a probar hacia el extremo izquierdo de la dirección X.
Dé el valor 1 a todos los bordes que van hacia arriba y todos los demás -1 como valores de dirección.
Compruebe los valores de la dirección del borde por los que pasa la línea de exploración y resúmalos.
Si la suma total de este valor de dirección es distinta de cero, entonces este punto a probar es un interior point, de lo contrario es un exterior point.
En la figura anterior, sumamos los valores de dirección desde los cuales pasa la línea de exploración, entonces el total es 1 - 1 + 1 = 1; que no es cero. Entonces se dice que el punto es un punto interior.