本文選題：基函數(shù) + 金字塔算法　； 參考：《華北理工大學(xué)》2017年碩士論文

【摘要】：金字塔算法(Pyramid Algorithms)是由美國(guó)數(shù)學(xué)家Ron Goldman首先提出來(lái)的,是一種動(dòng)態(tài)編程算法,因其形似金字塔,結(jié)構(gòu)清晰簡(jiǎn)單,表現(xiàn)算法全局能力強(qiáng),因此在多項(xiàng)式插值和逼近理論中得到廣泛應(yīng)用。在復(fù)雜的自由曲線曲面造型中,不可避免地要對(duì)曲線曲面的切向、曲率及包絡(luò)等變量進(jìn)行求解運(yùn)算,而該類(lèi)問(wèn)題一般都可轉(zhuǎn)化為基函數(shù)和導(dǎo)函數(shù)的求解。所以,研究樣條基函數(shù)快速且通用的構(gòu)造方法具有重要意義。基于傳統(tǒng)樣條插值逼近理論,系統(tǒng)地研究了金字塔算法在基函數(shù)構(gòu)建過(guò)程中的運(yùn)用。首先針對(duì)Lagrange,Newton及Hermite三類(lèi)插值基函數(shù),通過(guò)線性插值來(lái)構(gòu)建算法金字塔,綜合Neville和Aitken算法,分析了路徑路標(biāo)仿射組合系數(shù)的性質(zhì),得到了節(jié)點(diǎn)下標(biāo)的可交換性,有效減少了計(jì)算復(fù)雜度。通過(guò)數(shù)值算例,分析插值曲線拼接處的光滑性,驗(yàn)證了算法的優(yōu)越性。其次結(jié)合開(kāi)花(Blossom)理論,通過(guò)利用對(duì)稱(chēng)性及多仿射性將舊的開(kāi)花值遞推得到新的開(kāi)花值,來(lái)推導(dǎo)一元B樣條基函數(shù)的算法金字塔�；诼窂铰窐�(biāo)的對(duì)稱(chēng)平行性質(zhì),通過(guò)倒轉(zhuǎn)金字塔來(lái)減少計(jì)算復(fù)雜度,得到基函數(shù)的向下遞推算法。并且對(duì)相鄰路徑進(jìn)行交叉重疊,實(shí)現(xiàn)了拼接節(jié)點(diǎn)處光滑性的簡(jiǎn)單證明。進(jìn)一步將算法在x,y兩個(gè)方向上進(jìn)行雙線性插值,得到矩形張量積基函數(shù)的金字塔算法,并分析了計(jì)算復(fù)雜度。針對(duì)矩形張量積節(jié)點(diǎn)處計(jì)算復(fù)雜度較高的問(wèn)題,將節(jié)點(diǎn)定義在三角形網(wǎng)格上,利用重心坐標(biāo)的仿射不變性,推廣到局部三角形B樣條曲面。通過(guò)對(duì)基函數(shù)構(gòu)造理論的分析和研究,設(shè)計(jì)了基于動(dòng)態(tài)編程的一般插值多項(xiàng)式及樣條曲線曲面生成的金字塔算法,為復(fù)雜曲線曲面和實(shí)體造型問(wèn)題提供了新的思路與方法,特別是對(duì)CAGD中需要對(duì)幾何變量進(jìn)行編程求解的問(wèn)題具有重要的應(yīng)用價(jià)值。
[Abstract]:Pyramid algorithm was first put forward by American mathematician Ron Goldman. It is a kind of dynamic programming algorithm. So it is widely used in polynomial interpolation and approximation theory. In the complex modeling of free curve and surface, it is inevitable to solve the tangential, curvature and envelope variables of curve and surface, but this kind of problem can be transformed into the solution of basis function and derivative function. Therefore, it is of great significance to study the fast and general construction method of spline basis function. Based on the traditional spline interpolation approximation theory, the application of pyramid algorithm in the construction of basis functions is systematically studied. Firstly, the algorithm pyramid is constructed by linear interpolation for Lagrange Newton and Hermite interpolation basis functions. The properties of affine combination coefficients of path signs are analyzed by synthesizing Neville and Aitken algorithms, and the commutativity of node subscript is obtained. The computational complexity is reduced effectively. By numerical example, the smoothness of interpolation curve splicing is analyzed, and the superiority of the algorithm is verified. Secondly, based on the Blossom-blooming theory, the new flowering value is obtained by using symmetry and multi-affine to derive the algorithm pyramid of B-spline basis function. Based on the symmetry and parallelism of path signs, the computational complexity is reduced by turning the pyramids upside down, and the downward recursive algorithm of the basis function is obtained. And the adjacent paths are crossed and overlapped, and a simple proof of smoothness of the spliced nodes is realized. The algorithm is further interpolated bilinear in XY direction to obtain the pyramid algorithm of rectangular tensor product basis function, and the computational complexity is analyzed. In order to solve the problem of high computational complexity at rectangular tensor product nodes, the nodes are defined on triangular meshes and generalized to local triangular B-spline surfaces by using affine invariance of barycentric coordinates. Based on the analysis and research of basis function construction theory, a pyramid algorithm for generating general interpolation polynomial and spline curve and surface based on dynamic programming is designed, which provides a new way of thinking and method for complex curve and surface and solid modeling problem. Especially, it has important application value to solve the problem of geometric variables in CAGD.
【學(xué)位授予單位】：華北理工大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類(lèi)號(hào)】：O241.3

【參考文獻(xiàn)】

相關(guān)期刊論文 前10條

1 陳偉;蔡占川;;一種顯式Hermite曲線插值方法[J];計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào);2016年08期

2 郭嘯;韓旭里;黃琳;;逼近三次B樣條導(dǎo)矢曲線的四次Hermite插值樣條[J];圖學(xué)學(xué)報(bào);2016年02期

3 王慧;朱春鋼;李彩云;;六次PH曲線G~2 Hermite插值[J];圖學(xué)學(xué)報(bào);2016年02期

4 李軍成;謝煒;;自動(dòng)滿足C~2連續(xù)的帶參數(shù)五次Hermite插值樣條[J];浙江大學(xué)學(xué)報(bào)(理學(xué)版);2016年02期

5 王鳳玲;陳慶林;孫麗男;;Lagrange、Newton、Hermite插值法MATLAB算法比較研究及應(yīng)用[J];黑河學(xué)院學(xué)報(bào);2015年06期

6 席博彥;祁鋒;;s-對(duì)數(shù)凸函數(shù)的Hermite-Hadamard型積分不等式[J];數(shù)學(xué)物理學(xué)報(bào);2015年03期

7 鄧四清;方逵;謝進(jìn);陳福來(lái);陸海波;;一種新的帶參數(shù)雙三次有理插值樣條的有界性與點(diǎn)控制[J];計(jì)算數(shù)學(xué);2010年04期

8 ;Global Continuity Adjustment and Local Shape Optimization Technique for Complex Trimmed Surface Model[J];Chinese Journal of Mechanical Engineering;2010年02期

9 郭清偉;熊建;朱功勤;;均勻B樣條曲線曲面的擴(kuò)展[J];計(jì)算機(jī)應(yīng)用與軟件;2010年04期

10 王仁宏;常錦才;;矩形剖分上一類(lèi)二元樣條空間與薄板純彎曲[J];應(yīng)用數(shù)學(xué)和力學(xué);2007年07期

相關(guān)博士學(xué)位論文 前1條

1 李彩云;曲線曲面造型中的若干相關(guān)問(wèn)題研究[D];大連理工大學(xué);2013年

相關(guān)碩士學(xué)位論文 前4條

1 楊玉婷;基于開(kāi)花的非均勻B樣條曲線細(xì)分[D];河北師范大學(xué);2012年

2 錢(qián)婷;ECT-B樣條的開(kāi)花研究[D];南京航空航天大學(xué);2011年

3 譚德松;基函數(shù)法構(gòu)造插值樣條曲線曲面[D];湖南師范大學(xué);2007年

4 岑培超;空間結(jié)構(gòu)參數(shù)曲面描述及網(wǎng)格劃分算法[D];浙江大學(xué);2006年

，

本文編號(hào)：1977845