relleno de poligonos

Rellenado de Polígonos
 
Dado un conjunto de puntos que forman un polígono creamos la Lista Global de Aristas LGA. Hay que recordar que una arista esta formadapor dos puntos Pi y Pi+1. Nuestra LGA tendrá la siguiente información.
 
1.- ymin el cual es el valor mínimo entre yi y yi+1
2.- ymax el cual es el valor máximoentre yi y yi+1
3.- xval es el valor de la xi correspondiente a la y mínima:
es decir xval
 
if(yi < yi+1) return xi
else return xi+1
 
4.- Calculamos lapendiente 1/m como (xi – xi+1)/(yi – yi+1)
 
Una vez creada la LGA, el algoritmo para rellenado de polígonos es:
 
1.- Hacer y igual a la menor coordenada ymin de laLGA
2.- Crear una Lista de Aristas Activas LAA que inicialmente este vacía
3.- Repetir el procedimiento mientras TAA y TA no estén vacías
3.1 mover de la LGA a laLAA las aristas con ymin = y y luego ordenar LAA con base a la coordenada x.
3.2 Rellenar los valores de los píxeles deseados en la línea de rastreo y usando paresde coordenadas x de LAA.
3.3 Eliminar de la LAA las entradas con y = ymax
3.4 incrementar y en 1
3.5 Actualizar x para la nueva y en cada arista no vertical quepertenezca a la LAA haciendo
x(k+1) = x(k) + 1/m
 
Ejemplo del Pescadito
 
Dado los siguientes vértices rellenar el polígono correspondiente
 
x   y
10, 1010, 16
16, 20
28, 10
28, 16
22, 10
 
Creamos la LGA
 
n
ymin
ymax
xval
1/m
1
10
16
10
0.0
2
16
20
10
1.5
3
10
20
28
-1.2
4
10
16
28
05
10
16
22
1
6
10
10
10
inf


Ejemplo de un polígono
 
Dados los vértices
 
            x    y
 2,  3
 2,  9
 7,  7
13, 11
13,  5
 7,  2