Reparameterization Method For Coincidence Detection Of Polynomial Curves And Root-finding Problem Of Polynomials

Coincidence detection between two curves and root-finding of polynomials are two fundamental problems of in Computer Aided Geometric Design(CAGD)and Computer Graphics(CG).They have wide applications such as in collision detection,curve/surface intersection,medial axis computation and point projection,and so on.This paper focuses on both the coincidence condition between two Bézier curves and root-finding of polynomials,and provides reparameterization-based method.It mainly includes:(1)The coincidence detection of two Bézier curves of an arbitrary degree.We discuss the coincidence detection problem between two Bézier curves of an arbitrary degree.The difficulties mainly lie in:(1)For a complete coincident case,the degree of some curves can be reduced by using reparameterization,while the existing methods based on original control polygon will fail;(2)For a partial coincident case,it needs to solve the coincident parts of the parameter intervals.This paper presents a method which turns the coincidence detection problem between two curves into a new one between two control polygons,by transforming a reparameterizable curve into a non-reparameterizable one.It improves the stability and precision of the coincidence detection.It also provides an explicit formula of the partial coincidence interval,which also makes the computation more efficient.(2)Provide a method for dealing with multiple roots of a univariable polynomial.If the given polynomial can be reparameterized into another polynomial of a lower degree,one can reduce the corresponding computational complexity.However,if polynomials cannot be reparameterized,we propose a method based on cubic clipping algorithm in R~3 space,and also provide rapid judgment and dealing for multiple root.So both the approximation order and the convergence rate can be improved.Numerical examples show convergence rate and computational stability of the new method.