Roots Of Polynomial Equations Clipping Methods And Application Research

Root-finding and calculate the minimum distance of a point to the curve, which arefundamental problem in the field of CAGD. This problem has applications in many areas, such asthe common game collision detection, collision detection robot contacts, NC machining tool andobject to be processed, the geometric surface modeling system from the midpoint to the query, canalso be used Evaluation of curve fitting and contour accuracy error, matching curves and surfacesand so on.The main contents of this paper include: Firstly, for polynomial root finding problem, wepresent a tangent method based on cubic clipping algorithm inR1space. Compared with thetraditional methods, this method has the same approximation order, significantly improve thecomputational efficiency at the same time. In the new method, two cubic polynomials are directlyconstructed, which can bound the given polynomial in many cases. Under certain conditions,directly constructed polynomial is also the smallest error surrounded polynomial, it improves theapproximation error. Secondly, for polynomial root finding problem, we present a new methodbased on cubic clipping algorithm inR2space. Compared with the conventional method based onR1space, the new method has a higher order of approximation, it is five. Cubic clipping methodretains the better computational stability of Bernstein basis function while improving theconvergence rate, showing the obvious advantages. In many cases, it directly constructs twopolynomials, whose roots can be used to bound the roots of f (t)within an interval, and thus avoidsthe time-consuming computation of surrounded polynomial. Examples also illustrate the newmethod has higher computational efficiency and faster convergence. Finally, we present a method tocalculate the minimum distance of a point to the curve based on curve approaching. The cubicclipping method is used in calculating the minimum distance of a point to the curve. Firstly we useseveral segments to approximate a given quadratic curve. The minimum distance from the point tothe quadratic curve can have explicit analytical solutions. The computation can be more efficientand simple, in the same time, the use of geometric approximation theory to estimate thecorresponding error between the quadratic approximation given curve and the curve. We canquickly exclude contains the closest point (minimum distance occurs at the corresponding point)range, significantly improves the stability and efficiency.