参考文档：
参考1：https://blog.csdn.net/u013044116/article/details/49737585
参考2：https://blog.csdn.net/keneyr/article/details/83747501
算法思想：
对多边形沿y轴从0开始遍历，建立边表NET。只记录顶点的x, dx, ymax。
根据NET构建活动边表AET(activate edge table)。射线与多边形的交点坐标为（x + △x, y + 1）， △x是斜率的倒数（dx）。详解见 参考1。
实现代码：
点击查看代码
# encoding=utf8
import math
import cv2
import numpy as np
class EdgeTable:
def __init__(self, x, dx, ymax):
self.x = x
self.dx = dx
self.ymax = ymax
self.next = None
def fill_polys(polys):
poly_x_max = float('-inf')
poly_y_max = float('-inf')
for poly in polys:
poly_x_max = max(poly_x_max, poly[0])
poly_y_max = max(poly_y_max, poly[1])
poly_x_max += 1
poly_y_max += 1
point_count = len(polys)
# build edge table
net = [None for _ in range(poly_y_max)]
for i in range(poly_y_max):
for j in range(point_count):
# 一个点跟前面的点形成线段 跟后边的点也形成线段
if polys[j][1] == i:
if polys[(j - 1 + point_count) % point_count][1] > polys[j][1]:
x_ = polys[j][0]
dx_ = (
polys[(j - 1 + point_count) % point_count][0] - polys[j][0]
) / (polys[(j - 1 + point_count) % point_count][1] - polys[j][1])
ymax_ = polys[(j - 1 + point_count) % point_count][1]
pnt = EdgeTable(x_, dx_, ymax_)
pnt.next = net[i]
net[i] = pnt
if polys[(j + 1 + point_count) % point_count][1] > polys[j][1]:
x_ = polys[j][0]
dx_ = (
polys[(j + 1 + point_count) % point_count][0] - polys[j][0]
) / (polys[(j + 1 + point_count) % point_count][1] - polys[j][1])
ymax_ = polys[(j + 1 + point_count) % point_count][1]
pnt = EdgeTable(x_, dx_, ymax_)
pnt.next = net[i]
net[i] = pnt
# build activate edge table
bg = np.zeros((poly_x_max, poly_y_max), dtype=np.uint8)
aet = EdgeTable(0, 0, 0)
for i in range(poly_y_max):
# 计算新的交点 更新aet表
pa = aet.next
while pa:
pa.x = pa.x + pa.dx
pa = pa.next
# 更新aet表之后对ate表进行排序
# 断表排序 不开辟新空间
pa = aet
pcur = aet.next
pa.next = None
while pcur:
while pa.next and pcur.x >= pa.next.x:
pa = pa.next
pt = pcur.next
pcur.next = pa.next
pa.next = pcur
pcur = pt
pa = aet
# net表中的点加入到aet表中，并用插值法按x排序插入
pn = net[i]
pa = aet
while pn:
while pa.next and pn.x >= pa.next.x:
pa = pa.next
pt = pn.next
pn.next = pa.next
pa.next = pn
pn = pt
pa = aet
# 填充
pcur = aet.next
while pcur and pcur.next:
# 浮点数转成整数 如果dx是负数 向下取整；如果dx是正数 向上取整
s = math.ceil(pcur.x) if pcur.dx > 0 else math.floor(pcur.x)
e = math.ceil(pcur.next.x) if pcur.next.dx > 0 else math.floor(pcur.next.x)
# for x in range(pcur.x, pcur.next.x+1):
for x in range(s, e + 1):
bg[x][i] = 1
pcur = pcur.next
# 从aet表中删除ymax==i的结点
pa = aet
pcur = pa.next
while pcur:
if pcur.ymax == i:
pa.next = pcur.next
del pcur
pcur = pa.next
else:
pcur = pcur.next
pa = pa.next
print(bg)
def matrix(polys):
m = np.zeros((10, 10), dtype=np.uint8)
for x, y in polys:
m[x, y] = 1
return m
def cv_fill(polys):
mask = np.zeros((5, 5), dtype=np.uint8)
cv2.fillPoly(mask, [np.array(polys)], 1, lineType=cv2.FILLED)
return mask
if __name__ == "__main__":
# r = matrix([[8, 8], [2, 7], [5, 5], [2, 2], [5, 1], [9, 3]])
# print(r)
polys = [[2, 4], [1, 2], [3, 0], [4, 1], [3, 2], [4, 3]]
fill_polys(polys)
# cv_fill(polys)
结果展示：
