【作者】 陈越强；

【导师】 冯玉瑜；

【作者基本信息】 中国科学技术大学 ， 计算数学， 2008， 博士

【摘要】 在计算机辅助几何设计中,几何信息的保存至关重要,而由于有些算法的近似性以及计算机浮点误差的存在,很多时候我们只能得到近似的结果。因此,为了保证一些几何处理中的信息不丢失,引进了区间算法的概念,也就是用一个区间来代替一个点来计算。这样就能保证理论上的精确结果包含于计算的结果中,从而避免了信息丢失。本文的主要研究内容为参数曲面的区间隐式化、区间曲面的降阶以及区间多项式的“零点”问题。我们首先说明了误差控制在计算机辅助几何设计和几何计算中的重要性,并回顾了关于这些问题的研究历史和现状,然后举例说明了引入区间算法的意义。文中首先讨论了有理B样条曲面的区间隐式化的问题,该问题是曲线情形的推广,对于曲面的相切求交等操作具有很好的应用价值。与曲线情况的先求中心曲线、再通过调整中心曲线得到边界的方法不同,本文采用直接求解区间隐式曲面的两个边界的方法。通过引入影响曲面几何形状的距离、能量、法向等约束建立最优化求解模型,然后给出了该问题的算法以及具体的算例,并讨论了该方法在实际中的应用。其次讨论区间样条曲面的降阶。区间曲面的降阶克服了减少几何处理复杂度的同时又避免了几何信息丢失的矛盾。本文分别考虑了张量积区间样条曲面的降阶,多边形域上三角剖分区间样条曲面的降阶以及区间PS曲面的降阶。接着,我们讨论了区间多项式的“零点”问题。我们知道,求解多项式的零点一直是个非常重要的工作,但是由于计算机浮点误差导致了其在实际应用中的一些限制,本文通过引入区间多项式的概念,避免了实际操作中的信息丢失。文中对于单变量情形,给出了“零点”的定义以及“零点”重数的定义,然后给出了多项式的Descartes法则、Budan-Fourier定理以及Sturm定理在区间多项式情形的推广。最后,我们考虑了两个双变量的区间多项式的“交点”个数问题,对判定两个代数曲线交点个数的Bezout定理进行了推广。更多还原

【Abstract】 Conservation of geometric information is very important for Computer Aided Geometric Design(CAGD), but only approximate results can be obtained in many cases for the approximation property of some algorithms and the existence of computer float error. Interval operation is presented to avoid information loss during some geometric procedure. Instead of a point, we use an interval that contains the given point in our computation. By this way, the theoretic accurate result is contained in the computation result and the information loss is avoided.In this paper, our main job is to study interval implicitization of parametric surface, reduction of interval surfaces and the number of "zero" s of an interval polynomial. The importance of error control in CAGD and geometric computation is explained, the history and the state-of-the-art of these problems are reviewed, and then some examples are given to illustrate the significance of interval operation.First, we study the interval implicitization of rational B-spline surfaces. This problem is the generation of the case of curves which is useful to surface operations, such as seeking the intersection of two tangent surfaces. Instead of the method used in the case of curves in which searching the centric curve is followed by searching the boundary curves, we directly seek the boundary surfaces of the interval implicit surface. By introducing the distance, energy and normal direction of the interval surface that determine the geometric shape, we establish an optimization model and give the algorithm of this problem. We give some examples illustrating the algorithm and discuss the application of this method.Secondly, we study degree reduction of interval spline surfaces. Degree reduction overcomes the contradiction between reducing the complexity of geometric process and avoiding the geometric information loss. Degree reduction of tensor product interval spline surfaces, triangular partition interval spline surfaces over polygonal domain and interval PS surfaces are respectively discussed.Thirdly, we study the number of the "zero" s of a univariate interval polynomial. Seeking the roots of polynomials is a very important job, but computer float error restricts its applications. In this thesis, we introduce interval polynomials which avoid the information loss. The definition of "zero" and its multiplicity are presented. Then we generalize Descartes rule, Budan-Fourier theorem and Sturm theorem for polynomials to interval polynomials.Finally, we study the number of "intersection" s of two multivariate interval polynomials and generalize Bezout theorem which determine the number of the intersections of two algebraic curves.更多还原