CAD圖形表示算法研究

吳磊

(吉林建筑大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，長(zhǎng)春130118)

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

關(guān)鍵詞：CAD；圖形表示；算法；工程設(shè)計(jì)

收稿日期：2015-01-15.

作者簡(jiǎn)介：吳磊(1978～)，男，吉林省長(zhǎng)春市人，實(shí)驗(yàn)師，碩士.

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

1圖形表示問(wèn)題基本算法研究

1.1求解兩線段交點(diǎn)問(wèn)題

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

1.2求解線段與平面交點(diǎn)問(wèn)題

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

2平面區(qū)域計(jì)算問(wèn)題研究

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

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

2.2確定點(diǎn)與區(qū)域之間關(guān)系

就平面問(wèn)題而言，點(diǎn)與區(qū)域之間關(guān)系無(wú)外乎有三種情況：區(qū)域內(nèi)、區(qū)域邊界及區(qū)域外.

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

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

2.3確定點(diǎn)與線段之間關(guān)系

線段所在直線能夠?qū)⑵矫鎰澐譃閮蓚€(gè)半平面.換句話說(shuō)，確定點(diǎn)與線段間的關(guān)系，就是要由公式(1)判別點(diǎn)是位于線段上側(cè)、下側(cè)還是線段及線段延長(zhǎng)線上.具體方法如下：如果A=0，則表示點(diǎn)位于線段或者線段延長(zhǎng)線之上；如果A>0，則表示點(diǎn)位于上側(cè)；如果A<0，則表示點(diǎn)位于在下側(cè).

2.4完成平面區(qū)域之間各項(xiàng)運(yùn)算問(wèn)題

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

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

(1)獲取兩區(qū)域邊界交點(diǎn)坐標(biāo).具體包括交點(diǎn)集(記作P)和序號(hào)集(記作L)；

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

(3)判定所有分割段性質(zhì).具體包括如下三種：一是重合段.即一個(gè)區(qū)域某分割段和另一區(qū)域?qū)?yīng)分割段為重合關(guān)系；二是域內(nèi)段.即一個(gè)區(qū)域某分割段位于在另一個(gè)區(qū)域內(nèi)部；三是域外段.即一個(gè)區(qū)域某分割段位于另一區(qū)域外部.

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

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

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

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

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

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

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

以平面第一區(qū)域?yàn)榛A(chǔ)，去掉第一區(qū)域與第二區(qū)域的公共部分.用這樣的方式得到的剩余區(qū)域，即為兩封閉區(qū)域的差.兩區(qū)域差的結(jié)果可能為如下情形：

(1)差為第一區(qū)域，而第二區(qū)域?yàn)椴钪锌斩矗?/p>

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

(3)第一區(qū)域自身(此時(shí)第二區(qū)域遠(yuǎn)離第一區(qū)域).差的求解過(guò)程需要依靠求交過(guò)程，即在第一區(qū)域內(nèi)將上述求交的結(jié)果去掉.

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

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

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

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

(3)如此推進(jìn)線點(diǎn)數(shù)<1，則轉(zhuǎn)(9)；

(4)完成推進(jìn)線上最左點(diǎn)i(第0點(diǎn)除外)的搜索過(guò)程；

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

(6)完成目標(biāo)推進(jìn)線plt生成過(guò)程；

(7)如果plt(1)[x]>plt(0)[x]，則以plt(0)作為旋轉(zhuǎn)點(diǎn)，以plt(0)-plt(1)為起始邊沿順時(shí)針?lè)较虿粩嗨阉?，依次得到所有三角形?/p>

(8)實(shí)現(xiàn)下一個(gè)推進(jìn)線plt生成過(guò)程；

(9)結(jié)束本算法.

4結(jié)語(yǔ)

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

參考文獻(xiàn)

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

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

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

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