艾迪，周云燕，万里兮

（中国科学院微电子研究所 北京 100029）

微电子领域，常用的商用仿真软件如Cadence，HFSS，对于实体、层、网格等等单元的操作都会大量使用到多边形处理的各种算法。比如鼠标点击选中相应单元的操作需要用到点是否在多边形内的算法；绘制版图时需要大量用到多边形的合并，分割、删除等算法。这些软件只能对已经存在的多边形进行这些操作。然而有些时候从DXF文件导入的版图中仅含有线段信息，不含多边形信息；或者需要对椭圆、圆弧等其他实体围成的封闭区域进行这种类似多边形操作。对于这些情况这些软件就无能为力。本文在实际电磁仿真软件开发的基础上提出的图形封闭区域识别算法很好的解决了这个问题。

这种识别算法输入可以是任意的线段、圆弧信息，输出则为所有的封闭区域（包含多边形）。在处理过程中首先需要对于已知线段集合求出所有交点信息。而这种求交点已经有了快速高效的算法。本文应用了这种高效的算法，并增加了它的适应性以支持圆弧。在封闭区域的搜索过程中，本文采用了一种类似于计算机图形学中广泛应用的图的广度优先遍历搜索算法。该算法原本目的是路径搜索发现，本文在算法实现过程中加以修改，拓展了图的相邻表储存结构，使之能够发现图中封闭的区域，同时又保持了算法本身低时间复杂度的特性。

1 基本理论

在二维的计算几何学问题中，每个输入单元都用一个点的集合{pn}来表示，其中每个 pi=（xi，yi），xi∈R，yi∈R。……