基于交点有序化的简单多边形布尔运算

来源：计算机技术与发展杂志2019年第08期北京时间：

作者：魏胜利;李源

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

关键词：布尔运算;多边形;基点;交点;计算几何