Relleno de polígonos

En geometría, un polígono es una figura plana compuesta por una secuencia finita de segmentos rectos consecutivos que cierran una región en el plano. Estos segmentos son llamados lados, y los puntos en que se intersecan se llaman vértices.

En un sentido amplio, se define como una región del espacio delimitada por un conjunto de líneas (aristas) y cuyo interior puede estar rellenado por un color o patrón dado.

La tarea de rellenar a figuras primitivas puede ser dividida en dos partes: la decisión de cuáles pixeles se tienen que rellenar (que depende de la forma de la primitiva modificada por el recortado), y la decisión más sencilla de cuál valor rellenarlos.

MÉTODO DE RELLENO DE POLÍGONOS CON  COLOR

SCAN-LINE

 Fila a fila van trazando lineas de color entre aristas.                                                              para scan-line que cruce el polígono se busca en la intersección entre las lineas de barrido y las aristas del polígono.

• Dichas intersecciones se ordenan y se rellenan a pares.

LINEA DE BARRIDO

     Es valido para polígonos cóncavos como convexos. Incluso para si el objeto tiene huecos interiores.

     Funcionan en el trozo de lineas horizontales, denominadas lineas de barridos, que intersectan un numero de veces, permitiendo a partir de ella identificar los puntos que se consideran interiores al polígono.

INUNDACIÓN

• Empieza en un interior y pinta hasta encontrar la frontera del objeto.
• Partimos de un punto inicial (x,y), un colo de relleno y  un color de frontera.
•  El algoritmo va testeando los píxeles vecinos a los ya pintados, viendo si son frontera o no.
• No solo sirven para polígonos, sino para cualquier área curva para cualquier imagen AE se usan los programas de dibujo.

FUERZA BRUTA

• Calcula una caja contenedora del objeto.
• Hace un barrido interno de la caja para comprobar c/pixel este dentro del polígono.
• Con polígonos simétricos basta con que hagamos un solo barrido en una sección y replicar los demás pixeles.
• Requiere aritmética punto-flotante, esto lo hace preciso y costoso.

ALTERNATIVAS PARA LA SITUACIÓN INICIAL DEL PATRÓN

Consiste en situar el punto asociado a la esquina superior izquierda del patrón en un vértice del polígono.

1. Considerar la región a rellenar en toda la pantalla y por lo tanto el patrón se citua en el origen de esta (esquina superior izquierda).
   

EJEMPLO DE SCAN-LINE

• Encontrar las intersecciones de los scanlines en el polígono.
• Almacenar las intersecciones en alguna estructura de datos ET (edge table), de manera ordena ascendiente en Y y en X  en  buckets.
• Rellenar los spans usando la estructura.
• Usar algún criterio de paridad para saber cuando un intervalo debe ser rellenado o no.