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