D. Manocha et J. Demmel, ALGORITHMS FOR INTERSECTING PARAMETRIC AND ALGEBRAIC-CURVES .2. MULTIPLE INTERSECTIONS, Graphical models and image processing, 57(2), 1995, pp. 81-100
Citations number
45
Categorie Soggetti
Computer Sciences, Special Topics","Computer Science Software Graphycs Programming
The problem of computing the intersection of parametric and algebraic
curves arises in many applications of computer graphics and geometric
and solid modeling. Previous algorithms are based on techniques from e
limination theory or subdivision and iteration and are typically limit
ed to simple intersections of curves. Furthermore, algorithms based on
elimination theory are restricted to low degree curves. This is mainl
y due to issues of efficiency and numerical stability. In this paper w
e use elimination theory and express the resultant of the equations of
intersection as a matrix determinant. Using matrix computations the a
lgorithm for intersection is reduced to computing eigenvalues and eige
nvectors of matrices. We use techniques from linear algebra and numeri
cal analysis to compute geometrically isolated higher order intersecti
ons of curves. Such intersections are obtained from tangential interse
ctions, singular points, etc. The main advantage of the algorithm lies
in its efficiency and robustness. The numerical accuracy of the opera
tions is well understood and we come up with tight bounds on the error
s using 64-bit IEEE floating point arithmetic. (C) 1995 Academic Press
, Inc.