二维图形封闭区域自动识别算法.docVIP

第 20 卷第 7 期电子设计工程2012 年 4 月 Vo 第 20 卷 第 7 期 电子设计工程 2012 年 4 月 Vol.20 No.7 Electronic Design Engineering Apr. 2012 二维图形封闭区域自动识别算法 艾 迪， 周云燕， 万里兮 （中国科学院微电子研究所 北京 100029） 摘要： 在图形处理中，常需要从仅含有直线、弧线信息的原始图形中获取多边形这样的封闭区域信息。 该算法首先生 成原始图形中线和线各交点组成的稀疏图结构，然后采用以广度遍历算法为基础的单源有哪些信誉好的足球投注网站法识别出图形中所有封 闭区域，最终以点集形式输出这些区域的信息。 输出结果能直接作为很多其他图形算法的输入（如多边形合并，凸包 寻找）。 这种算法快速高效 ，能很好的应对如多重交点 、线段重合等一些临界情况，并且支持对弧线的处理 。 关键词： 二维图形； 封闭区域； 广度遍历； 多边形 中图分类号： TP391.72 文献标识码： A 文章编号：1674－6236（2012）07-0044-05 Enclosed areas in 2D graphics automatic identification algorithm AI Di， ZHOU Yun-yan， WAN Li-xi （Institute of Microelectronics of Chinese Academy of Sciences， Beijing 100029， China） Abstract: We usually need to obtain enclosed area such as polygon simply from a number of lines and arcs in geometric. The algorithm firstly gets the sparse graph representing those line intersections， then searches through a single source to generate a directed acyclic tree， and outputs information on all the enclosed areas at last. The results can be directly used as the input of many other subsequent algorithms（e.g. graphic merging， convex hull searching）. This algorithm is fast and efficient. It is robust enough deal with boundary conditions such as multiple intersections or line overlap. It also supports the processing of arcs. Key words: two-dimensional graphics； enclosed area； breadth-first search； polygon 微电子领域，常用的商用仿真软件如 Cadence， HFSS，对 于实 体 、 层 、 网格 等 等 单元 的 操 作都 会 大 量使 用 到 多边 形 处 理的各种算法。 比如鼠标点击选中相应单元的操作需要用到 点是否在多边形内的算法；绘制版图时需要大量用到多边形 的合并，分割、删除等算法。 这些软件只能对已经存在的多边 基本理论 在二维的计算几何学问题中，每个输入单元都用一个点 的集合{ pn}来表示，其中每个 pi=（xi，yi），xi∈R，yi∈R。 输入单 元可以是简单的点、线段、圆弧或是多边形，在本文的算法中 还有可能是一段折线。用点集表示多边形 P 时，可以按照在 P 的边 界 上出 现 的 逆时 针 或 是顺 时 针 顺序 排 列 的 顶 点 序 列 来 （p1，p2，… ，pn）表示。 对于 圆 弧， 一 般 计 算机 中 需 要 用 3 组 信 息 来 储 存 ， 分 别 是圆弧的起点、终点以及弧度值大小。 圆弧可能是圆的一部 分，也有可能是一段任意的曲线。 在本文的算法中，对圆弧的 处理 只 会用 到 圆 弧与 其 他 单元 的 交 点 ， 以 及 圆 弧 上 点 的 次 序。 因此在计算完交点后，圆弧可以当作一般线段处理，即可 用圆弧上顺序排列的点（p1，p2，… ，pn）来表示。 本算 法 与一 些 其 他图 像 识 别算 法 （ 如 文 献[1]） 不 同 之 处 在 于 输入 为 点 集{