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

Sub-region data structure and its composition algorithm in pattern generator

作　　者：张博[1,2] 唐小萍[1] 杨勇[1] 严伟[1] 

机构地区：[1]中国科学院光电技术研究所,成都610209 [2]中国科学院研究生院信息科学与工程学院,北京100049

出　　处：《计算机应用》2009年第12期3314-3316,共3页journal of Computer Applications

基　　金：02科技重大专项(2009ZX02037-06);国家863计划项目(2009AA03Z341)

摘　　要：为实现直写曝光机中图形发生器的软件功能模块,系统地给出了一种多边形的双向链接边表的表示方法及高效的平面子区域划分的叠合算法。该算法以计算几何中常用的平面扫描算法为基础,对叠合过程中出现的各种情况,给出了通用的处理方法,针对多边形中出现空洞的情况,提出了一种判别准则和基于图的重构的遍历搜索方法。根据分析,该算法的时间复杂度含有对数因子,优于传统的二次项复杂度,并且具有线性的空间复杂度。由于双向链接边表的数据结构主要由指针和链表组成,所以易于在计算机中实现。To realize the software functional module in pattern generator, this paper gave a new data structure, doubly-connected edge list, and a well-designed composite algorithm of the sub-regions by using the plane sweep algorithm in computational geometry. In that algorithm, a general approach was given to process any situation appearing in sub-regions composition. To find the internal-hollowed polygon, a discriminate method and a search method were proposed based on graph reconstruction. The time complexity in this algorithm has a logarithmic item and linear space complexity, better than the quadratic one. The data structure is easy to realize in PCs because it is mainly composed of pointers and linked-lists.

关 键 词：双向链接边表 子区域划分 叠合 空洞 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]