圖形輪廓排序及頂點(diǎn)凹凸性判別的研究與實(shí)現(xiàn)

趙玉剛，張 健，于光偉，李海洋

（山東理工大學(xué) 機(jī)械工程學(xué)院，淄博 255049）

0 引言

在CAD/CAM系統(tǒng)中，尤其是在基于圖形交互式的自動編程系統(tǒng)中，圖形輪廓的排序及頂點(diǎn)凹凸性的快速自動識別是解決許多實(shí)際問題的基礎(chǔ)，也是計(jì)算機(jī)圖形學(xué)中一個(gè)基本的內(nèi)容。圖形輪廓的走向及其頂點(diǎn)凹凸性識別具有重要的使用價(jià)值，如在刀具軌跡路徑的生成、多邊形的三角剖析、輪廓特征點(diǎn)的基元關(guān)系判定、科學(xué)計(jì)算可視化和石材異型板上挖孔等方面均有應(yīng)用。在模型識別、圖像處理、曲面插值等方面常常遇到對多邊形區(qū)域或離散點(diǎn)進(jìn)行分割的問題，如能預(yù)先確定圖形輪廓各個(gè)頂點(diǎn)的凹凸性，就可使問題的解決得到簡化。

1 圖形輪廓的排序

在圖形交互式的數(shù)控自動編程系統(tǒng)CAD模塊中，按時(shí)間先后順序繪制的圖形輪廓不一定首尾順序連接，因此由繪圖系統(tǒng)提供的圖形元素在空間上是各自獨(dú)立的，而在數(shù)控加工中，要求各個(gè)圖元在空間上是連續(xù)的，即各個(gè)加工段之間是按順序首尾相連的，因此要對這些在空間域上雜亂無章的圖形元素按數(shù)控加工刀具軌跡所要求的順序進(jìn)行重新編排。

實(shí)現(xiàn)圖形輪廓的排序，其核心思想是端點(diǎn)跟蹤法。首先以選中的第一段圖形元素的終點(diǎn)為依據(jù)點(diǎn)，在其它圖形元素中尋找與這一點(diǎn)重合的端點(diǎn)。如果存在，則作為第二段圖形元素，且將這個(gè)端點(diǎn)作為第二段圖形元素的起點(diǎn)。如果不存在，則將第一段圖形元素的起點(diǎn)與終點(diǎn)互換，然后再重復(fù)上面的過程，直到找到第二段圖形元素。然后再以第二段圖形元素的終點(diǎn)作為依據(jù)點(diǎn)，繼續(xù)尋找下一段圖形元素。將各圖形元素按順序依次排序，形成一個(gè)首尾順序連接的封閉環(huán)。

圖1既是圖形輪廓排序的算法流程圖，其中一些參數(shù)的意義如下：N為圖形輪廓的邊數(shù)，Pi,1、Pi,2表示第i條邊的起點(diǎn)與終點(diǎn)坐標(biāo)。

圖1 圖形輪廓端點(diǎn)排序流程圖

從圖形輪廓排序的算法流程圖可以得到，以選擇的第一段圖形元素為起始邊，各邊按順序連接組成封閉環(huán)。而這個(gè)封閉環(huán)也具有了一定的走向，再通過下面的最值法來確定圖形輪廓的走向。

2 圖形輪廓走向的判定

通過上面圖形輪廓的排序，即可以得到一個(gè)圖形輪廓串聯(lián)環(huán)，而這個(gè)環(huán)是由一串坐標(biāo)組成。我們找到圖形輪廓所有頂點(diǎn)中的最高點(diǎn)，最高點(diǎn)的前一段圖元和后一段圖元構(gòu)成的兩個(gè)向量（即最高點(diǎn)連接的兩條邊的邊矢向量）做叉乘，根據(jù)叉乘符號判別多邊形是順時(shí)針還是逆時(shí)針，符合右手法則。

判斷圖形輪廓頂點(diǎn)的最高點(diǎn)，其算法流程如圖2。Pi,y代表第i條邊終點(diǎn)的縱坐標(biāo)值，N為圖形輪廓的邊數(shù)，j代表最高頂點(diǎn)所在的邊。

圖2 求解最高點(diǎn)的算法流程圖

平面圖形輪廓的特征點(diǎn)是指在多邊形的所有頂點(diǎn)中，Y坐標(biāo)值最大的那個(gè)頂點(diǎn)，即某圖形輪廓最上面的那個(gè)頂點(diǎn)。最高頂點(diǎn)終點(diǎn)所在的邊為j，這個(gè)頂點(diǎn)即為特征點(diǎn)。分兩種情況討論圖形輪廓的走向：第一種情況，，不妨設(shè)為第j條邊的向量，由起點(diǎn)指向終點(diǎn)，考察特征點(diǎn)處兩條相鄰邊矢的叉積，記：；第二種情況，j=N，即最高點(diǎn)為最后封閉環(huán)的終點(diǎn)，而考察特征點(diǎn)處兩條相鄰邊矢的叉積，記：。由的符號可知：符號為正時(shí)，圖形輪廓的走向?yàn)槟鏁r(shí)針（即四指的旋向?yàn)槟鏁r(shí)針），如圖3所示；反之，圖形輪廓的走向?yàn)轫槙r(shí)針（四指的旋向?yàn)轫槙r(shí)針），如圖4所示。

圖3 逆時(shí)針走向

圖4 順時(shí)針走向

用特征點(diǎn)法能夠快速確定平面圖形輪廓的發(fā)矢方向，并由此初步判別出圖形輪廓的走向。對于有圓弧存在的輪廓圖形環(huán)，由圓弧的走向決定，通過最大Y坐標(biāo)做垂直線，遍歷所有的圓弧圖元，搜索是否有圓弧圖元與這條垂直線相交（交點(diǎn)Y坐標(biāo)必須大于最大Y坐標(biāo)），如果存在，記錄圓弧圖元的數(shù)目。如果存在的圓弧圖元的數(shù)目為奇數(shù)時(shí)，則圖形輪廓環(huán)的方向反向；如果存在的圓弧圖元的數(shù)目為偶數(shù)時(shí)，則圖形輪廓環(huán)的方向不發(fā)生改變。

3 圖形輪廓頂點(diǎn)凹凸性自動識別

通過端點(diǎn)跟蹤法對圖形輪廓進(jìn)行排序及最值法判斷圖形輪廓的走向，便可識別出多邊形頂點(diǎn)的凹凸性。按邊的順序作矢量(j=1…N)，將沿圖形輪廓的走向旋轉(zhuǎn)到矢量方向，根據(jù)轉(zhuǎn)過的角度來判斷圖形輪廓的頂點(diǎn)的凹凸性。如果轉(zhuǎn)過的角度大于π，則圖形輪廓的此頂點(diǎn)為凹頂點(diǎn)；如果轉(zhuǎn)過的角度小于π，則多邊形的此頂點(diǎn)為凸頂點(diǎn)。

4 圖形輪廓排序及頂點(diǎn)凹凸性算法的實(shí)現(xiàn)

我們在計(jì)算機(jī)上用C++Builder，實(shí)現(xiàn)了圖形輪廓的排序、走向及頂點(diǎn)凹凸性的判斷，實(shí)驗(yàn)結(jié)果表明：此算法穩(wěn)定可靠、實(shí)現(xiàn)簡單、速度快。

圖5 CAD模塊繪制的多邊形頂點(diǎn)數(shù)據(jù)

圖6 排序后的多邊形頂點(diǎn)數(shù)據(jù)

圖5是在CAD/CAM自動編程系統(tǒng)的CAD模塊中，隨意繪制的多邊形各邊的端點(diǎn)數(shù)據(jù)，并以文本文檔的格式保存。經(jīng)過多邊形的排序，得到如圖6所示的多邊形頂點(diǎn)數(shù)據(jù)。通過圖6可以清晰的看到，將雜亂的數(shù)據(jù)整理成首尾順序連接的有向封閉多邊形。

圖7 多邊形的繪制

圖7為在CAD/CAM自動編程系統(tǒng)中，利用CAD模塊，初步建立的示范圖形。其中所標(biāo)注的數(shù)字所在的頂點(diǎn)是繪制的多邊形各邊的終點(diǎn)位置與前面的圖5相對應(yīng)，其中數(shù)據(jù)的順序也代表了繪制多邊形各邊的先后順序。假設(shè)在選擇多邊形各邊加工時(shí)，選擇的順序同樣按照圖形標(biāo)注的順序選擇。當(dāng)然也可以隨意的選擇多邊形各邊。經(jīng)過多邊形的排序、走向的確定及凹凸性的判別。最終得到的如圖8所示。

在圖8中，經(jīng)過圖形輪廓的排序、走向的確定及頂點(diǎn)凹凸性的判別，其結(jié)果顯示在統(tǒng)計(jì)窗口中，圖形輪廓包括了7條邊，在選擇多邊形加工時(shí)，選擇的順序?yàn)轫槙r(shí)針，得到兩個(gè)凹頂點(diǎn)，分別用實(shí)心小圓標(biāo)志。

圖8 多邊形的排序及凹凸點(diǎn)判斷

5 結(jié)束語

本文主要針對圖形輪廓的排序、走向的確定及頂點(diǎn)凹凸性的判別，進(jìn)行了分析和研究。在C++Builder環(huán)境下，驗(yàn)證算法的可行性，并實(shí)現(xiàn)了圖形輪廓頂點(diǎn)凸凹性的判別。該方法使用于各種平面圖形輪廓凹凸性的判別。而且在CAD/CAM自動編程系統(tǒng)中，具有很高的使用價(jià)值。

[1] 周培德.確定任意多邊形凸凹性頂點(diǎn)的算法[J].軟件學(xué)報(bào),1995,6(5):276-279.

[2] 史萬田.多邊形頂點(diǎn)為凸凹點(diǎn)的計(jì)算機(jī)識別方法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),1990,2(3):15-16,23.

[3] 萬書亭,韓慶瑤.平面多邊形凸凹性的頂角判別法[J].水利電力機(jī)械,2003,(4):6-8.

[4] 汪學(xué)明.多邊形頂點(diǎn)凸凹性識別算法的研究與實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用,2005,(8):1786-1788.

[5] 劉曉平.簡單多邊形方向及頂點(diǎn)凹凸性的快速判斷[J].工程圖學(xué)學(xué)報(bào),2005,(4):124-128.