计算机图形学扫码线算法

计算机图形学中的扫描线算法是一种用于填充多边形的算法。它的基本思想是将多边形沿着y轴方向进行扫描，对于每一条扫描线，找到它与多边形的交点，然后根据交点的奇偶性来确定该扫描线上哪些像素需要被填充。具体步骤如下：

1. 对多边形的顶点按照y坐标进行排序，得到一个顶点表。
2. 初始化一个活动边表AET为空，扫描线从上往下扫描，对于每一条扫描线，将与之相交的边加入AET中。
3. 对于AET中的每一条边，计算它与当前扫描线的交点，将交点按照x坐标进行排序，得到一个交点表。
4. 对于交点表中相邻的两个交点，将它们之间的像素填充，如果两个交点的奇偶性相同，则不填充，否则填充。
5. 对于AET中的每一条边，更新它的x坐标，如果它的下一个顶点与当前扫描线相交，则将它的下一条边加入AET中。
6. 对于AET中的每一条边，如果它的上一个顶点与当前扫描线相交，则将它从AET中删除。

下面是一个Python实现的例子：

class Edge:
    def __init__(self, y_max, x_min, k):
        self.y_max = y_max
        self.x_min = x_min
        self.k = k

def scanline_fill_polygon(poly):
    # 1. 对多边形的顶点按照y坐标进行排序
    edges = []
    for i in range(len(poly)):
        x1, y1 = poly[i]
        x2, y2 = poly[(i+1)%len(poly)]
        if y1 == y2:
            continue
        if y1 > y2:
            x1, x2 = x2, x1
            y1, y2 = y2, y1
        k = (x2 - x1) / (y2 - y1)
        edges.append(Edge(y2, x1, k))
    
    edges.sort(key=lambda e: e.y_max)
    
    # 2. 初始化活动边表
    AET = []
    y = edges[0].y_max
    i = 0
    while i < len(edges) or len(AET) > 0:
        # 3. 计算交点表
        for e in edges[i:]:
            if e.y_max == y:
                AET.append(e)
            elif e.y_max > y:
                i -= 1
                break
        i += 1
        AET.sort(key=lambda e: e.x_min)
        intersections = []
        for j in range(0, len(AET), 2):
            e1, e2 = AET[j], AET[j+1]
            x = e1.x_min
            intersections.append(x)
            while x < e2.x_min:
                x += 1
                intersections.append(x)
        # 4. 填充像素
        for j in range(0, len(intersections), 2):
            x1, x2 = intersections[j], intersections[j+1]
            for x in range(int(x1), int(x2)+1):
                set_pixel(x, y)
        # 5. 更新AET
        new_AET = []
        for e in AET:
            e.x_min += e.k
            if e.y_max > y:
                new_AET.append(e)
        AET = new_AET
        # 6. 删除AET中的边
        AET = [e for e in AET if e.y_max > y]
        y -= 1