圖形輪廓排序及頂點凹凸性判別的研究與實現

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

（山東理工大學 機械工程學院，淄博 255049）

0 引言

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

1 圖形輪廓的排序

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

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

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

圖1 圖形輪廓端點排序流程圖

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

2 圖形輪廓走向的判定

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

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

圖2 求解最高點的算法流程圖

平面圖形輪廓的特征點是指在多邊形的所有頂點中，Y坐標值最大的那個頂點，即某圖形輪廓最上面的那個頂點。最高頂點終點所在的邊為j，這個頂點即為特征點。分兩種情況討論圖形輪廓的走向：第一種情況，，不妨設為第j條邊的向量，由起點指向終點，考察特征點處兩條相鄰邊矢的叉積，記：；第二種情況，j=N，即最高點為最后封閉環的終點，而考察特征點處兩條相鄰邊矢的叉積，記：。由的符號可知：符號為正時，圖形輪廓的走向為逆時針（即四指的旋向為逆時針），如圖3所示；反之，圖形輪廓的走向為順時針（四指的旋向為順時針），如圖4所示。

圖3 逆時針走向

圖4 順時針走向

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

3 圖形輪廓頂點凹凸性自動識別

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

4 圖形輪廓排序及頂點凹凸性算法的實現

我們在計算機上用C++Builder，實現了圖形輪廓的排序、走向及頂點凹凸性的判斷，實驗結果表明：此算法穩定可靠、實現簡單、速度快。

圖5 CAD模塊繪制的多邊形頂點數據

圖6 排序后的多邊形頂點數據

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

圖7 多邊形的繪制

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

在圖8中，經過圖形輪廓的排序、走向的確定及頂點凹凸性的判別，其結果顯示在統計窗口中，圖形輪廓包括了7條邊，在選擇多邊形加工時，選擇的順序為順時針，得到兩個凹頂點，分別用實心小圓標志。

圖8 多邊形的排序及凹凸點判斷

5 結束語

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

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

[2] 史萬田.多邊形頂點為凸凹點的計算機識別方法[J].計算機輔助設計與圖形學學報,1990,2(3):15-16,23.

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

[4] 汪學明.多邊形頂點凸凹性識別算法的研究與實現[J].計算機應用,2005,(8):1786-1788.

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