有效边表填充算法

基本思想:

用水平扫描线从上到下(或从下到上)扫描由多条首尾相连的线段构成的多边形,每根扫描线

与多边形的某些边产生一系列的交点。将这些交点按照x坐标排序,将排序后的点两两配对,作

为线段的两个端点,以所填的颜色画水平直线。

步骤

1.求交,计算扫描线与多边形的交点。

2.交点排序,对第1步得到的交点按照x从小到大排序

3.颜色填充,对排序后的交点两两组成一个水平线段,以画线段的方式进行颜色填充。

4.完成多边形扫描,就结束算法,否则,继续1

 有效边

多边形与当前扫描线相交的边成为有效边(active edge)。在处理一条扫描线时仅对有效边进行

求交运算,避免与多边形所有边求交,提高效率。

x ymax 1/k next

桶表与边表

有效边给出了扫描线与有效边交点的计算方法,但没有给出新边出现的位置坐标。为了确定在

哪条扫描线上加入了新边,就需要构造一个边表(edge table ET),用以存放扫描线上多边形各

条边出现的信息。水平边本身就是扫描线在建立边表时可以不予考虑。

桶表与边表的表示法

桶表是按照扫描线顺序管理边出现的一个数据结构。首先,构造一个纵向扫描线链表,链表的

长度为多边形所占有的最大扫描线数,链表的每个节点称为桶(bucket),对应多边形覆盖的每一

条扫描线。

将每条边的信息链加入该边最小y坐标对应的桶处。

对每一条扫描线,如果新增多条边,按照x|ymin 坐标递增的顺序存放在一个链表中,若x|ymin 相等,

则按照1/k递增,就形成边表。

x|ymin ymax 1/k

next

原文地址:https://www.cnblogs.com/zuoyou151/p/9864673.html