An iterative/subdivision hybrid algorithm for curve/curve intersection

摘要

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 Kan-torovich'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.