多边形扫描线填充算法的Python实现

有好长时间没有更新自己的博客,一是最近ACM Lab那边事情稍多一点,一是重装了下Manjaro Linux,环境也没怎么配。说实话主要原因是每天晚上回宿舍便和舍友忙着开黑吃鸡,以至于留给自己的时间实在少的可怜……前几天刚刚加入了IR Lab,见到实验室周围人如此上进,心想自己也不能如此颓废,就打算时常更新下博客。

扫描线填充算法其实原理很简单,具体实现起来可能比之前的画线画圆之类的算法要复杂一些:就是用一条扫描线,从下到上开始扫描,要涂的区域肯定在这条扫描线与多边形的两两交点之间。也不用每次都重新求一边交点,因为每次$y$是增加$1$的,因为边是直线所以此时交点横坐标只需要各自增加$\delta x$就可以了,碰到一条边被扫描完了就把它删掉加下一条边。具体实现的时候把(当前的横坐标,横坐标增量,结束纵坐标)存入到链表数组NET[起始横坐标]中去,链表AET维护当前y = i这条扫描线的各节点顺序。看下代码应该还是比较清晰的。

下面是一些通用的函数,分别是画格点、画像素点方块以及画直线的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.patches import Rectangle
from matplotlib.lines import Line2D

def add_grid(size_x, size_y):
major_ticks = np.arange(0, size_x + 1, 5)
minor_ticks = np.arange(0, size_y + 1, 1)
ax.set_xticks(major_ticks)
ax.set_xticks(minor_ticks, minor=True)
ax.set_yticks(major_ticks)
ax.set_yticks(minor_ticks, minor=True)
ax.grid(which='minor', alpha=0.2)
ax.grid(which='major', alpha=0.5)

def pixel_plot(x, y, c):
rect = Rectangle((x, y), 1, 1, color=c, alpha=0.5)
ax.add_patch(rect)

def draw_line(x1, x2, y, c):
for x in range(int(x1 + 0.5), int(x2 + 0.5)):
pixel_plot(x, y, c)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def polyfill(polygon, color):
edges = [(polygon[i - 1], polygon[i]) for i in range(0, len(polygon))] # 产生所有的边
for (x1, y1), (x2, y2) in edges: # 对这些边进行连线
ax.add_line(Line2D((x1 + 0.5, x2 + 0.5), (y1 + 0.5, y2 + 0.5), linewidth=2, color='blue'))
_, ys = zip(*polygon) # 获得所有的y值
ymax, ymin = max(ys), min(ys)
n = ymax - ymin + 1
net = [[] for i in range(n)]
for (x1, y1), (x2, y2) in edges:
if y1 > y2:
(x1, y1), (x2, y2) = (x2, y2), (x1, y1)
net[y1 - ymin].append((x1, (x1 - x2) / (y1 - y2), y2)) # 将ymin = i的节点放入net[i]
aet = []
for i in range(n):
# 将net[i]中每个结点按顺序插入到AET中
for edge in net[i]:
aet.append(edge)
j = len(aet) - 1
while j > 0 and edge < aet[j - 1]:
aet[j] = aet[j - 1]
j -= 1
aet[j] = edge
# 两两配对填充
for j in range(1, len(aet), 2):
draw_line(aet[j - 1][0], aet[j][0], i + ymin, color)
aet = list(filter(lambda edge: edge[2] != ymin + i, aet)) # 将所有扫描完的边删除
aet = list(map(lambda edge: (edge[0] + edge[1], edge[1], edge[2]) if edge[2] > ymin + i else edge, aet)) # 更新
1
2
3
4
5
fig, ax = plt.subplots(figsize=(15, 15))
add_grid(100, 100)
polygon = [(0, 0), (55, 10), (90, 0), (90, 20), (75, 20), (50, 50), (30, 90)]
polyfill(polygon, 'black')
plt.show()

png

如果您觉得这篇文章对您有帮助,请随意打赏。