An iterative/subdivision hybrid algorithm for curve/curve intersection

被引：0
作者：
Gun Srijuntongsiri
机构：
[1] Thammasat University,Sirindhorn International Institute of Technology
来源：
The Visual Computer | 2011年 / 27卷
关键词：
Curve/curve intersection; Newton’s method; Subdivision method;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
The problem of finding all intersections between two space curves is one of the fundamental problems in computer-aided geometric design and computational geometry. This article proposes a new iterative/subdivision hybrid algorithm for this problem. We use a test based on Kantorovich’s theorem to detect the starting point from which Newton’s method converges quadratically and a subdivision scheme to exclude certain regions that do not contain any intersections. Our algorithm is guaranteed to detect all intersections in the domain for nondegenerate and non-ill-posed cases.
引用
收藏
页码：365 / 371
页数：6
相关论文
共 36 条
  • [1] Deuflhard P.(1980)Affine invariant convergence theorems for Newton’s method and extensions to related methods SIAM J. Numer. Anal. 16 1-10
  • [2] Heindl G.(1996)On the optimal stability of the Bernstein basis Math. Comput. 65 1553-1566
  • [3] Farouki R.T.(2001)Efficient solution of the complex quadratic tridiagonal system for Numer. Algorithms 27 35-60
  • [4] Goodman T.N.T.(1987) PH quintic splines Comput. Aided Geom. Des. 4 191-216
  • [5] Farouki R.T.(1998)On the numerical condition of polynomials in Bernstein form Math.l Eng. Ind. 7 269-282
  • [6] Kuspa B.K.(1985)Genetic algorithm approach to curve–curve intersection Comput. Aided Geom. Des. 2 173-183
  • [7] Manni C.(1996)Implementation of a divide-and-conquer method for intersection of parametric surfaces Comput. Aided Des. 28 495-506
  • [8] Sestini A.(1948)Robust interval algorithm for curve intersections Dokl. Akad. Nauk SSSR 59 1237-1240
  • [9] Farouki R.T.(1995)On Newton’s method for functional equations (Russian) Comput. Graph. 19 391-403
  • [10] Rajan V.T.(1993)Geometric algorithms for the intersection of curves and surfaces Comput. Aided Geom. Des. 10 407-429
1234