多項式方程求根的裁剪方法及應(yīng)用研究.pdf

1、多項式求根和計算點到曲線的最小距離是計算機輔助設(shè)計與圖形學(xué)領(lǐng)域的基本問題之一。它有著廣泛的應(yīng)用,比如游戲中普遍存在的碰撞檢測、數(shù)控加工中加工刀具與加工物體的干涉檢測、幾何造型系統(tǒng)中點到曲面的距離查詢,也可用于評價曲線的擬合精度和輪廓度誤差、曲線曲面的匹配等。
　　本文的主要研究內(nèi)容包括:首先,針對多項式求根問題,提出了基于R1空間相切的三次幾何裁剪方法。跟傳統(tǒng)的方法相比,新方法具有相同的逼近階,同時顯著地提高了計算效率。直接構(gòu)造出

2、兩條三次多項式,使得很多情形下都可以在給定區(qū)間內(nèi)直接包住給定的多項式,從而避免了現(xiàn)有方法中耗時的誤差估算。在一定條件下,直接構(gòu)造的多項式同時還是誤差最小的包圍多項式,改善了逼近誤差。其次,針對多項式求根問題,提出了基于R2空間內(nèi)的三次幾何裁剪新方法。同以往的基于R1空間內(nèi)的方法相比,新方法具有更高的逼近階,即5階。幾何裁剪方法仍保留了Bernstein基函數(shù)較好的計算穩(wěn)定性,同時提高了收斂速度,顯示了較明顯的優(yōu)勢。很多情況下,給定多項式

3、f(t)的根,可被新方法中直接構(gòu)造的三次多項式對應(yīng)的實根包住,因此節(jié)省了計算包圍多項式的大量計算。實例也說明了新方法具有更高的計算效率和更快的收斂速度。最后,提出了基于曲線逼近的點到曲線最小距離計算方法。將本文的幾何裁剪思路應(yīng)用到點/曲線最小距離的計算中。首先用若干段二次曲線去逼近給定的曲線,點/二次曲線的最小距離可以有顯式的解析解,求解計算可以較為簡便高效。同時,利用幾何逼近的理論來估算給定曲線與二次逼近曲線間相應(yīng)的誤差,從而快速排除