An iterative/subdivision hybrid algorithm for curve/curve intersection

1. Deuflhard, P., Heindl, G.: Affine invariant convergence theorems for Newton’s method and extensions to related methods. SIAM J. Numer. Anal. 16, 1–10 (1980)

   Article  MathSciNet  Google Scholar 

2. Farouki, R.T., Goodman, T.N.T.: On the optimal stability of the Bernstein basis. Math. Comput. 65(216), 1553–1566 (1996)

   Article  MATH  MathSciNet  Google Scholar 

3. Farouki, R.T., Kuspa, B.K., Manni, C., Sestini, A.: Efficient solution of the complex quadratic tridiagonal system for \(\mathcal{C}^{2}\) PH quintic splines. Numer. Algorithms 27, 35–60 (2001)

   Article  MATH  MathSciNet  Google Scholar 

4. Farouki, R.T., Rajan, V.T.: On the numerical condition of polynomials in Bernstein form. Comput. Aided Geom. Des. 4(3), 191–216 (1987). doi:10.1016/0167-8396(87)90012-4

   Article  MATH  MathSciNet  Google Scholar 

5. Hawat, R.N., Piegl, L.A.: Genetic algorithm approach to curve–curve intersection. Math.l Eng. Ind. 7(2), 269–282 (1998)

   MATH  MathSciNet  Google Scholar 

6. Heath, M.T.: Scientific Computing: An Introductory Survey. McGraw-Hill, New York (2005)

   Google Scholar 

7. Hoschek, J., Lasser, D.: Fundamentals of Computer Aided Geometric Design. A.K. Peters, Wellesley (1993). Translated by L.L. Schumaker

   MATH  Google Scholar 

8. Houghton, E.G., Emnett, R.F., Factor, J.D., Sabharwal, C.L.: Implementation of a divide-and-conquer method for intersection of parametric surfaces. Comput. Aided Geom. Des. 2(1–3), 173–183 (1985)

   Article  MATH  Google Scholar 

9. Hu, C.Y., Maekawa, T., Sherbrooke, E.C., Patrikalakis, N.M.: Robust interval algorithm for curve intersections. Comput. Aided Des. 28(6/7), 495–506 (1996)

   Article  Google Scholar 

10. Kantorovich, L.: On Newton’s method for functional equations (Russian). Dokl. Akad. Nauk SSSR 59, 1237–1240 (1948)

    Google Scholar 

11. Limaiem, A., Trochu, F.: Geometric algorithms for the intersection of curves and surfaces. Comput. Graph. 19(3), 391–403 (1995)

    Article  Google Scholar 

12. Maekawa, T., Patrikalakis, N.M.: Computation of singularities and intersections of offsets of planar curves. Comput. Aided Geom. Des. 10(5), 407–429 (1993)

    Article  MATH  MathSciNet  Google Scholar 

13. Maekawa, T., Patrikalakis, N.M.: Interrogation of differential geometry properties for design and manufacture. Vis. Comput. 10(4), 216–237 (1994)

    Article  Google Scholar 

14. Megiddo, N.: Linear programming in linear time when the dimension is fixed. J. ACM 31, 114–127 (1984)

    Article  MATH  MathSciNet  Google Scholar 

15. Mortenson, M.E.: Geometric Modeling. Wiley, New York (1985)

    Google Scholar 

16. Patrikalakis, N.M.: Surface-to-surface intersections. IEEE Comput. Graph. Appl. 13(1), 89–95 (1993)

    Article  Google Scholar 

17. Rubin, S.M., Whitted, T.: A 3-dimensional representation for fast rendering of complex scenes. SIGGRAPH Comput. Graph. 14(3), 110–116 (1980)

    Article  Google Scholar 

18. Sederberg, T.W., Nishita, T.: Curve intersection using Beźier clipping. Comput. Aided Des. 22(9), 538–549 (1990). doi:10.1016/0010-4485(90)90039-F

    Article  MATH  Google Scholar 

19. Srijuntongsiri, G.: Finding all intersections between planar curves. In: ECTI-CON 2010, pp. 1241–1244 (2010)

    Google Scholar 

20. Srijuntongsiri, G., Vavasis, S.A.: A condition number analysis of a line–surface intersection algorithm. SIAM J. Sci. Comput. 30(2), 1064–1081 (2007)

    Article  MathSciNet  Google Scholar 

21. Srijuntongsiri, G., Vavasis, S.A.: Properties of polynomial bases used in a line-surface intersection algorithm. In: Parallel Processing and Applied Mathematics (2009)

    Google Scholar 

22. Whitted, T.: An improved illumination model for shaded display. Commun. ACM 23(6), 343–349 (1980)

    Article  Google Scholar 

Download references