图形发生器中新的子区域划分表示及叠合算法

• 作者: 严伟 唐小萍 张博 杨勇
• 来源期刊: 计算机应用
• 学科: 工学
• 关键词: 双向链接边表 子区域划分 叠合 空洞
• 年，卷（期）: 2009,（12）
• 所属期刊栏目: 图形图像处理
• 页码范围: 3314-3316
• 页数: 3页
• 分类号: TP391.41
• 字数: 1805字
• 语种: 中文

摘要

为实现直写曝光机中图形发生器的软件功能模块,系统地给出了一种多边形的双向链接边表的表示方法及高效的平面子区域划分的叠合算法.该算法以计算几何中常用的平面扫描算法为基础,对叠合过程中出现的各种情况,给出了通用的处理方法,针对多边形中出现空洞的情况,提出了一种判别准则和基于图的重构的遍历搜索方法.根据分析,该算法的时间复杂度含有对数因子,优于传统的二次项复杂度,并且具有线性的空间复杂度.由于双向链接边表的数据结构主要由指针和链表组成,所以易于在计算机中实现.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	杨勇	中国科学院光电技术研究所	101	942	20.0	27.0
2	唐小萍	中国科学院光电技术研究所	32	193	8.0	12.0
3	严伟	中国科学院光电技术研究所	67	294	10.0	13.0