2.采用的数据结构 (1)活性边表 为了计算每条扫描线与多边形各边的交点,最简单的 方法是把多边形的所有边放在一个表 在处理每条扫描 线时,按顺序从表中取出所有的边,分别与扫描线求交 这样处理效率很低,这是因为一条扫描线往往只与少数几 条边相交,甚至与整个多边形都不相交。为了提高效 在处理一条扫描线时,仅对与它相交的多边形的边进行求 前扫描线相交的边称为活性边,并把 称此链表为活性巫标递增的顺序存放在一个链表中 描线交点 活性边表的每个结点存放对应边的有关信息,如扫描 线与该边的交点x,边所跨 描线条数等。由于边的连 性(即当某条边与当前扫描线相交时,它很可能也与下 条扫描线相交 以及扫描线的连贯性(即当前扫描线 各边的交点顺序与下一条扫描线与各边的交点顺序很可 能相同或非常类似),在当前扫描线处理完毕之后,不必 为下一条扫描线从头开始构造活性边表 要对当前扌 描线的活性边表稍作修改和更新,就可以得到下一条扫描 线的活性边表。具体原理讨论如下:2．采用的数据结构 （1）活性边表 为了计算每条扫描线与多边形各边的交点，最简单的 方法是把多边形的所有边放在一个表中。在处理每条扫描 线时，按顺序从表中取出所有的边，分别与扫描线求交。 这样处理效率很低，这是因为一条扫描线往往只与少数几 条边相交，甚至与整个多边形都不相交。为了提高效率， 在处理一条扫描线时，仅对与它相交的多边形的边进行求 交运算。我们把与当前扫描线相交的边称为活性边，并把 它们按与扫描线交点x坐标递增的顺序存放在一个链表中， 称此链表为活性边表。 活性边表的每个结点存放对应边的有关信息，如扫描 线与该边的交点x，边所跨的扫描线条数等。由于边的连 贯性（即当某条边与当前扫描线相交时，它很可能也与下 一条扫描线相交），以及扫描线的连贯性（即当前扫描线 与各边的交点顺序与下一条扫描线与各边的交点顺序很可 能相同或非常类似），在当前扫描线处理完毕之后，不必 为下一条扫描线从头开始构造活性边表，而只要对当前扫 描线的活性边表稍作修改和更新，就可以得到下一条扫描 线的活性边表。具体原理讨论如下：