基于工程圖的連通域劃分及鄰接關系確定*

劉慶保，張樹生，范海濤

(西北工業(yè)大學現代設計與集成制造技術教育部重點實驗室，西安710072)

1 引言

近年來，國際上CAPP技術及應用呈現出基于三維模型的工藝設計、工藝仿真與優(yōu)化及可視化裝配等發(fā)展趨勢［1］。但是現階段，CAPP的應用基本上基于二維CAD進行，三維CAD的集成應用還處于起步階段，有待研究和突破。本課題提出基于工藝語義的二維工序圖的三維工序模型重建［2-3］技術研究。其中，最重要的內容是基于工藝語句的二維工序圖形的特征識別，而工程圖中連通域的劃分和鄰接關系的確定則是實現特征識別的必要預處理過程。

在工程圖的預處理中，文獻［4］提出了采用區(qū)域連接圖表示工程圖的方法，在符號識別的處理中僅考慮了連通域相鄰情況，對包含連通則沒有提出有效解決辦法。文獻［5］提出了連通域種類劃分，以及一種多邊形環(huán)的獲取方法，但是未提出連通域鄰接關系的判定具體算法，未就多邊形環(huán)如何在連通域的劃分與鄰接關系確定的應用做出詳細分析。文獻［6］運用掃描線與二維切片環(huán)相交來自動生成三維網格，是掃描線算法在CAD領域的重要應用。

作者提出了用極左路徑法劃分封閉環(huán)并在封閉環(huán)鄰接關系的確定中引入掃描線算法，基于此得到連通域的劃分以及連通域的鄰接關系。

2 關鍵技術

2.1 封閉環(huán)的劃分及位置關系的確定

2.1.1 封閉環(huán)的劃分算法

連通域可由多邊形封閉環(huán)所圍成的區(qū)域來表示，封閉環(huán)的劃分與鄰接關系的確定是連通域劃分與確定其鄰接關系的前提。采用極左路徑法來劃分封閉環(huán)。以工程圖左下方端點為起始點，先采用極右路徑法遍歷出視圖的最大環(huán)(即最外輪廓環(huán))，再采用極左路徑法依次遍歷出最大環(huán)的子環(huán)。

算法的具體步驟如下:

Step 1.判斷圖元鏈表 TopViewList是否為空?是，結束。否，轉入Step2。

Step 2.從 TopViewList中取(xm，ym)且 x 優(yōu)先的極值點vif為初始點，按照逆時針檢測所有圖形節(jié)點。當遇到某一個節(jié)點v有多于2條邊時，采用極右路徑法，直到回到初始點vif為止。此時，獲得最大環(huán)Maxloop。

Step 3.以vif為初始點，按照逆時針檢測所有圖形節(jié)點。當遇到某一個節(jié)點v有多于2條邊沒有遍歷時，采用極左路徑法，并將該節(jié)點存入到Mlist鏈表中，若遇到某一個有多于2條邊沒有遍歷的節(jié)點v兩次，則終止并獲取兩次遇到該節(jié)點中間所經過的路徑存入環(huán)鏈表LoopsList中，轉入Step3重新開始。否則直到回到初始點vif為止，構成一個封閉回路C，即搜索到一個封閉環(huán)，存入LoopsList中。

Step 4.判斷Mlist是否為空?是，結束;否，轉入Step5。

Step 5.從Mlist鏈表中移取一個節(jié)點v，然后以該點為起始點，判斷與該節(jié)點的相鄰邊是否有未遍歷的?是，令vif=v，重復Step3;否，轉入Step6。

Step 6.將上述所有涉及的圖元從TopViewList刪除，轉入Step1。

以圖1舉例說明對最大環(huán)Maxloop進行一步步細分獲得子環(huán)的過程。

圖1 封閉環(huán)的劃分過程

2.1.2 封閉環(huán)鄰接關系的類型及確定

按照封閉環(huán)之間的位置情況，環(huán)之間的鄰接關系可分為包含、分離、相鄰三大類。其中包含包括點包含和空包含。相鄰分為點相鄰和邊相鄰［5］。如表1所示。

?

首先選取掃描線，用掃描線分別與兩個環(huán)取交點。然后，根據交點的分布情況來判斷環(huán)與環(huán)之間的關系。具體步驟如下:

Step 1:分別計算出兩個環(huán)XY方向上的重合部分(xmin，xmax)，(ymin，ymax)，并取兩條直線 x=xb，y=yb且 xb∈(xmin，xmax)，yb(ymin，ymax)。若 XY 方向上都沒有重合部分，說明兩個環(huán)相離。

Step 2:兩條直線x=xb，y=yb分別與兩個環(huán)取交點，記錄交點坐標(b［i］)以及交點屬于哪個環(huán)(a［i］=1表示交點屬于環(huán) 1，a［i］=2表示交點屬于環(huán)2)，對交點坐標(b［i］)由小到大排序，并根據坐標值大小對a［i］排序。

Step 3:判斷b［i］中相鄰項是否有相同的點，若有，說明兩個環(huán)關系是邊相鄰。如圖2(a)所示。

Step 4:對 a［i］中的值進行判斷，若序列如(11222211)，1和2均是成對出現，則遍歷兩個環(huán)所有的線段，若存在分別屬于兩個環(huán)的兩條線段共一個端點，則兩個環(huán)鄰接關系為點相鄰如圖2(b)所示，否則相離如圖3(b)所示。若序列如(1221)或者(2112)，即 a［n］a［n+1］，則兩個環(huán)為包含關系。若a［0］=1則環(huán)1包含環(huán)2;若a［0］=2則環(huán)2包含環(huán)1。此時同樣遍歷兩個環(huán)所有線段，若存在分別屬于兩個環(huán)的兩條線段共一個端點則為點包含如圖3(c)所示，否則為空包含如圖3(a)所示。

圖2 相鄰關系交點重合點分布

圖2、圖3中細實線環(huán)表示環(huán)1，粗實線環(huán)為環(huán)2。圖3中虛線為兩個環(huán)相鄰所共有的線。圖3中數字1(2)分別表示環(huán)1(環(huán)2)與y=yb的交點。

圖3 包含分離關系交點分布

xb，yb是在兩個環(huán)的重合區(qū)域(xmin，xmax)，(ymin，ymax)中隨機選擇的。若y=yb或者x=xb正好經過環(huán)中某直線或者曲線端點(比如直線y=yb過三角形頂點如圖3(d)所示)，則交點為奇異點［6］，不能用其來判斷環(huán)與環(huán)之間的關系。所以必須首先采取去除奇異點的處理。保證系統計算結果正確。

2.2 連通域的劃分及鄰接關系判斷

2.2.1 連通域的定義

滿足下列兩個條件的區(qū)域，稱之為連通域。

(1)區(qū)域D是連通的，即D中任何兩點都可以用完全屬于D的一條折線連接起來。

(2)區(qū)域D是有界的，即D與其邊界一起構成一個閉區(qū)域或閉域，記做D。

在二維圖形中，連通域有單連通域和多連通域之分。若區(qū)域中的任意封閉實曲線可在區(qū)域中連續(xù)地收縮成一點，則該區(qū)域是單連通域;否則，為多連通域。在連通域中不存在孤立邊，即每條邊的兩端必然連接其他邊［5］。

2.2.2 連通域的劃分

在二維工程圖中，環(huán)的劃分是連通域的前提。把劃分的環(huán)分成兩種:一種是包含其他環(huán)的封閉環(huán)，稱之為A類環(huán);另一種就是不包含其他環(huán)的封閉環(huán)，稱之為B類環(huán)。

所有B類環(huán)包含的區(qū)域都是一個單連通域。而A類環(huán)中，均包含有其他環(huán)，假如環(huán)a包含環(huán)b，則環(huán)a與環(huán)b所包含的區(qū)域為多連通域。

綜上所述，在二維工程圖中，所有B類環(huán)各圍成一個單連通域，所有A類環(huán)與其各自所包含的環(huán)共同圍成一個多連通域。用公式表示如下:

φA表示 A 類環(huán)的集合。φA=(x1，x2，x3，...，xn)

φB表示 B 類環(huán)的集合。φB=(y1，y2，y3，...，ym)

ω 表示所有環(huán)的集合。φA∪φB=ω，φA∩φB=?

φB表示所有B類環(huán)各自圍成的單連通域的集合。φB=(X1，X2，X3，...，Xn)

φA表示所有A類環(huán)與各自所包含的環(huán)共同圍成的多連通域的集合。其中YmZm表示環(huán)ym包圍環(huán)zm形成的多連通域，ym∈φB，zm∈ω。φA=(Y1Z1，Y2Z2，Y3Z3，...，YmZm)

Ω表示工程圖所包含的所有連通域的集合。φA∪φB=Ω，φA∩φB=?

2.2.3 連通域的鄰接關系判斷

連通域的鄰接關系可以由環(huán)的鄰接關系推斷出。環(huán)與環(huán)之間鄰接關系分為包含、分離、相鄰，則連通域的鄰接關系也分為包含、分離、相鄰三種。

假設

其中 a，b∈ω

其中 A，B∈Ω

若 A，B∈ΦA，則有 fc(A，B)=fl(a，b)。其中a，b為包圍 A，B 的封閉環(huán)，且有 a，b∈φA，如圖4(a)所示。

若 A∈ΦA，B∈ΦB，設 B=YiZi，若 a=zi，則 fc(A，B)=-2，如圖 4(b)所示;a≠zi，則 fc(A，B)=fl(a，yi)。其中 a∈φA，b∈φB，a 為包圍 A 的封閉環(huán)。yi為包圍多連通域B的兩個環(huán)中較大的環(huán)。zi為包圍多連通域B的兩個環(huán)中較小的環(huán)，如圖4(c)所示。若兩個環(huán)的關系是子包含，對應的兩個連通域關系歸為包含這一類。

3 實例驗證

在Visual C++集成開發(fā)平臺中，利用C++語言對該算法進行了驗證。以某一視圖為例，如圖5所示。Si表示由i環(huán)包圍而成的單連通域，Sij表示由i環(huán)包圍j環(huán)而成的多連通域(S10為單連通域)。其中第一個環(huán)是最大環(huán)不包圍形成任何連通域。環(huán)關系矩陣fl，fl(i，j)表示第i個環(huán)與第j個環(huán)之間的關系。參照上一節(jié)的公式得出:

連通域關系矩陣fc按照上一節(jié)算法由fl推導得出。

圖4 連通域鄰接關系確定

圖5 實例演示

4 結束語

在二維工程圖的特征識別中，圖元凹凸性，孔的通盲性，各種槽與型腔的識別，工藝語句與圖元匹配等都需要連通域的判別。連通域在二維工程圖特征識別的應用，為后續(xù)三維模型的重建工作打下基礎。

［1］ 張振明.現代CAPP的應用與發(fā)展趨勢［J］.CAD/CAM與制造業(yè)信息化，2004(2):30-31.

［2］ Shusheng Zhang，Yunfei Shi，Haitao Fan.Serial 3D model reconstruction for machining evolution of rotational parts by merging semantic and graphic process planning information［J］.Computer-Aided Design42(2010):781-794.

［3］ 石云飛，張樹生，成彬等.工藝語義驅動的序列三維模型構建系統［J］.計算機集成制造系統，2009，15(11):2133-2139.

［4］ Llados J，Marti E，Villanueva J J.Symbol recognition by error tolerant subgraph matching between region adjacency graphs［J］.IEEE Trans on Pattern Analysis and Machine Intelligence，2001，23(10):1137-1143.

［5］ 劉曉平，何士雙.基于三角劃分的多連通域圖形匹配研究［J］.工程圖學學報，2010(1):61-66.

［6］ 魏青松，史玉升，董文楚，等.基于水平掃描線算法的STL模型三維網格化［J］.華中科技大學學報的自然科學版，2006，34(4):86-88.