13472J/1.128J/2158J/16940J COMPUTATIONAL GEOMETRY Lectures 10-12 N.M. Patrikalakis Massachusetts Institute of Technology Cambridge MA 02139-4307 USA Copyright 2003 Massachusetts Institute of Technology Contents 10.1 Overview of intersection problems 10.2 Intersection problem classification 5 10. 2. 1 Classification by dimension 10.2.2 Classification by type of geometr 10.2.3 Classification by number system 6 10.3 Point /point"intersection 7 10.4 Point/curve intersection 10.4.1 Point/Implicit curve intersection 10.4.2 Point /Parametric curve intersection 10.4.3 Point/Procedural parametric (offset, evolute, etc. curve intersection 10.5 Point /surface intersection 10.5.1 Point/Implicit(usually algebraic)surface intersection 10.5.2 Point/Rational polynomial surface intersection 13 10.5.3 Point /Procedural surface intersection 10.6 Curve/curve intersection 20 10.6.1 Case D3: RPP/IA curve intersection 10.6.2 Case D1: RPP/RPP Curve Intersection 10.6.3 Case D2 /D5: RPP/PP and PP/PP Curve Intersections 10.6.4 Case D6: PP/IA Curve Intersection 10.6.5 Case D8: IA/IA Curve Intersection 10.7 Curve/ surface intersection 10.7. 1 Case E3: RPP Curve/IA Surface Intersection 10.7.2 Case El: RPP Curve/RPP Surface Intersection 10.7.3 Case E2/E6: RPP/PP, PP/PP Curve/Surface Intersection 10.7.4 Case E7: PP Curve/IA Surface Intersection13.472J/1.128J/2.158J/16.940J COMPUTATIONAL GEOMETRY Lectures 10 - 12 N. M. Patrikalakis Massachusetts Institute of Technology Cambridge, MA 02139-4307, USA Copyright c 2003 Massachusetts Institute of Technology Contents 10.1 Overview of intersection problems . . . . . . . . . . . . . . . . . . . . . . . . . 3 10.2 Intersection problem classification . . . . . . . . . . . . . . . . . . . . . . . . . 5 10.2.1 Classification by dimension . . . . . . . . . . . . . . . . . . . . . . . . 5 10.2.2 Classification by type of geometry . . . . . . . . . . . . . . . . . . . . . 5 10.2.3 Classification by number system . . . . . . . . . . . . . . . . . . . . . . 6 10.3 Point/point “intersection” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 10.4 Point/curve intersection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 10.4.1 Point/Implicit curve intersection . . . . . . . . . . . . . . . . . . . . . 8 10.4.2 Point/Parametric curve intersection . . . . . . . . . . . . . . . . . . . . 10 10.4.3 Point/Procedural parametric (offset, evolute, etc.) curve intersection . 12 10.5 Point/surface intersection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 10.5.1 Point/Implicit (usually algebraic) surface intersection . . . . . . . . . . 13 10.5.2 Point/Rational polynomial surface intersection . . . . . . . . . . . . . . 13 10.5.3 Point/Procedural surface intersection . . . . . . . . . . . . . . . . . . . 19 10.6 Curve/curve intersection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 10.6.1 Case D3: RPP/IA curve intersection . . . . . . . . . . . . . . . . . . . 20 10.6.2 Case D1: RPP/RPP Curve Intersection . . . . . . . . . . . . . . . . . 27 10.6.3 Case D2/D5: RPP/PP and PP/PP Curve Intersections . . . . . . . . . 28 10.6.4 Case D6: PP/IA Curve Intersection . . . . . . . . . . . . . . . . . . . . 28 10.6.5 Case D8: IA/IA Curve Intersection . . . . . . . . . . . . . . . . . . . . 29 10.7 Curve/surface intersection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 10.7.1 Case E3: RPP Curve/IA Surface Intersection . . . . . . . . . . . . . . 30 10.7.2 Case E1: RPP Curve/RPP Surface Intersection . . . . . . . . . . . . . 31 10.7.3 Case E2/E6: RPP/PP, PP/PP Curve/Surface Intersection . . . . . . . 31 10.7.4 Case E7: PP Curve/IA Surface Intersection . . . . . . . . . . . . . . . 31 1