計(jì)算幾何小論文（英文）

1、computational geometrycollege of grudation post gruduate class3 grade2008 computational mathematics (2008010320)computational geometry is a geometrical branch of computational mathematics, approximation theory, differential geometry, algebraic geometry and computer science it has very important theo

2、tetical significance not only in geometry but also in cad, cam, computer graphics, image processing and other concerned field has important value computational geometry is a lively sub field in theotetical computer science. the achievement has been use in computer graphics, chemistry, statistical an

3、alysis, pattern recognition, geographical database and some other fields. how to supply all kinds of basic effective algorithm theotetical foundation is always the research direction of native and abroad scholors1 the mathematical basis of computational geometry.computational geometry includes weier

4、stras theorem, the optimal unifoim approximation, quadratic approximation, polynomial interpolation, spline and multivariate spline(1) weierstras theoremsuppose f (%) e ca,b, then for any given £0 , it exists such polynomial p(x), such that maxlp(x)-/(x)| < £a<x<b 11weierstras the

5、orem proves that any continous polynomial from a.b could be approached by polynomial.(2) the optimal uniform approximation (tchebyshev )：p(x) is the optimal unifoim polynomial of pn when f (x) g ca. b, if and only if:p(x) f m has a sequence no less than n + 2 at a,b.<x2 < <, n >n + 2it c

6、ould get to a(p) by the form of negative and positive and the optimal uniform approximation is sole.(2) polynomial interpolationpolynomial interpolation includes lagrange interpolation, newton interpolation, hermite interpolation and other interpolations. by lagrange as an example:0?（兀）=（兀_首）（兀_兀）（兀

7、_£）2 the basic theory of curved shape and curved surface.the basic theory of curved shape and curved surface include: representation, basic terms, geometrical joint and basic formula. the representation of curved shape and curved surface include: parametric representation and algebraic represen

8、tation.(1) the first basic formulas2 = p2 = p- pt = (u v)(ph)(rupvx.) =vuv)f( ) = pf pvs means the arc length and f幾仇、cpjpvpv )(2) the second basic formulas? ke n = p g 卩丁 g =(e'puuan，、3 the splines curved shape and curved surface of b.by the basic function of bernstein we constructed the curved

9、 shape and curved surface of bezier. because the polynomial has strong terms of globality, so in actual use we generally take subsection, low power and smooth curved shape and curved surface of bezie匚 the mathod of b splindes contains the advantages of bezier and also has the anvantage of subsection

10、 changes.(1) the basic univariate spline. the basic spline define of b.given a division of axis u :u :< um j = 0, ± 1, ), by the style of recursion wedetermine the nj p(w) and it is call the concerned the division of p powe匚 namely, /； +1 power of basic univariate spline of bl.w ewpw.+1)othe

11、rshll w；. n 11 un,。(u)=ng ) +叫w(«), p > 2ui+p ui坷+“+i 一色+idefine: = 00the formular above is called de boor-cox. u is called sequence node. ui is called node.if uj_i<uj=u=-' = uj+l_<uj+lthen uju j+l_ is called / multiple node of u .(2) the spline curve of b.suppose there exists h +

12、1 vectors £；()w/?', ni p(u) is p power basic spline function (. n > p ) which defined on the nodes of u =+.(色 < 曾+i=0,1,昇2 + ) then we call polyline也)=£側(cè)衛(wèi))，ueup,un+li=0is the concerned p power basic spline on nodes vectors u 片 is called control vertex polyli ne pq is the control

13、polygon.(3) the curved surface of b.given space vector of (m + /?) x (z? + q)pjj w /?3(j =+ 1,.，加 _l,j = _g,= g + l,.,n_l)ni p(«) and a(v) are p power and q power spline function which are defined on nodes of =dp，dp+i，上加+pandv = 匕？，匕好，比+? and the concerned tensor surfacep(c)=工 s pi.jn“a)nj,qe),

14、 (w,v)gw0,m/jxv0,vji=-p j=-qare called a pxq power curved surface of b. j is called control vertex. by line joins the neighobor control vertex of the same row and column. the formed polyline grid is called controlgrid. parameter section4 the rational curved shape and curved surface of bezier and mat

15、hodof nurbs.as we take basic function of bernstein, it has many advantages of terms. but as thepolynomial but it has some flaws to show some curves so we should take n power of rationalbasic function of bernstein.r：=噸，2 0,/=（）given n + 1 space vectors of pi e (, = 0丄,)，we call n power parametersecti

16、on2嚴(yán)“r=()0</<l/=0/=0as one n power rational curve of bezier. pi is called control vertex on turns we use line to join the neighbour pi, the formed polygon is called bezier polygon or called control polygon. coi is called weight factor or weight.by the restriction of many mathods, computational geometry also