2.采用的数据结构 (1)活性边表 为了计算每条扫描线与多边形各边的交点,最简单的 方法是把多边形的所有边放在一个表 在处理每条扫描 线时,按顺序从表中取出所有的边,分别与扫描线求交 这样处理效率很低,这是因为一条扫描线往往只与少数几 条边相交,甚至与整个多边形都不相交。为了提高效 在处理一条扫描线时,仅对与它相交的多边形的边进行求 前扫描线相交的边称为活性边,并把 称此链表为活性巫标递增的顺序存放在一个链表中 描线交点 活性边表的每个结点存放对应边的有关信息,如扫描 线与该边的交点x,边所跨 描线条数等。由于边的连 性(即当某条边与当前扫描线相交时,它很可能也与下 条扫描线相交 以及扫描线的连贯性(即当前扫描线 各边的交点顺序与下一条扫描线与各边的交点顺序很可 能相同或非常类似),在当前扫描线处理完毕之后,不必 为下一条扫描线从头开始构造活性边表 要对当前扌 描线的活性边表稍作修改和更新,就可以得到下一条扫描 线的活性边表。具体原理讨论如下:
2．采用的数据结构 （1）活性边表 为了计算每条扫描线与多边形各边的交点，最简单的 方法是把多边形的所有边放在一个表中。在处理每条扫描 线时，按顺序从表中取出所有的边，分别与扫描线求交。 这样处理效率很低，这是因为一条扫描线往往只与少数几 条边相交，甚至与整个多边形都不相交。为了提高效率， 在处理一条扫描线时，仅对与它相交的多边形的边进行求 交运算。我们把与当前扫描线相交的边称为活性边，并把 它们按与扫描线交点x坐标递增的顺序存放在一个链表中， 称此链表为活性边表。 活性边表的每个结点存放对应边的有关信息，如扫描 线与该边的交点x，边所跨的扫描线条数等。由于边的连 贯性（即当某条边与当前扫描线相交时，它很可能也与下 一条扫描线相交），以及扫描线的连贯性（即当前扫描线 与各边的交点顺序与下一条扫描线与各边的交点顺序很可 能相同或非常类似），在当前扫描线处理完毕之后，不必 为下一条扫描线从头开始构造活性边表，而只要对当前扫 描线的活性边表稍作修改和更新，就可以得到下一条扫描 线的活性边表。具体原理讨论如下：
假设当前扫描线与多边形的某一条边的交点坐标为x, 那 条扫描线与该边的交点不必从头计算,只要加上 个增量即可。设边的直线方成为 ax+by+C=0 若y=y时,x=×i,则当y=y+1时, +1=(-byi+1-c/a=(-b(yi+1)C)a=(-byi- c/a-b/a=xi-b/a 其中△ⅹ=-b/a为常量。△x可以存放在对应边的活性 边表结点中。另外,使用增量法计算时,我们需要知道 删除,量免下一芜的算 交,以便及时把它从活性 综上所述,活性边表的结点中至少应为对应边保存如 下内容 X:当前扫描线与边的交点; △x:从当前扫描线到下一条扫描线之间的x增量; ymax:边所交的最高扫描线号
假设当前扫描线与多边形的某一条边的交点坐标为x， 那么下一条扫描线与该边的交点不必从头计算，只要加上 一个增量即可。设边的直线方成为 ax+by+c=0 若y=yi时，x=xi，则当y=yi+1时， xi+1=(-byi+1-c)/a=(-b(yi+1)-c)/a=(-b yi - c)/a-b/a=xi-b/a 其中△x=-b/a为常量。△x可以存放在对应边的活性 边表结点中。另外，使用增量法计算时，我们需要知道一 条边何时不再与下一条扫描线相交，以便及时把它从活性 表中删除，避免下一步无谓的计算。 综上所述，活性边表的结点中至少应为对应边保存如 下内容： x: 当前扫描线与边的交点； △x：从当前扫描线到下一条扫描线之间的x增量； ymax: 边所交的最高扫描线号
若规定多边形的边不自交,则从当前扫描线 延续到下一条扫描线,边与下一条扫描线的交点 顺序保持不变。否则,到下一条扫描线,必须重 新排序。由于扫描线的连贯性,新交点序列与旧 交点序列基本一致,最多只有个别需要调整。因 此,采用冒泡排序法可获得较好效果。对于下 条扫描线新交上的边,则必须在当前扫描线处理 完之后的更新过程中,插入到活性边表的适当位 置,并保持有序性。这个过程采用插入排序最适 宜。另外,在上述的交点x坐标更新和新边插入之 前,必须把那些与当前扫描线有交,而与下一条 扫描线不再相交的边,从活性边表中删除。图 5.1.4中,扫描线6的活性边表如图(a)所示 扫描线7的活性边表如图(b)所示
若规定多边形的边不自交，则从当前扫描线 延续到下一条扫描线，边与下一条扫描线的交点 顺序保持不变。否则，到下一条扫描线，必须重 新排序。由于扫描线的连贯性，新交点序列与旧 交点序列基本一致，最多只有个别需要调整。因 此，采用冒泡排序法可获得较好效果。对于下一 条扫描线新交上的边，则必须在当前扫描线处理 完之后的更新过程中，插入到活性边表的适当位 置，并保持有序性。这个过程采用插入排序最适 宜。另外，在上述的交点x坐标更新和新边插入之 前，必须把那些与当前扫描线有交，而与下一条 扫描线不再相交的边，从活性边表中删除。图 5.1.4中，扫描线6的活性边表如图（a）所示， 扫描线7的活性边表如图（b）所示
207351577218 108
2 0 7 3.5 -1.5 7 7 2 8 11 0 8
928 1108 通过活性边表,可以充分利用边的连贯性 和扫描线的连贯性,减少求交计算量与提高排 序效率
9 2 8 11 0 8 Λ 通过活性边表，可以充分利用边的连贯性 和扫描线的连贯性，减少求交计算量与提高排 序效率