[1]魏胜利,李 源.基于交点有序化的简单多边形布尔运算[J].计算机技术与发展,2019,29(08):81-85.[doi:10. 3969 / j. issn. 1673-629X. 2019. 08. 016]
 WEI Sheng-li,LI Yuan.A Simple Polygon Boolean Operation Based on Sorted Intersection Points[J].,2019,29(08):81-85.[doi:10. 3969 / j. issn. 1673-629X. 2019. 08. 016]
点击复制

基于交点有序化的简单多边形布尔运算()
分享到:

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:
29
期数:
2019年08期
页码:
81-85
栏目:
智能、算法、系统工程
出版日期:
2019-08-10

文章信息/Info

Title:
A Simple Polygon Boolean Operation Based on Sorted Intersection Points
文章编号:
1673-629X(2019)08-0081-05
作者:
魏胜利;?李 源
安阳工学院 计算机科学与信息工程学院,河南 安阳 455000
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
分类号:
TP391
DOI:
10. 3969 / j. issn. 1673-629X. 2019. 08. 016
摘要:
在分析现有算法的基础上,提出了一种基于交点有序化的简单多边形布尔运算算法。 该算法以循环单链表数据结构存储多边形顶点和交点,在交点按顺序插入到多边形链表环节提出基点的概念。 对于采用时间复杂度为 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.

相似文献/References:

[1]徐巍 陈东方.基于有向边的Java手机多边形算法研究[J].计算机技术与发展,2008,(08):105.
 XU Wei,CHEN Dong-fang.Research of Polygon on Java Phone Based on Directed Line[J].,2008,(08):105.
[2]刘建新 卢新明 岳昊.简单多边形快速Delaunay三角剖分算法[J].计算机技术与发展,2006,(07):126.
 LIU Jian-xin,LU Xin-ming,YUE Hao.Fast Algorithm for Delaunay Triangulation of Simple Polygon Based on Maximum Triangle Weights[J].,2006,(08):126.

更新日期/Last Update: 2019-08-10