23計算幾何應(yīng)用技術(shù)

《23計算幾何應(yīng)用技術(shù)》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、2.3計算幾何應(yīng)用技術(shù)山于大量的應(yīng)用領(lǐng)域提供了特有的幾何問題，對于這些問題必須建立有效的算法，這就是孕育計算機(jī)幾何這門學(xué)問的基礎(chǔ)。特別是CAD領(lǐng)域，提岀的一系列問題需要計算幾何基礎(chǔ)理論的支持。例如，采用何種數(shù)學(xué)模型進(jìn)行離散點的插值或擬合問題，表面看來這各問題并不復(fù)雜，但深入考慮則產(chǎn)生了問題：數(shù)學(xué)方程形式往往與坐標(biāo)系Z間具冇密切的聯(lián)系，CAD系統(tǒng)希望擺脫坐標(biāo)系的約束，采用幾何特征量建立曲線方程，這樣就可以采用統(tǒng)一的方程形式，不必根據(jù)情況專門進(jìn)行朋標(biāo)變換，也不必為出現(xiàn)多值函數(shù)1佃頭疼了。又如，采用分片曲面描述地形衣面或設(shè)計農(nóng)面時，需要

2、采用適當(dāng)?shù)乃惴ń鉀Q判定給定點位于哪一個曲面分塊之中的問題。2.3.1曲線擬合與插值對于計算機(jī)所處理的某些問題，將一條曲線表示成為一個彖素序列可能是非常合適的，但對于刃一些問題，則希望曲線能夠冇一個數(shù)學(xué)表達(dá)式。找出一條通過一組給定點的曲線是一個插值問題，而找出一條近似地通過一組給定點的曲線則是逼近問題，曲線擬合則是一個????統(tǒng)稱以上兩類問題的術(shù)語。2.3.1.1多項式插值令(xi,yi),(X2,y2),???,(xH,yn)是平面上的點的序列，切對于iHj,x￥xj,能夠比較容易地得到(n-1)次的插值多項式公式。n(X-Xj)

3、Pn(x)=Eytn11(Xi-Xj)對于n=2的情況，則可以得到連接兩點的直線方程：(X-X2)(X-X1)I〉2(x)=yi+(Xi-X2)(X2-X1)多項式插值的主要缺點是曲線可能在給尬點ZI'可顯著震蕩，對于這一點我們可以通過如下的示例加以認(rèn)識。[例]給定5點：(0,0),(1,3),(2,0),(3,0),(4,0),插值多項式為:p(x)=-0.5x(x~2)(x~3)(x~4)該插值曲線具有三個極值點,位于(0.67,3.46),(2.46,-0.47),(3.5,0.66)。直觀上，我們可能會希望插值曲線在區(qū)間[

4、2,4]Z間基本上尸0,而在x=l吋具有一個極大值點，然而該曲線不具備這種特性(參見圖2-17[a])。圖田7多項式及分段多項孌插值曲線如果分段多項式插值，能夠在一處程度上克服上述缺點，例如，對于與上例相同的5個點，采用如卜?方程進(jìn)行插值，其曲線特征能夠得到顯著改善(圖2-17［b］)oPa(x)=6x(0.6-0.7x),0Wx<1.5;Pb(x)=5.4(x-2)2,l?5Wx〈2;Pc(x)=0,2WxW4.分段多項式的一般衣達(dá)形式為：p(x)=pi(x),XiWxWxi+i,i=0,1,,k-1P(J>i-i(x)=p(J

5、>i(x),j=0,1,,r-1,i=l,2,,k-1點X】,……,XkT把區(qū)間［a,b］分為k個子區(qū)間，通常將這些點稱為間斷點，對應(yīng)這些x值的曲線上的點稱為結(jié)點。間斷點上的連續(xù)性約束條件是山第二組方程衣示的，這里p(0>i(x)農(nóng)示Pi(x),而p⑴i(x)(j>0)表示p(x)的第j階導(dǎo)數(shù)。有時，用尸0表示沒有任何約束條件。當(dāng)"1時，我們得到了一個連續(xù)函數(shù)，但對于其導(dǎo)數(shù)沒有約束條件。設(shè)Pi(x)是m次多項式，如果r=m+l,就會得到一個在［a,b］上的簡單多項式。因此，是產(chǎn)生分段多項式的約束條件的最大數(shù)。2.3.1.2樣條曲線

6、的基本概念對于樣條這一概念可以通過繪圖員所使用的一種工具加以理解：他們經(jīng)常使用一把可以彎曲的木尺，通過適當(dāng)控制彎出一條通過指處數(shù)據(jù)點的曲線，作為繪圖的模板。從這一示例中可以看到，在CAD系統(tǒng)中可以采用樣條曲線描述設(shè)計對象的曲線特征，事實上在丄業(yè)領(lǐng)域樣條曲線很早就被應(yīng)用到船休放樣的工作之中。對于樣條曲線的研究主要關(guān)注兩個問題：間斷點的數(shù)量和位置，以及曲線所采用的數(shù)學(xué)形式。B樣條是一種廣為使用的樣條曲線，其突出優(yōu)點是對局部的修改不會引起樣條形狀變化的遠(yuǎn)距離傳播，也就是說修改樣條的某些部分時，不會過多地影響曲線的其它部分。設(shè)m為樣條的次

7、數(shù)，B樣條在(m+1)個了區(qū)間以外的其它了區(qū)間上其值都為0。在圖2-18中顯示了一次、二次和三次B樣條基函數(shù)的曲線形態(tài)。対于B樣條函數(shù)可以采用遞歸的方式加以定義：【定義2-1】第i個子區(qū)間上的常數(shù)(0次)B樣條函數(shù)為：{1,XiWxWxi+i(2-3)0,其它。在區(qū)I'可［xi,Xi?］上的第m次B樣條函數(shù)定義為：(X-X))(X“?+1-X)Ni,n(x)=Ni,m(x)+Nw,m(x)(2-4)(Xi.a-Xi)(Xu-Xi+1)根據(jù)式(2-3)ik(2-4),可以得到：一次B樣條函數(shù)為：xWxWxi+i(Xi+2一X)_Xi

8、)(2-5)x“iWxWxi+2(Xi42一XH1)二次樣條函數(shù)為：(Xi?2一Xi)(XiM--Xi)(X-Xi)(Xi+2-X)(X“2-Xi)(Xi+2一XiJ(X-2Xi+3)(Xi卜3一Xi+1)(Xi「3_Xi(X-Xi)'(Xi+3