劉慶保，張樹生，范海濤

(西北工業(yè)大學(xué)現(xiàn)代設(shè)計(jì)與集成制造技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，西安710072)

1 引言

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

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

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

2 關(guān)鍵技術(shù)

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

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

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

算法的具體步驟如下:

Step 1.判斷圖元鏈表 TopViewList是否為空?是，結(jié)束。否，轉(zhuǎn)入Step2。

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

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

Step 4.判斷Mlist是否為空?是，結(jié)束;否，轉(zhuǎn)入Step5。

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

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

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

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

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

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

?

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

Step 1:分別計(jì)算出兩個環(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)取交點(diǎn)，記錄交點(diǎn)坐標(biāo)(b［i］)以及交點(diǎn)屬于哪個環(huán)(a［i］=1表示交點(diǎn)屬于環(huán) 1，a［i］=2表示交點(diǎn)屬于環(huán)2)，對交點(diǎn)坐標(biāo)(b［i］)由小到大排序，并根據(jù)坐標(biāo)值大小對a［i］排序。

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

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

圖2 相鄰關(guān)系交點(diǎn)重合點(diǎn)分布

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

圖3 包含分離關(guān)系交點(diǎn)分布

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

2.2 連通域的劃分及鄰接關(guān)系判斷

2.2.1 連通域的定義

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

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

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

在二維圖形中，連通域有單連通域和多連通域之分。若區(qū)域中的任意封閉實(shí)曲線可在區(qū)域中連續(xù)地收縮成一點(diǎn)，則該區(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ū)域?yàn)槎噙B通域。

綜上所述，在二維工程圖中，所有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 連通域的鄰接關(guān)系判斷

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

假設(shè)

其中 a，b∈ω

其中 A，B∈Ω

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

若 A∈ΦA(chǔ)，B∈ΦB，設(shè) 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)的關(guān)系是子包含，對應(yīng)的兩個連通域關(guān)系歸為包含這一類。

3 實(shí)例驗(yàn)證

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

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

圖4 連通域鄰接關(guān)系確定

圖5 實(shí)例演示

4 結(jié)束語

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

［1］ 張振明.現(xiàn)代CAPP的應(yīng)用與發(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］ 石云飛，張樹生，成彬等.工藝語義驅(qū)動的序列三維模型構(gòu)建系統(tǒng)［J］.計(jì)算機(jī)集成制造系統(tǒng)，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］.工程圖學(xué)學(xué)報，2010(1):61-66.

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