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

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

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

2、的算法解決判定給定點(diǎn)位于哪一個(gè)曲面分塊之中的問(wèn)題。2.3.1曲線擬合與插值對(duì)于計(jì)算機(jī)所處理的某些問(wèn)題，將一條曲線表示成為一個(gè)象素序列可能是非常合適的，但對(duì)于另一些問(wèn)題，則希望曲線能夠有一個(gè)數(shù)學(xué)表達(dá)式。找出一條通過(guò)一組給定點(diǎn)的曲線是一個(gè)插值問(wèn)題，而找出一條近似地通過(guò)一組給定點(diǎn)的曲線則是逼近問(wèn)題，曲線擬合則是一個(gè)統(tǒng)稱以上兩類問(wèn)題的術(shù)語(yǔ)。2.3.1.1多項(xiàng)式插值令(x1,y1),(x2,y2),…，(xn,yn)是平面上的點(diǎn)的序列，切對(duì)于i≠j，xi≠xj，能夠比較容易地得到(n-1)次的插值多項(xiàng)式公式。n(x–xj)Pn(x)=∑yi∏─────i=1(xi-xj)對(duì)于n=

3、2的情況，則可以得到連接兩點(diǎn)的直線方程：(x–x2)(x–x1)P2(x)=y1─────+─────(x1-x2)(x2–x1)多項(xiàng)式插值的主要缺點(diǎn)是曲線可能在給定點(diǎn)之間顯著震蕩，對(duì)于這一點(diǎn)我們可以通過(guò)如下的示例加以認(rèn)識(shí)。[例]給定5點(diǎn)：(0,0),(1,3),(2,0),(3,0),(4,0)，插值多項(xiàng)式為：p(x)=-0.5x(x-2)(x-3)(x-4)該插值曲線具有三個(gè)極值點(diǎn)，位于(0.67,3.46),(2.46,-0.47),(3.5,0.66)。直觀上，我們可能會(huì)希望插值曲線在區(qū)間[2,4]之間基本上y=0，而在x=1時(shí)具有一個(gè)極大值點(diǎn)，然而該曲線不具備

4、這種特性（參見(jiàn)圖2-17[a]）。[a][b]圖2-17多項(xiàng)式及分段多項(xiàng)式插值曲線5第2章計(jì)算機(jī)輔助系統(tǒng)開(kāi)發(fā)基礎(chǔ)知識(shí)如果分段多項(xiàng)式插值，能夠在一定程度上克服上述缺點(diǎn)，例如，對(duì)于與上例相同的5個(gè)點(diǎn)，采用如下方程進(jìn)行插值，其曲線特征能夠得到顯著改善（圖2-17[b]）。Pa(x)=6x(0.6-0.7x),0≤x<1.5;Pb(x)=5.4(x-2)2,1.5≤x<2;Pc(x)=0,2≤x≤4.分段多項(xiàng)式的一般表達(dá)形式為：p(x)=pi(x),xi≤x≤xi+1,i=0,1,……,k-1p(j)i-1(x)=p(j)i(x),j=0,1,……,r-1,i=1,2,……,k

5、-1點(diǎn)x1,……,xk-1把區(qū)間[a,b]分為k個(gè)子區(qū)間，通常將這些點(diǎn)稱為間斷點(diǎn)，對(duì)應(yīng)這些x值的曲線上的點(diǎn)稱為結(jié)點(diǎn)。間斷點(diǎn)上的連續(xù)性約束條件是由第二組方程表示的，這里p(0)i(x)表示pi(x)，而p(j)i(x)（j>0）表示p(x)的第j階導(dǎo)數(shù)。有時(shí)，用r=0表示沒(méi)有任何約束條件。當(dāng)r=1時(shí)，我們得到了一個(gè)連續(xù)函數(shù)，但對(duì)于其導(dǎo)數(shù)沒(méi)有約束條件。設(shè)pi(x)是m次多項(xiàng)式，如果r=m+1，就會(huì)得到一個(gè)在[a,b]上的簡(jiǎn)單多項(xiàng)式。因此，r=m是產(chǎn)生分段多項(xiàng)式的約束條件的最大數(shù)。2.3.1.2樣條曲線的基本概念對(duì)于樣條這一概念可以通過(guò)繪圖員所使用的一種工具加以理解：他們經(jīng)常

6、使用一把可以彎曲的木尺，通過(guò)適當(dāng)控制彎出一條通過(guò)指定數(shù)據(jù)點(diǎn)的曲線，作為繪圖的模板。從這一示例中可以看到，在CAD系統(tǒng)中可以采用樣條曲線描述設(shè)計(jì)對(duì)象的曲線特征，事實(shí)上在工業(yè)領(lǐng)域樣條曲線很早就被應(yīng)用到船體放樣的工作之中。對(duì)于樣條曲線的研究主要關(guān)注兩個(gè)問(wèn)題：間斷點(diǎn)的數(shù)量和位置，以及曲線所采用的數(shù)學(xué)形式。B樣條是一種廣為使用的樣條曲線，其突出優(yōu)點(diǎn)是對(duì)局部的修改不會(huì)引起樣條形狀變化的遠(yuǎn)距離傳播，也就是說(shuō)修改樣條的某些部分時(shí)，不會(huì)過(guò)多地影響曲線的其它部分。設(shè)m為樣條的次數(shù)，B樣條在(m+1)個(gè)子區(qū)間以外的其它子區(qū)間上其值都為0。在圖2-18中顯示了一次、二次和三次B樣條基函數(shù)的曲線

7、形態(tài)。圖2-18一、二、三次B樣條基函數(shù)對(duì)于B樣條函數(shù)可以采用遞歸的方式加以定義：【定義2-1】第i個(gè)子區(qū)間上的常數(shù)（0次）B樣條函數(shù)為：1，xi≤x≤xi+1Ni,0(x)=(2-3)0,其它。在區(qū)間[xi,xi+m+1]上的第m次B樣條函數(shù)定義為：(x–xi)(xI+m+1–x)Ni,m(x)=─────Ni,m-1(x)+──────NI+1,m-1(x)(2-4)(xi+m-xi)(xI+m+1–xI+1)根據(jù)式（2-3）及(2-4)，可以得到：一次B樣條函數(shù)為：5第2章計(jì)算機(jī)輔助系統(tǒng)開(kāi)發(fā)基礎(chǔ)知識(shí)(x–xi)──────,xi≤x