刘庆保，张树生，范海涛

(西北工业大学现代设计与集成制造技术教育部重点实验室，西安710072)

1 引言

近年来，国际上CAPP技术及应用呈现出基于三维模型的工艺设计、工艺仿真与优化及可视化装配等发展趋势［1］。但是现阶段，CAPP的应用基本上基于二维CAD进行，三维CAD的集成应用还处于起步阶段，有待研究和突破。本课题提出基于工艺语义的二维工序图的三维工序模型重建［2-3］技术研究。其中，最重要的内容是基于工艺语句的二维工序图形的特征识别，而工程图中连通域的划分和邻接关系的确定则是实现特征识别的必要预处理过程。

在工程图的预处理中，文献［4］提出了采用区域连接图表示工程图的方法，在符号识别的处理中仅考虑了连通域相邻情况，对包含连通则没有提出有效解决办法。文献［5］提出了连通域种类划分，以及一种多边形环的获取方法，但是未提出连通域邻接关系的判定具体算法，未就多边形环如何在连通域的划分与邻接关系确定的应用做出详细分析。文献［6］运用扫描线与二维切片环相交来自动生成三维网格，是扫描线算法在CAD领域的重要应用。

作者提出了用极左路径法划分封闭环并在封闭环邻接关系的确定中引入扫描线算法，基于此得到连通域的划分以及连通域的邻接关系。

2 关键技术

2.1 封闭环的划分及位置关系的确定

2.1.1 封闭环的划分算法

连通域可由多边形封闭环所围成的区域来表示，封闭环的划分与邻接关系的确定是连通域划分与确定其邻接关系的前提。……