Linea de Rastreo

El algoritmo presentado a continuación considera polígonos cóncavos al igual que convexos, incluyendo aquellos
que puedan tener huecos internos o intersectados por si mismos.
La siguiente figura ilustra el procedimiento de la línea de rastreo para el llenado  sólido de  polígono.

 Para cada línea de rastreo que cruza un polígono el algoritmo de llenado de áreas debe:

· localizar los puntos de intersección de la línea de rastreo con las aristas del polígono,
· definir los intervalos de llenado (spans) para cada línea de rastreo.
Esto se repetiría para todas las líneas de rastreo que intersectan el polígono.


ejemplo

Para comenzar es necesario obtener los siguientes datos de cada linea :
     1.-la Y máxima de la arista
     2.- la X de la Yminima de la arista
     3.-la inversa de la pendiente (1/m)

para comenzar a obtener los valores de cada arista que compone el polígono comensaremos por obtener la pendiente y su inversa a partir de la formula  m=(y2-y1) / (x2-x1)

1 paso calcular los datos de las aristas:
(en este ejemplo solo se calculara la de b pero es el mismo procedimiento para todas)

para obtener los datos del la arista b [ 1/m , Ymax , X de ymin ]
b [ 1/5 , 13 , 10]

2) la forma mas sencilla es hacer una tabla donde la primera columna sera desde Y menor de la arista hasta la Y max y la segunda columna iniciara en X de ymin e ira incrementando deacuerdo al valor de 1/m

Para cada arista se repiten estos pasos asi que podrian calcularse en una misma tabla tomando de referencia solo la Y min del polígono y la Y max del polígono e ir calculando en la tabla los valores de X de cada arista dependiendo de la Y en la que se encuentre ejemplo

Y	Arista    a	Arista     b
3	-	10
4	4	10(1/5)
5	3(7/8)	10(2/5)
6	3(6/8)	10(3/5)
7	3(5/8)	10(4/5)
8	3(4/8)	11
9	3(3/8)	11(1/5)
10	3(2/8)	11(2/5)
11	3(1/8)	11(3/5)
12	3	11(4/5)
13	-	12

los valores de la arista a para Y=3 y Y=13 no se calculan ya que la arista a va de Ymin= 4 a Ymax =12
este proceso se repite para todas las aristas

después de esto se acomodan los puntos para cada y de menor a mayor y se gráfican en pares tomando en cuenta la restricción de que se eliminan las intersecciones repetidas cuando coinciden con un vértice que no es máximo ni mínimo

Referencia documental:
http://cannes.itam.mx/Alfredo/Espaniol/Cursos/Grafica/Relleno.pdf