目录

边表(Edge Table, ET)

在多边形的扫描转换算法中，我们首先需要建立一个全局的边表(ET),它包含多边形的所有边，并且这些边按照它们各自y坐标较小值($y_{min}$ymin​)排序。
有资料也把这个全局的边表称为新边表(New Edge Table, NET),但是意思是一样的，即多边形扫描转换算法初始化时建立的全局边表。

ET是基于桶排序的方式建立的，有多少扫描线就有多少个桶(一般在最下面的桶下面再多加一个，看下面的例子就知道是什么意思了）,每一个桶对应一个链表，每一个链表中的边的下端端点的纵坐标是相同的。然后在每个桶中，根据边的较低的端点的x坐标（$x_{min}$xmin​)，按照增序的方式对边进行排序。

ET（边表）中每一个链表的节点（每个节点对应一条边）包含下列信息：

• 边的$y_{max}$ymax​坐标值
• 边的下端端点的x坐标$x_{min}$xmin​。
  注意这里$x_{min}$xmin​ is the x at the minimum y for the edge, not necessarily the minimum x of the edge. Hence $x_{min} = 7$xmin​=7 for edge AB in 图3.14.
• 随着扫描线递变到下一条线时的x坐标的增量1/m, (斜率的导数，m是斜率，slope)

边表包含所有的边

• sorted by their smaller y coordinate of edge. ($y_{min}$ymin​)
• If smaller y coordinates of edge are equal
  • edges are sorted in order of increasing x coordinate of the lower endpoint of edge. ($x_{min}$xmin​)
• And if two x coordinates of the lower endpoint of edge are equal
  • edges are sorted according to the slope(斜率） of edge. ($m$m)

总结一下如何构建边表
1.按照每条边的$y_{min}$ymin​进行桶排序。
2.在一个桶中，按照$x_{min}$xmin​递增的顺序进行排序。
3.如果$x_{min}$xmin​也相同，那就按照边的斜率递增的顺序进行排列。

光说不练假把式。
下图中有个多边形ABCDEF,

格点的坐标写上去之后就是下面这个图。

该多边形的边表(ET)如下：

1.有多少条扫描线就有多少桶。
最低点是1， 我不知道为什么要把0也写上，暂时就多写一个吧。
最高点是11， 所以扫描线最高是11，没有问题

2.根据每个边的$y_{min}$ymin​对边进行桶排序
一共有多少个$y_{min}$ymin​?，分别是多少？对应那几条边？

1 -> AB， BC
3 -> FA
5 -> CD
7 -> EF, DE 

所以0,2,4,6,8,9,10,11都是空的，这里用$\lambda$λ进行占位。（为什么要用$\lambda$λ，记住就好了）。

3.如果边的$y_{min}$ymin​相同，则按照$x_{min}$xmin​的顺序进行排列。（这个我感觉是针对水平边的，因为水平边是被忽略的，这样以来，水平边的两个端点的$x_{min}$xmin​就不同了）

4.如果边的$y_{min}$ymin​和$x_{min}$xmin​都相同，则按照边的斜率进行排序。
所以这就是扫描线7,中EF排在前，DE排在后的原因了。

OK，到此多边形扫描转换中的边表就讲清楚了，接下来讲解活性边表(Active Edge Table, AET)。