多边形扫描转换算法中的边表(Edge Table, ET)

大家好，欢迎来到IT知识分享网。

目录

边表(Edge Table, ET)

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

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

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

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

形象的展示一下：

边表包含所有的边

• sorted by their smaller y coordinate of edge. ($y_{min}$)
• 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}$)
• And if two x coordinates of the lower endpoint of edge are equal
  • edges are sorted according to the slope(斜率） of edge. ($m$)

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

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

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

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

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

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

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