about 图形学中的多边形扫描算法。

在图形学中，多边形往往是由有序的顶点序列表达的，以便于进行放缩、平移、旋转等操作。然而，在填充灰度或色彩时，采用点阵的方式才容易操作。所以对于多边形而言，涉及一个扫描转换的问题：给定多边形，确定屏幕上归属于多边形的像素集合。

属于图形学系列文章。

多边形基础知识

Polygon Types：Convex、Concave、Degenerate（zero surface area）

Identifying Concave Polygons

Triangulating a Convex Polygon

Polygon Rasterization

Basic idea

Intersecting a scanline with polygon edges and fill between pairs of intersections

Corner Case 特殊情况

Scanning Polygon 例子

需要好好体会整个过程！

算法实现

Brute force: intersect all the edges with all scanline 太慢啦！

更高效的做法：

Find the y_min and y_max of each edge and intersect the edge only when it crosses the scanline

Only calculate the intersection of the edge with the first scan line it intersects

Edge Table (ET)

Active Edge Table (AET)

这里课件中的图画错了，下图右下角是正确的图：

算法

construct the ET # edge table
AET = [] # active edge table
for y = ymin to ymax
  merge-sort ET[y] into AET by x value
  for each edge in AET:
    if edge.ymax = y:
      remove edge from AET
  fill between pairs of x in AET
  for each edge in AET:
    edge.x = edge.x + dx/dy
  sort AET by x value