CAD圖形表示算法研究

吳磊

(吉林建筑大學計算機科學與工程學院，長春130118)

摘要：本文對CAD中圖形表示算法進行了深入討論，主要包括基本算法、平面區(qū)域計算和自然表面的數(shù)字化表示.本文算法的實施能更好地提高工程設計效率、管理工作水平以及迅速應付變化的能力.

關鍵詞：CAD；圖形表示；算法；工程設計

收稿日期：2015-01-15.

作者簡介：吳磊(1978～)，男，吉林省長春市人，實驗師，碩士.

中圖分類號：TP 391文獻標志碼：A

Research on Graphics Processing Algorithms in CAD

WU Lei

(SchoolofComputerScienceandEngineering,JilinJianzhuUniversity,ChangChun,China130118)

Abstract：In this paper we deeply discussed the graphics processing algorithms in CAD, which are mainly about the basic algorithm, the calculation of planar area and digital representation of natural surface．The application of these algorithms contributes to improving the quality of engineering design and management, as well as enhancing the capability of quick meeting emergencies.

Keywords:CAD；graphics display；algorithm；engineering design

0引言

CAD技術是計算機技術發(fā)展的一個重要分支，它的不斷發(fā)展和日趨完善能更好地幫助工程技術人員降低工作強度，是一項有力的工具和武器.就當前而言，計算機CAD技術已日益廣泛而深入地應用于工程設計和各項管理工作當中[1-2].運用CAD技術完成各項工程設計的一個顯著優(yōu)勢在于工作中的每一時刻都能夠保證畫面的整潔與明晰.不僅如此，針對于任意設計環(huán)節(jié)與狀態(tài)，CAD技術均能實時準確地完成數(shù)據(jù)與信息的查詢與反饋.本文討論的重點在于各種CAD圖形表示的算法問題，而這些算法的有效運用能夠更好地提升工程設計效率、管理工作水平及迅速應付變化的能力.

1圖形表示問題基本算法研究

1.1求解兩線段交點問題

參數(shù)方程可以表示平面上的兩條線段，在此基礎上運用參數(shù)方程求取線段交點.具體操作為：判斷參數(shù)方程交點的參數(shù)值，若參數(shù)取值在0到1閉區(qū)間內，則意味著兩條線段存在交點；否則兩條線段無交點[3-4].

1.2求解線段與平面交點問題

根據(jù)解析幾何理論得知，兩點可以確定一條直線，而不在同一直線上的三點能夠確定一個平面，所以，求解線段與平面的交點，可以通過求取直線參數(shù)方程與平面參數(shù)方程的交點.若存在交點，且直線參數(shù)取值在0到1閉區(qū)間內，則意味著線段與平面存在交點；否則線段與平面無交點.

2平面區(qū)域計算問題研究

2.1計算平面區(qū)域面積

一般可由閉合多邊形描述工程問題中的平面區(qū)域.假設平面區(qū)域由坐標點(x1,y1)，(x2,y2)，…，(xn-1,yn-1)(xn,yn)順次連接而成，則可由公式(1)求得面積S的值.

2.2確定點與區(qū)域之間關系

就平面問題而言，點與區(qū)域之間關系無外乎有三種情況：區(qū)域內、區(qū)域邊界及區(qū)域外.

(1)運用射線法確定點與區(qū)域關系.此關系可根據(jù)從該點引出射線和區(qū)域上每條線段交點個數(shù)確定.如果有奇數(shù)個交點，則表示點位于區(qū)域內部，否則該點位于區(qū)域外部；

(2)運用轉角法確定點與區(qū)域關系.該問題可以通過求解連接該點與區(qū)域邊界各點間夾角代數(shù)α實現(xiàn).如果α=0，則表示該點位于區(qū)域外部；如果|α|=360°，則表示該點位于區(qū)域內部.此外，如果存在某一邊線，使該點到邊線的距離為零，則表示點位于區(qū)域邊界位置.

2.3確定點與線段之間關系

線段所在直線能夠將平面劃分為兩個半平面.換句話說，確定點與線段間的關系，就是要由公式(1)判別點是位于線段上側、下側還是線段及線段延長線上.具體方法如下：如果A=0，則表示點位于線段或者線段延長線之上；如果A>0，則表示點位于上側；如果A<0，則表示點位于在下側.

2.4完成平面區(qū)域之間各項運算問題

2.4.1求解兩平面區(qū)域的交.

兩平面區(qū)域共有部分就是兩區(qū)域的交.兩區(qū)域的交可能為如下情形：交有多塊；交有一塊；交為空(即不存在公共部分，兩區(qū)域彼此遠離)；通常而言，兩平面區(qū)域的交可以是任意多邊形，這是由于區(qū)域本身就是多邊形所圍成.由此可知，這個問題就是確定這個區(qū)域多邊形的位置描述，即該多邊形的各條邊界線段.具體步驟如下：

(1)獲取兩區(qū)域邊界交點坐標.具體包括交點集(記作P)和序號集(記作L)；

(2)確定由若干段組成的兩區(qū)域邊界.邊界線段是由相鄰交點按順序分割形成，即分割段；

(3)判定所有分割段性質.具體包括如下三種：一是重合段.即一個區(qū)域某分割段和另一區(qū)域對應分割段為重合關系；二是域內段.即一個區(qū)域某分割段位于在另一個區(qū)域內部；三是域外段.即一個區(qū)域某分割段位于另一區(qū)域外部.

為了判斷分割段的性質，這里采用如下方法.除端點外，只需判斷分割段上的任一其他點和另一區(qū)域間的位置關系.易知分割段的性質即與位置關系相對應.

(4)重合段、域內段所圍圖形即為兩區(qū)域的交.假設段集S1{s1i}是由第一區(qū)域的重合段和域內段共同構成，段集S2{s2i}由第二區(qū)域的重合段和域內段共同構成，則交可由如下方式求解.首先從S1中取得最前部分可用段，并記作s1i；而后在從S2中獲取段s2j(與s1i相鄰)，并標記；如果s2j的終點與s1i的起點重合，則意味著一個區(qū)域的交由s1i和s2j形成.否則，重新在集合Sl中獲取與s2j相鄰段s1i.執(zhí)行l(wèi)oop操作，直到最后的交將由若干段共同圍成.

2.4.2求解平面兩區(qū)域的并.

并由平面上兩區(qū)域所有公共部分構成.并的可能結果如下：

(1)并是一塊封閉區(qū)域，且其中可能存在若干空洞，即空間內任意點不歸屬兩區(qū)域之任意一個；

(2)兩區(qū)域之交是空集，即各自的兩塊.通過前面求解交的分析可知，求解并與求解交的不同在于并是由重合段、域外段所共同構成.并操作包含了兩區(qū)域的所有公共部分.

2.4.3求解兩封閉區(qū)域之差.

以平面第一區(qū)域為基礎，去掉第一區(qū)域與第二區(qū)域的公共部分.用這樣的方式得到的剩余區(qū)域，即為兩封閉區(qū)域的差.兩區(qū)域差的結果可能為如下情形：

(1)差為第一區(qū)域，而第二區(qū)域為差中空洞；

(2)差分為數(shù)塊；

(3)第一區(qū)域自身(此時第二區(qū)域遠離第一區(qū)域).差的求解過程需要依靠求交過程，即在第一區(qū)域內將上述求交的結果去掉.

3數(shù)字化任意自然表面算法研究

對于任意自然表面，如果采用手工處理方式，首先需要完成對應表面等高線圖的繪制，而后再使用前述等高線圖依次完成相應計算過程.然而，由于這種方式對提高計算機運算速度和自動化程度意義不大，所以現(xiàn)代計算機系統(tǒng)應用不多.基于此種考慮，這里在描述自然表面時使用三角網(wǎng)法，而這些三角形為不相交且兩兩一邊相鄰的，該三角網(wǎng)中每個三角形在同一投影面上的面積之和即為平面上自然表面的投影面積.假定已知欲描述的自然表面的特征點集(記作P)，該自然表面的形狀由這些特征點所控制，則三角網(wǎng)的生成算法可表示如下[4]：

(1)搜索P中存在的最左pz，進而尋找pn作為最近點；

(2)將pz-pn作為起始邊，向上、下半平面分別進行搜索，得到以其作為旋轉點的各三角形(所得三角形需要滿足搜索條件中頂角最大者條件)，并據(jù)此生成起始推進線(記作plt)；

(3)如此推進線點數(shù)<1，則轉(9)；

(4)完成推進線上最左點i(第0點除外)的搜索過程；

(5)將P(i)-P(i-1)作為起始邊，將P(i)作為旋轉點，各三角形的求解方式選擇逆時針旋轉，求解過程持續(xù)到所求點P為空(即推進線的末端點是P(i))，否則繼續(xù)點P(i+1)；

(6)完成目標推進線plt生成過程；

(7)如果plt(1)[x]>plt(0)[x]，則以plt(0)作為旋轉點，以plt(0)-plt(1)為起始邊沿順時針方向不斷搜索，依次得到所有三角形；

(8)實現(xiàn)下一個推進線plt生成過程；

(9)結束本算法.

4結語

對于各項工程實踐與研究領域，筆者探討的CAD圖形表示算法具有一定的實用價值.其計算工程涉及土方量、計算與設計各項鐵路和公路線路、施工計劃與進度編制、礦巖量計算、場地平整處理計算，以及與環(huán)境有關問題的計算任務，上述討論算法已有效運用于多項實際工程項目中，證明了本文所述成果的有效性與可行性.

參考文獻

[1]甘早斌,李志欣,彭彬.矢量圖形編輯系統(tǒng)的數(shù)據(jù)模型及其實現(xiàn)[J].計算機工程與科學,2005,27(6):48-50.

[2]韓成龍,呂志鵬,廖燕.基于VBA的AutoCAD二次開發(fā)及其應用[J].機械工程師,2007(5):41-42.

[3]冷長庚,李海強,周志毅.在CAD圖形系統(tǒng)中處理非圖形數(shù)據(jù)[J].組合機床與自動化加工技術,2001(5):33-34.

[4]張凱.露天礦土石方量的CAD圖形算法[J].酒鋼科技,2007(1):29-32.