Python扫描线填充算法实现与原理详解

陈默

发布时间：2026-10-13| 7人浏览过

原创

本文详细介绍Python中扫描线填充算法的实现原理与代码。通过活性边表（AET）和新边表（NET）管理多边形边界，利用水平扫描线从上至下遍历，计算交点并按X坐标排序后成对填充。文章包含完整数组实现代码及实例演示，适用于计算机图形学基础学习。

本文分享一个基于Python的扫描线填充算法示例，供相关领域开发者参考。

算法原理概述

首先，使用水平扫描线从上至下遍历由线段构成的多边形。

其次，计算每条扫描线与多边形各边的交点。将这些交点按X坐标排序，并成对提取作为端点，以指定颜色绘制水平线段。

最后，当所有扫描线处理完毕，多边形内部填充即告完成。

数据结构设计

核心依赖两个关键数据结构：活性边表（Active Edge Table, AET），用于存储当前扫描线相交的边；以及新边表（New Edge Table, NET），用于预存储即将在后续扫描线中出现的边。

具体实现上，NET按Y坐标索引存储边信息，AET则在扫描过程中动态维护。

代码实现

以下是基于数组结构的Python代码实现。


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()