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

• 作者: 李源 魏胜利
• 来源期刊: 计算机技术与发展
• 学科: 工学
• 关键词: 布尔运算 多边形 基点 交点 计算几何
• 年，卷（期）: 2019,（8）
• 所属期刊栏目: 智能、算法、系统工程
• 页码范围: 81-85
• 页数: 5页
• 分类号: TP391
• 字数: 4774字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-629X.2019.08.016

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	魏胜利	安阳工学院计算机科学与信息工程学院	29	68	5.0	7.0
2	李源	安阳工学院计算机科学与信息工程学院	16	42	4.0	6.0