作者：魏胜利; 李源布尔运算多边形基点交点计算几何
摘要：在分析现有算法的基础上,提出了一种基于交点有序化的简单多边形布尔运算算法。该算法以循环单链表数据结构存储多边形顶点和交点,在交点按顺序插入到多边形链表环节提出基点的概念。对于采用时间复杂度为O(n+k)logm的算法所求出无序多边形交点,以邻接表暂存这些交点,把具有相同基点的交点按交点到基点的距离从小到大排序以实现无序交点的有序化,然后通过一次遍历邻接表把交点依次插入到多边形链表中。在循环单链表中,主多边形和裁剪多边形共享同一个交点,以哈希表存储交点的地址,以提高查找效率。根据多边形顶点的进出性追踪多边形的交、并、差。最后对算法进行了编程实现并与其他同类算法进行了比较,结果表明该算法具有更高的执行效率。
注：因版权方要求，不能公开全文，如需全文，请咨询杂志社
