扫描线填充算法

介绍

1. 用水平扫描线从上到下扫描由点线段构成的多段构成的多边形。
2. 每根扫描线与多边形各边产生一系列交点。将这些交点按照x坐标进行分类，将分类后的交点成对取出，作为两个端点，以所填的色彩画水平直线。
3. 多边形被扫描完毕后，填色也就完成。
   

数据结构

活性边表：

新边表：

代码（使用数组）

import numpy as np
from PIL import Image
from PIL import ImageDraw
from PIL import ImageFont
 
array = np.ndarray((660, 660, 3), np.uint8)
array[:, :, 0] = 255
array[:, :, 1] = 255
array[:, :, 2] = 255
 
for i in range(0,660,1):
  array[i,330]=(0,0,0)
for j in range(0,660,1):
  array[330,j]=(0,0,0)
 
    
def creat_Net(point, row, y_min,y_max ): 
  Net =  [([ ] * y_max ) for i in range(y_max )] 
  point_count = point.shape[0]
  for j in range(0,  point_count):  
    x = np.zeros(10) 
    first = int(min(point[(j+1)%point_count][1] , point[j][1]))  
    x[1] =  1/((point[(j+1)%point_count][1]-point[j][1])/(point[(j+1)%point_count][0]-point[j][0])) # x 的增量
    x[2] = max(point[(j+1)%point_count][1] , point[j][1]) 
    if(point[(j+1)%point_count][1] < point[j][1]):
      x[0] = point[(j+1)%point_count][0]  
    else:
      x[0] = point[j][0] 
    Net[first].append(x) 
  return Net

def draw_line(i,x ,y ):
  for j in range(int(x),int(y)+1):
    array[330-i,j+330]=(20,20,20)
  

def polygon_fill(point):
  y_min = np.min(point[:,1])
  y_max = np.max(point[:,1]) 
  Net = creat_Net(point, y_max - y_min + 1, y_min, y_max) 
  x_sort = [] * 3
  for i in range(y_min, y_max): 
    x = Net[i]
    if(len(x) != 0): 
      for k in x :
        x_sort.append(k)  
    x_image = [] * 3  
    for cell in x_sort:
      x_image.append(cell[0])
    x_image.sort()
    if(len(x_image) >= 3 and x_image[0]==x_image[1] and x_image[2]>x_image[1]):
      x_image[1] = x_image[2]  
    draw_line(i, x_image[0], x_image[1])
    
    linshi = [] * 3 
    for cell in x_sort:
      if cell[2] > i: 
        cell[0] += cell[1]
        linshi.append(cell)     
    x_sort = linshi[:] 

  x_image = [] * 3  
  for cell in x_sort:
    x_image.append(cell[0])
  x_image.sort()
  
  draw_line(i, x_image[0],x_image[1]) 

def main(): 
  point =  [[55,40], [100,80], [100,160],[55,180], [10,160], [10,80]]
  point = np.array(point) 
  polygon_fill( point )
  image = Image.fromarray(array)
  image.save('saomao.jpg')
  image.show() 

if __name__ == "__main__":
  main()


 

实例：