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

Enclosed areas in 2D graphics automatic identification algorithm

作　　者：艾迪[1] 周云燕[1] 万里兮[1] 

机构地区：[1]中国科学院微电子研究所,北京100029

出　　处：《电子设计工程》2012年第7期44-48,共5页Electronic Design Engineering

摘　　要：在图形处理中,常需要从仅含有直线、弧线信息的原始图形中获取多边形这样的封闭区域信息。该算法首先生成原始图形中线和线各交点组成的稀疏图结构,然后采用以广度遍历算法为基础的单源搜索法识别出图形中所有封闭区域,最终以点集形式输出这些区域的信息。输出结果能直接作为很多其他图形算法的输入(如多边形合并,凸包寻找)。这种算法快速高效,能很好的应对如多重交点、线段重合等一些临界情况,并且支持对弧线的处理。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.

关 键 词：二维图形 封闭区域 广度遍历 多边形 

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