10.4.2 Point /Parametric curve intersection 1. Rational polynomial curves Ro∩R=R(t)A≤t≤B Brute force elementary method We solve each of the following three nonlinear polynomial equations separately and we search for common real roots in a<t< B 0 t1,…,t (t)-30=0→t1,…,tn In principle, this elementary approach is "easy "for polynomials. However, in prad tice, this process is complex and inefficient and prone to numerical inaccuracies Preprocessing and subdivision method Use bounding box of R(t) to eliminate easily resolvable cases, with some level of subdivision(splitting) to reduce bo Concept of subdivision in rational arithmetic: To eliminate numerical error in the subdivision process(which can lead to erroneous decisions), rational arithmetic may be employed (if the input coefficients of R(t) are rational or Hoating point numbers). This can be easily done in object-oriented languages uch as C++ using operator overloading Continue subdivision until box is small -Then, we could use a numerical technique, such as F {R-R()2}t∈D1c[A,B nd use some t from the interval D1 as the initial approximation. Use of the square of the distance function is necessary to avoid possible divergence of the derivative of the distance function, if it approaches zero If the minimization process converges to to and VF(to)<8, t= to is the desired solution Implicitization(perhaps with box preprocessing) such as (o, yo)n f=r0),y=y(t)y Let us consider an example where a(t), y(t) are quadratic polynomials(the curve is a parabola). We will attempt to eliminate t to get a polynomial f(r, y)=0 which the a, y coordinates of all points on the curve satisfy. We start with the system =aot +bot +co aot+ bot t4+bot+co aot+ bot+co10.4.2 Point/Parametric curve intersection 1. Rational polynomial curves R0 ∩ R = R(t) A ≤ t ≤ B • Brute force elementary method: We solve each of the following three nonlinear polynomial equations separately and we search for common real roots in A ≤ t ≤ B. x(t) − x0 = 0 → t 0 1 , · · · ,t 0 n y(t) − y0 = 0 → t 00 1 , · · · ,t 00 n z(t) − z0 = 0 → t 000 1 , · · · ,t 000 n In principle, this elementary approach is “easy” for polynomials. However, in prac￾tice, this process is complex and inefficient and prone to numerical inaccuracies. • Preprocessing and subdivision method – Use bounding box of R(t) to eliminate easily resolvable cases, with some level of subdivision (splitting) to reduce box size. – Concept of subdivision in rational arithmetic: To eliminate numerical error in the subdivision process (which can lead to erroneous decisions), rational arithmetic may be employed (if the input coefficients of R(t) are rational or floating point numbers). This can be easily done in object-oriented languages such as C++ using operator overloading. – Continue subdivision until box is small. – Then, we could use a numerical technique , such as: F(t) = min{|R0 − R(t)| 2 } t ∈ D1 ⊂ [A, B] and use some t from the interval D1 as the initial approximation. Use of the square of the distance function is necessary to avoid possible divergence of the derivative of the distance function, if it approaches zero. – If the minimization process converges to t0 and q F(t0) < δ, t = t0 is the desired solution. • Implicitization (perhaps with box preprocessing) such as (x0, y0) ∩ {x = x(t), y = y(t)} Let us consider an example where x(t), y(t) are quadratic polynomials (the curve is a parabola). We will attempt to eliminate t to get a polynomial f(x, y) = 0 which the x, y coordinates of all points on the curve satisfy. We start with the system x = a0t 2 + b0t + c0 y = a 0 0 t 2 + b 0 0 t + c 0 0 ⇒ a0t 2 + b0t + c0 − x = 0 a 0 0 t 2 + b 0 0 t + c 0 0 − y = 0 10