基于交点有序化的简单多边形布尔运算-《计算机技术与发展》

文章信息/Info

Title:: A Simple Polygon Boolean Operation Based on Sorted Intersection Points

Author(s):: WEI Sheng-li; LI Yuan; School of Computer Science&Information Engineering,Anyang Institute of Technology,Anyang 455000,China

Keywords:: Boolean operations; polygon; basis point; intersection point; computational geometry

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

Abstract:: Based on the analysis of existing algorithms,a simple polygon Boolean algorithm based on sorted intersection points is presented. The algorithm stores the vertices and intersection points of polygons in a cyclic single-linked list data structure. The concept of base points is presented at the intersection points inserted sequentially into the polygonal linked list links. For the disorder intersection points of polygons with O(n + k) log m time complexity,the adjacent tables is used to store these intersection points temporarily. The intersection points with the same basis point from small to large by the distance of intersection point to basis point are sorted,so that the disorder intersections will be ordered. The intersection points are inserted into the lists of the polygons sequentially by traversing through the adjacent tables once. In the circular single linked list,the main polygon and the clipping polygon share the same intersection points,the address of the intersection points is stored in a hash table to improve the search efficiency. In terms of the entry and exit of polygon vertices the intersection,union and difference of the polygons are traced. Finally,the algorithm is programmed and compared with other similar algorithms,which shows that it has higher efficiency.