Robust Algebraic Curve Intersections with Tolerance Control. (June 2022)

• Record Type: Journal Article
• Authors: Shao, Wenbing; Chen, Falai; Liu, Xuefeng
• Is Part Of: Computer aided design. Volume 147(2022)
• Publication Date: 2022-06
• Subjects: Algebraic curve -- Curve/curve intersection -- Subdivision method -- Krawczyk's method -- Sturm's theorem -- Resultant; Computer-aided design -- Periodicals; Engineering design -- Data processing -- Periodicals; Computer graphics -- Periodicals; Conception technique -- Informatique -- Périodiques; Infographie -- Périodiques; Computer graphics; Engineering design -- Data processing; Periodicals; Electronic journals; 620.00420285
• DOI: 10.1016/j.cad.2022.103236
• Languages: English
• ISSNs: 0010-4485

Abstract

Abstract: In this paper, a robust and efficient algorithm is proposed to calculate the intersection points of two planar algebraic curves with guaranteed tolerance. The proposed method takes advantage of the fundamental methods in the fields of CAGD, solution verification for nonlinear equations and symbolic computation. Specifically, the subdivision method is applied to quickly exclude the regions without intersection points, and then Krawczyk's method is used to find a sharp and guaranteed bound for the intersection points. For ill-conditional cases, Sturm's theorem is applied to determine if there are any intersection points in undetermined regions. We present examples to demonstrate the robustness and efficiency of our algorithm, and comparisons with classic methods and a state-of-the-art method are also provided. The method can be easily adapted to computing the intersection points of two parametric curves. Highlights: An algorithm is proposed to calculate the intersection of two algebraic curves. Subdivision method and Krawczyk's method are combined to find the solutions. Symbolic method is applied to address the ill conditional case. The algorithm is robust and efficient with tolerance control.