一个有效的多边形裁剪算法论文.docVIP

一个有效的多边形裁剪算法 摘要: 多边形多裁剪与线剪裁相比具有更广泛的实用意义,因此它是目前裁剪研究的主要课题.提出了一个多边形裁剪多边形的有效算法.其中的多边形都可以是一般多边形,既可以是凹多边形,也可以是有内孔的多边形.该算法不仅可以求多边形的“交”(多边形裁剪),而且可以求多边形的“并”和“差”.它是以所提出的一系列新方法和新技术为基础而形成的.首先,该算法使用单线性链表数据结构,与其他使用双链表或树结构的算法相比,具有占用空间少及处理速度快的特点;其次,找到了两个多边形之间进、出点之间的关系.再通过合理的数据结构处理,减少了算法对多边形链表的遍历次数,而且允许多边形既可以按顺时针方向也可以按逆时针方向输入.最后,判断和计算交点是裁剪算法的主要工作.提出了一个具有最少计算量的交点判断和计算方法,进一步加快了算法的运行速度.与其他同类算法进行了比较,结果表明,新算法具有最简单的结构和最快的执行速度. 正文: 1. 基本概念与定义. 为了便于下面对算法的讲解,本节首先介绍有关多边形裁剪的一些基本概念及术语. (1) 多边形的边的方向与内外区域的关系. 如果多边形的边的方向是顺时针的(即多边形的顶点是以顺时针的顺序输入的),则在沿着多边形的边走时,右侧区域为多边形的内部;相反,如果多边形的边的方向是逆时针的,则在沿着多边形的边走时,左侧区域为多边形的内部.对于具有孔洞的多边形,只要把内孔边界和外边界以相反的方向表示,由上面的规则判断多边形的内部仍然适用. (2) 进点和出点的定义. 设I是多边形S和C的一个交点,如果S沿着S的边界的方向在I点从C的外部进入C的内部,则称I为对于C的一个进点.反之,如果S在I点从C的内部出到C的外部,则称I为对于C的一个出点. 例如,对于如图1所示的多边形C和S及其交点I,若S的方向为逆时针方向S1→S2→S3→S4→S5,则I5I1I3是对于C的进点,I4I2I6是对于C的出点.如果S的方向为顺时针方向S5→S4→S3→S2→S1,则对于C来说,I2I4I6是进点,I1I5I3是出点 (3) 进点和出点的判定. 假设多边形S的一条边SiSi+1与另一多边形C有交点.当点Si是C的外点时,则沿着S的走向,边SiSi+1与C的第一个交点I必是C的进点;而当Si是C的内点时,I必是C的出点.由于沿着S的边界对于C的进点和出点是交替出现的(两多边形的边重合或者两多边形在顶点处相交的情况除外.这类特殊情况的处理将在第5节进行讨论),所以,只需判断第1个 交点是进点还是出点,其他交点的进出性则可依次确定. 对于一个多边形裁剪另一个多边形的过程,就是求两个多边形的相交区域(我们称其为结果多边形或输出多边形).结果多边形是由实体多边形位于裁剪多边形内的边界和裁剪多边形位于实体多边形内的边界组成的. 2.新算法的数据结构 多边形裁剪算法需要一个适当的数据结构来存储多边形及交点,并能够在其上进行正确的操作.在Weiler的算法中,输入多边形组成一个树形结构.Greiner-Hormann算法采用双向链表的结构,每个多边形由一个双向链表来表示.每找到一个交点,就将其分别插入到实体多边形和裁剪多边形的两个双向链表中.Greiner-Hormann算法使用了线性链表,与Weiler算法的树形结构相比降低了数据结构的复杂性.本文的算法采用单链表来表示所有的多边形(输入和输出),与Greiner-Hormann算法的双向链表结构相比,不仅由于少用了一个指针域而节省了存储空间,而且还进一步降低了数据结构的复杂性.我们知道,在插入一个交点时,双向链表所需修改的指针数是单链表的2倍,因此,对单链表的操作不仅简单,而且也省时. 新算法的每个多边形由一个单链表来表示,单链表的每一个结点按序(多边形顶点输入的顺序)存储着多边形的一个顶点.最后一个结点的指针指向第1个结点(循环单链表).每个链表由一个头指针指向其第1个结点,实体多边形链表的第1个结点由头指针HeadS指示;裁剪多边形链表的第一个结点由头指针HeadC指示.结点的结构定义如下(其中coordinates表示坐标类型,用于存储顶点或交点的坐标值;pointer表示指针类型): Vertex={x, y: coordinates; inters, used: Boolean; next: pointer; } 交点的数据结构如下: Intersection={x, y: coordinates; inters, used: Boolean; next1, next2: pointer; } 其中的指针域用于将交点分别插入到两个多边形的单链表中,第1指针域next1用于插入实体多边形链表;第2个指针域next2用于插入裁剪多边形链表.这样的