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

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

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

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.