Proof for the convergence rate

Although Yuan’s method [14] is based on cubic HybClip, it is mainly used to solve univariate polynomial root problems. However, a theoretical convergence rate or proof is not provided.

In this section, the theoretical results are provided on the convergence rate of the new curve/curve intersection algorithm. This begins with two technical lemmas:

Lemma 1. For any given polynomial P, there exists two constants CP and DP depending solely on P, such that for all intervals [α, β]  [0, 1] the lower bound m and the upper bound M generated in line 6 of Algorithm 1 satisfy

$${delta}_{mathrm{min}}=parallel P-m{parallel}_{infty}^{left[alpha, beta right]}le {C}_P{h}^4kern1em mathrm{and}kern1em {delta}_{mathrm{max}}=parallel P-M{parallel}_{infty}^{left[alpha, beta right]}le {D}_P{h}^4$$


where .

Proof. According to Eqs. (22) and (24), P(α) = m(α), P(β) = m(β), and P(t) ≥ m(t), t [α, β], and thus

$$P(t)-m(t)=left(t-alpha right)left(beta -tright)left({P}_1(t)-{m}_1(t)right)ge 0$$


where P1(t) is a continuous function of degree n − 2, and m1(t) is a linear function. Let g(t) = b0(β − t) + b1(t − α) be a line passing through the lowest control point and parallel to the line connecting the end points of P1(t), such that P1(t) − g(t) ≥ 0, t [α, β], and thus

$${P}_1(t)-{m}_1(t)le Cleft({P}_1(t)-g(t)right)$$


where the constant C depends solely on P.

$${displaystyle begin{array}{ll}{P}_1(t)-g(t)& =sumlimits_{i=0}^{n-2}{a}_i{B}_{i,left[alpha, beta right]}^{n-2}(t)-sumlimits_{i=0}^1{b}_i{B}_{i,left[alpha, beta right]}^1(t)\ {}& =sumlimits_{i=0}^{n-2}left({a}_i-{c}_iright){B}_{i,left[alpha, beta right]}^{n-2}(t),{a}_ige {c}_i,forall i\ {}& =left(beta -tright){P}_2(t)+left(t-alpha right){P}_3(t)end{array}},$$


where ({left{{c}_iright}}_{i=0}^{n-2}) are the control points of g after the degree elevation [1], ({P}_2(t)=sum_{i=0}^{n-3}left({a}_i-{c}_iright)left(genfrac{}{}{0pt}{}{n-2}{i}right){left(beta -tright)}^{i-1}{left(t-alpha right)}^{n-2-i}ge 0), and P3(t) = (an − 2 − cn − 2)(t − α)n − 3 ≥ 0.

Let t1, t2 be the minimum values of P2(t), P3(t) in [α, β], respectively, i.e.,

$${displaystyle begin{array}{ll}forall tin left[alpha, beta right]:& {P}_2(t)le {C}_1left({P}_2(t)-{P}_2left({t}_1right)right)={C}_1{P_2}^{prime}left({s}_1right)left(t-{t}_1right)le {C}_3left(beta -alpha right)\ {}mathrm{and}kern1em & {P}_3(t)le {C}_2left({P}_3(t)-{P}_3left({t}_2right)right)={C}_2{P_3}^{prime}left({s}_2right)left(t-{t}_2right)le {C}_4left(beta -alpha right)end{array}}$$


where s1, s2 [α, β]. Hence,

$${P}_1(t)-g(t)le {C}_3left(beta -tright)left(beta -alpha right)+{C}_4left(t-alpha right)left(beta -alpha right)le {C}_5{left(beta -alpha right)}^2$$


From Eqs. (34), (35), and (38),

$${displaystyle begin{array}{ll}left|P(t)-m(t)right|& le Cleft(t-alpha right)left(beta -tright)left({P}_1(t)-g(t)right)\ {}& le Cleft(t-alpha right)left(beta -tright){C}_5{left(beta -alpha right)}^2le {C}_P{left(beta -alpha right)}^4={C}_P{h}^4end{array}}$$


Similarly, |M(t) − P(t)| < DPh4.

Lemma 2. For any given polynomial P, there exist constants({C}_i^P,{D}_i^P,mathrm{with} i=0,1,2,3)depending solely on P, such that for all intervals [α, β]  [0, 1] the lower bound m and upper bound M generated in line 6 of Algorithm 1 for i {0, 1, 2, 3} satisfy

$$parallel {P}^{(i)}-{m}^{(i)}{parallel}_{infty}^{left[alpha, beta right]}le {C}_i^P{h}^{left(4-iright)}kern1em mathrm{and}kern1em parallel {P}^{(i)}-{M}^{(i)}{parallel}_{infty}^{left[alpha, beta right]}le {D}_i^P{h}^{left(4-iright)}$$


where(h=beta -alpha, parallel r{parallel}_{infty}^{left[alpha, beta right]}={max}_{tin left[alpha, beta right]}left|r(t)right|).

Proof A new norm in [α, β] is introduced as

$$parallel r{parallel}_{ast}^{left[alpha, beta right]}=parallel r{parallel}_{infty}^{left[alpha, beta right]}+hparallel {r}^{prime {parallel}_{infty}^{left[alpha, beta right]}}+{h}^2parallel {r}^{{primeprime} {parallel}_{infty}^{left[alpha, beta right]}}+{h}^3parallel {r}^{(3)}{parallel}_{infty}^{left[alpha, beta right]}$$


According to the equivalence of norms in a finite-dimensional real linear space, there exists a constant C such that

$$parallel r{parallel}_{ast}^{left[alpha, beta right]}le Cparallel r{parallel}_{infty}^{left[alpha, beta right]}$$


where the constant C does not depend on the intervals [α, β], again owing to the affine invariance. Using arguments similar to those in the previous proof, let r = P − m,

$${displaystyle begin{array}{ll}& parallel P-m{parallel}_{ast}^{left[alpha, beta right]}\ {}& =parallel P-m{parallel}_{infty}^{left[alpha, beta right]}+hparallel {P}^{prime }-{m}^{prime }{parallel}_{infty}^{left[alpha, beta right]}+{h}^2parallel {P}^{{primeprime} }-{m}^{{primeprime} }{parallel}_{infty}^{left[alpha, beta right]}+{h}^3parallel {P}^{(3)}-{m}^{(3)}{parallel}_{infty}^{left[alpha, beta right]}\ {}& le Cparallel P-m{parallel}_{infty}^{left[alpha, beta right]}le {C}_P{h}^4end{array}}$$


Similarly, (parallel P-M{parallel}_{ast}^{left[alpha, beta right]}le Cparallel P-M{parallel}_{infty}^{left[alpha, beta right]}le {D}_P{h}^4).

From the above lemmas, the convergence rate can be analyzed using the HybClip algorithm. In Algorithm 1, if Q = 0, the curve/curve intersection problem P(t) = Q(s) becomes a root-finding problem P(t) = 0; that is, the cubic HybClip technique may be used to compute the roots of the polynomials and intersections of the two curves. These two cases are discussed separately.

Theorem 2. (Single root) If polynomial P has a root tin [α, β], and provided that this root has multiplicity 1, the sequence of the lengths of the intervals generated through cubic HybClip containing that root has the convergence rate d = 4.

Proof. Suppose that ([αi, βi])i = 0, 1, 2, …, which converges to t, is a sequence of intervals generated by Algorithm 1, with lengths hi = βi − αi. It is assumed that the first derivative satisfies P(t) > 0 (otherwise, the polynomial −P can be considered instead of P).

Two cubic Bernstein polynomials m and M can be obtained as the lower and upper bounds of P in [αi, βi] based on line 6 of Algorithm 1. Because P is continuous, and owing to Lemma 2, the following inequalities

$${displaystyle begin{array}{ll}& parallel {P}^{prime }-{P}^{prime}left({t}^{ast}right){parallel}_{infty}^{left[{alpha}_i,{beta}_iright]}le frac{1}{4}{P}^{prime}left({t}^{ast}right)kern1em mathrm{and}kern1em parallel {m}^{prime }-{P}^{prime }(t){parallel}_{infty}^{left[{alpha}_i,{beta}_iright]}le frac{1}{4}{P}^{prime}left({t}^{ast}right)\ {}& parallel {M}^{prime }-{P}^{prime }(t){parallel}_{infty}^{left[{alpha}_i,{beta}_iright]}le frac{1}{4}{P}^{prime}left({t}^{ast}right)end{array}}$$


hold for all but a finite number of values of i. These three inequalities above imply that

$${displaystyle begin{array}{ll}& parallel {m}^{prime }-{P}^{prime}left({t}^{ast}right){parallel}_{infty}^{left[{alpha}_i,{beta}_iright]}le parallel {P}^{prime }-{P}^{prime}left({t}^{ast}right){parallel}_{infty}^{left[{alpha}_i,{beta}_iright]}+parallel {m}^{prime }-{P}^{prime }{parallel}_{infty}^{left[{alpha}_i,{beta}_iright]}le frac{1}{2}{P}^{prime}left({t}^{ast}right)\ {}& parallel {M}^{prime }-{P}^{prime}left({t}^{ast}right){parallel}_{infty}^{left[{alpha}_i,{beta}_iright]}le parallel {P}^{prime }-{P}^{prime}left({t}^{ast}right){parallel}_{infty}^{left[{alpha}_i,{beta}_iright]}+parallel {M}^{prime }-{P}^{prime }{parallel}_{infty}^{left[{alpha}_i,{beta}_iright]}le frac{1}{2}{P}^{prime}left({t}^{ast}right)end{array}}$$


and hence

$$forall tin left[{alpha}_i,{beta}_iright]:{m}^{prime (t)}ge frac{1}{2}{P}^{prime left({t}^{ast}right)},{M}^{prime (t)}ge frac{1}{2}{P}^{prime left({t}^{ast}right)}$$


From Lemma 1, the vertical height δ = δmin + δmax of m and M is bounded by ({C}_P{h}_i^4). Thus, the length hi of the intervals satisfies

$${h}_{i+1}le frac{2delta }{P^{prime left({t}^{ast}right)}}le frac{2{C}_P}{P^{prime left({t}^{ast}right)}}{h}_i^4$$


for all but a finite number of values of i (Fig. 4).

Fig. 4
figure 4

Illustration of Theorem 2

For other clipping techniques [8, 9], multiple roots reduce the convergence rate. The convergence rate of cubic HybClip is now discussed in the case of double roots, as illustrated in Fig. 5.

Fig. 5
figure 5

Illustration of Theorem 3

Theorem 3. (Double root) If the polynomial P has a root tin [α, β], and provided that this root has multiplicity 2, the sequence of the lengths of the intervals generated by cubic HybClip containing that root has the convergence rate d = 2.

Proof Similar to the proof of the previous theorem, the sequence of intervals ([αi, βi])i = 0, 1, 2, … is analyzed with lengths hi = βi − αi generated by Algorithm 1, which contains the double root. It is assumed that the second derivative satisfies P > 0. Otherwise, polynomial −P can be considered instead of P.

Again, two cubic Bernstein polynomials m and M can be obtained as the lower and upper bounds of P in [αi, βi]. Because P is continuous, and based on Lemma 2, the inequalities

$$parallel {P}^{{primeprime} }-{P}^{{primeprime}}left({t}^{ast}right){parallel}_{infty}^{left[{alpha}_i,{beta}_iright]}le frac{1}{4}{P}^{{primeprime}}left({t}^{ast}right)kern1em mathrm{and}kern1em parallel {m}^{{primeprime} }-{P}^{{primeprime} }(t){parallel}_{infty}^{left[{alpha}_i,{beta}_iright]}le frac{1}{4}{P}^{{primeprime}}left({t}^{ast}right)$$


hold for all but a finite number of values of i. These two inequalities imply that

$$parallel {m}^{{primeprime} }-{P}^{{primeprime} left({t}^{ast}right){parallel}_{infty}^{left[{alpha}_i,{beta}_iright]}}le parallel {P}^{{primeprime} }-{P}^{{primeprime} left({t}^{ast}right){parallel}_{infty}^{left[{alpha}_i,{beta}_iright]}}+parallel {m}^{{primeprime} }-{P}^{{primeprime} {parallel}_{infty}^{left[{alpha}_i,{beta}_iright]}}le frac{1}{2}{P}^{{primeprime} left({t}^{ast}right)}$$


and thus ({m}^{{primeprime} }(t)ge frac{1}{2}{P}^{{primeprime}}left({t}^{ast}right),forall tin left[{alpha}_i,{beta}_iright]). Letting τ = t − t, and based on

$$oversetleftharpoonup mleft(tauright)=m(t)=b_3tau^3+b_2tau^2+b_1tau+b_0,b_i=frac1{i!}m^{(i)}left(t^astright)$$


(left|{b}_2right|=frac{1}{2}{m}^{{primeprime}}left({t}^{ast}right)ge frac{1}{4}{P}^{{primeprime}}left({t}^{ast}right)>0). From Lemmas 1 and 2,

$${displaystyle begin{array}{ll}left|{b}_0right|& =left|mleft({t}^{ast}right)right|=left|mleft({t}^{ast}right)-Pleft({t}^{ast}right)right|le {C}_{0P}{h}_i^4\ {}left|{b}_1right|& =left|{m}^{prime}left({t}^{ast}right)right|=left|{m}^{prime}left({t}^{ast}right)-{P}^{prime}left({t}^{ast}right)right|le {C}_{1P}{h}_i^3\ {}left|{b}_3right|& =left|frac{1}{6}{m}^{(3)}left({t}^{ast}right)right|le frac{1}{6}left|{P}^{(3)}left({t}^{ast}right)right|+frac{1}{6}left|{m}^{(3)}left({t}^{ast}right)-{P}^{(3)}left({t}^{ast}right)right|\ {}& le frac{1}{6}left|{P}^{(3)}left({t}^{ast}right)right|+frac{1}{6}{C}_{3P}{h}_i:= {D}_{3P}end{array}}$$


Letting t1, t2 be the roots of m, t [t1, t2], and τ2 = t2 − t > 0, τ1 = t1 − t < 0, the following is obtained:

$${displaystyle begin{array}{ll}left|{b}_2{tau}_1^2right|& le left|{b}_3{tau}_1^3right|+left|{b}_1{tau}_1right|+left|{b}_0right|\ {}& le {tau}_1^2cdot {D}_{3P}left|{tau}_1right|+{C}_{1P}{h}_i^4+{C}_{0P}{h}_i^4:= {tau}_1^2cdot {D}_{3P}left|{tau}_1right|+{D}_{2P}{h}_i^4end{array}}$$


Because τ1 ≤ hi and hi → 0, D3P|τ1| → 0,

$$left|{b}_2{tau}_1^2right|le frac{1}{2}left|{b}_2right|left|{tau}_1^2right|+{D}_{2P}{h}_i^4$$


for a sufficiently large i. Therefore, ({D}_{2P}{h}_i^4ge frac{1}{2}left|{b}_2right|left|{tau}_1^2right|ge frac{1}{8}{P}^{{primeprime}}left({t}^{ast}right)left|{tau}_1^2right|), and hence

$${tau}_1le {left(frac{8{D}_{2P}}{P^{{primeprime} left({t}^{ast}right)}}right)}^{frac{1}{2}}{h}_i^2$$


Similarly, the following bound for t2 is obtained:

$${tau}_2le {left(frac{8D{prime}_{2P}}{P^{{primeprime} left({t}^{ast}right)}}right)}^{frac{1}{2}}{h}_i^2$$


Because τ1 < 0, τ2 > 0,

$${h}_{i+1}=left|{t}_2-{t}_1right|={tau}_2-{tau}_1le left({left(frac{8{D}_{2P}}{P^{{primeprime} left({t}^{ast}right)}}right)}^{frac{1}{2}}-{left(frac{8D{prime}_{2P}}{P^{{primeprime} left({t}^{ast}right)}}right)}^{frac{1}{2}}right){h}_i^2$$


Hence, the sequence (hi)i = 0, 1, 2, … has a convergence rate of 2.

From Theorems 2 and 3, it can be seen that the new algorithm has a higher convergence rate compared with geometry interval clipping [11] and quadratic clipping [8] when computing all roots of a univariate polynomial equation. The following theorem provides the convergence rate for the curve/curve intersection problems.

Theorem 4. Suppose f(t), g(s) have a transversal intersection (f(t) × g(s) ≠ 0) at p = f(t) = g(s). Furthermore, supposing that [αi, βi]i = 0, 1, 2, …is the sequence of generated intervals that contain t, and [ξi, ηi]i = 0, 1, 2, …is the corresponding sequence of generated intervals that contain s, there then exist constants C1, C2, C3, C4 depending solely on and g, such that

$${h}_{i+1,mathbf{f}}le {C}_1{h}_{i,mathbf{f}}^4+{C}_2{h}_{i,mathbf{g}}^2kern1em mathrm{and}kern1em {h}_{i+1,mathbf{g}}le {C}_3{h}_{i,mathbf{g}}^4+{C}_4{h}_{i,mathbf{f}}^4$$


Proof From line 11 of Algorithm 1, it can be seen that the length of intervals [ξi, ηi] tends toward zero as i tends toward infinity, that is, the interval [ξi, ηi] tends toward s.

Let ({overline{L}}_{mathbf{g}}) be the line or plane that passes through the endpoints b0, bm of g in [ξi, ηi]. Denote n as the unit normal vector of ({overline{L}}_{mathbf{g}}). Then, the distance function from f(t) to ({overline{L}}_{mathbf{g}}) is defined as

$$d(t)=mathbf{n}cdot left(mathbf{f}(t)-{mathbf{b}}_0right)$$


Denote ({mathbf{T}}_{mathbf{f}}^{ast }) as the tangent line of f at t. Let (phi in left[0,frac{pi }{2}right]) be the angle between ({mathbf{T}}_{mathbf{f}}^{ast }) and ({overline{L}}_{mathbf{g}}), and (theta in left[0,frac{pi }{2}right]) be the angles between ({mathbf{T}}_{mathbf{f}}^{ast }) and b0bm. As hi, g = [ξi, ηi] tends toward 0, the line or plane ({overline{L}}_{mathbf{g}}) converges at b0bm, and angle φ converges at θ. Thus, for a sufficiently small hi, g, (phi >frac{theta }{2}>0), and thus (0<sin left(frac{theta }{2}right)<sin left(phi right)le 1).

The angle ρ between f(t) and n is either (rho =frac{pi }{2}+phi) or (rho =frac{pi }{2}-phi). Using this, the derivative of the distance function can be bound at the intersection as

$$left|{d}^{prime}left({t}^{ast}right)right|=left|mathbf{n}cdot {mathbf{f}}^{prime}left({t}^{ast}right)right|=parallel {mathbf{f}}^{prime}left({t}^{ast}right)parallel left|cos left(frac{pi }{2}pm phi right)right|=parallel {mathbf{f}}^{prime}left({t}^{ast}right)parallel sin left(phi right)>0$$


Because d(t) ≠ 0, and for convenience, w = d(t) > 0 is denoted (otherwise, the vector −n can be considered instead of n).

Because d(t) is continuous, the inequality

$$parallel {d}^{prime }-{d}^{prime left({t}^{ast}right){parallel}_{infty}^{left[{alpha}_i,{beta}_iright]}}<frac{w}{2}$$


holds for all but a finite number of values of i. Hence,

$$forall tin left[{alpha}_i,{beta}_iright],{d}^{prime (t)}>frac{w}{2}$$


From line 6 of Algorithm 1, the cubic polynomial bound [dm(t), dM(t)] of the distance function d(t) can be obtained. Based on Lemma 2,

$$parallel {d}^{prime }-d{prime}_m{parallel}_{infty}^{left[{alpha}_i,{beta}_iright]}le frac{w}{4}kern1em mathrm{and}kern1em parallel {d}^{prime (t)}-d{prime}_M(t){parallel}_{infty}^{left[{alpha}_i,{beta}_iright]}le frac{w}{4}$$


and by Eq. (61), the following is obtained:

$$d{prime}_m(t)ge frac{w}{4}kern1em mathrm{and}kern1em d{prime}_M(t)ge frac{w}{4}$$


From Fig. 6, the bound for hi + 1, f is obtained as

$${displaystyle begin{array}{ll}& {h}_{i+1,mathbf{f}}={beta}_{i+1}-{alpha}_{i+1}le {l}_1+{l}_2+{l}_3\ {}& {l}_1+{l}_3=frac{d_{mathrm{max}}-{d}_{mathrm{min}}}{w/4}end{array}}$$


Fig. 6
figure 6

Based on Lemma 1, the vertical heights δi of dm and dM are bounded as follows:

$${delta}_i=parallel {d}_M-{d}_m{parallel}_{infty}^{left[{alpha}_i,{beta}_iright]}le parallel {d}_M-d{parallel}_{infty}^{left[{alpha}_i,{beta}_iright]}+parallel d-{d}_m{parallel}_{infty}^{left[{alpha}_i,{beta}_iright]}le {C}_{mathbf{f}}{h}_i^4$$


Let t1 and t2 be the roots of dm and dM respectively. From Eq. (63),



From Eq. (64), the above inequality implies that



This thus implies the first inequality in Eq. (57) from ({d}_{mathrm{max}}-{d}_{mathrm{min}}<{h}_{i,mathbf{g}}^2{C}_{mathbf{g}}) (see the proof of Theorem 6 in ref. [7]). Similarly, in the next iteration step, the following is obtained:

$${h}_{i+1,mathbf{g}}le C{prime}_{mathbf{g}}{h}_{i,mathbf{g}}^4+C{prime}_{mathbf{f}}{h}_{i+1,mathbf{f}}^2$$


where Cf is solely dependent on f, and Cg is solely dependent on g. Based on the first inequality of Eq. (57), the following is obtained:

$${displaystyle begin{array}{ll}{h}_{i+1,mathbf{g}}& le C{prime}_{mathbf{g}}{h}_{i,mathbf{g}}^4+C{prime}_{mathbf{f}}{left({C}_{mathbf{f}}{h}_{i,mathbf{f}}^4+{C}_{mathbf{g}}{h}_{i,mathbf{g}}^2right)}^2\ {}& le C{prime}_{mathbf{g}}{h}_{i,mathbf{g}}^4+C{prime}_{mathbf{f}}left({C}_{mathbf{f}}^2{h}_{i,mathbf{f}}^8+{C}_{mathbf{g}}^2{h}_{i,mathbf{g}}^4+2{C}_{mathbf{f}}{C}_{mathbf{g}}{h}_{i,mathbf{f}}^4{h}_{i,mathbf{g}}^2right)\ {}& le left(C{prime}_{mathbf{g}}+C{prime}_{mathbf{f}}{C}_{mathbf{g}}^2right){h}_{i,mathbf{g}}^4+left(C{prime}_{mathbf{f}}{C}_{mathbf{f}}^2{h}_{i,mathbf{f}}^4+2C{prime}_{mathbf{f}}{C}_{mathbf{f}}{C}_{mathbf{g}}{h}_{i,mathbf{g}}^2right){h}_{i,mathbf{f}}^4end{array}}$$


which implies the second inequality.

Note that the property of w being nonzero is key to binding l1 and l3. Therefore, a transversal intersection is required in the proof. From Theorem 4, the two sequences {[αi, βi]}i and {[ξi, ηi]}i of the new intersection algorithm have second- and fourth-order convergence rates, respectively, and the 3D curve intersection problem yields the same results.

Experimental results

In this section, all six algorithms are compared based on three criteria: the amount of time per iteration step, the number of iterations, and the computing time required to achieve a certain accuracy. All algorithms were implemented in C++ on a PC with an 2.60-GHz Intel(R) Core(TM) i7-9750H CPU and 16.0 GB of RAM. In all experiments, both curves P(t) and Q(s) have a parameter domain [0, 1].

For convenience, denote Bézier clipping as BezClip [5]; quadratic clipping and cubic clipping based on a degree reduction as 2-DegClip [8] and 3-DegClip [10], respectively; geometry interval clipping as 2-HybClip [11]; and cubic HybClip based on hybrid curves in ref. [14] as 3-HybClip*. In addition, the proposed cubic HybClip algorithm is denoted as 3-HybClip.

To analyze the relationship between the computational effort and the desired accuracy, two examples representing polynomials with transversal and tangent intersections are discussed. The five algorithms are first applied to three pairs of Bézier curves with a transversal intersection. Table 1 reports the number of pairs of iterations and the computing time in microseconds of the desired accuracy for computing the transversal intersections between the three curve pairs with various degrees. Figure 7a shows the relationship between the computing time and desired accuracy, and indicates that 3-HybClip based on cubic hybrid curves is significantly improved in comparison with BezClip, 2HybClip, 2-DegClip, and 3-DegClip.

$$left{begin{array}{c}{mathbf{P}}_4(t)=left(left(t-1/2right)left(t-3right){left(t+1right)}^2,left(t-1/2right)left(t-2right){left(t+1right)}^2right)\ {}{mathbf{Q}}_4(s)=left(left(s-1/2right)left(s-2right){left(s+2right)}^2,left(s-1/2right){left(s-2right)}^2left(s+1right)right)end{array}right.$$


$$left{begin{array}{c}{mathbf{P}}_8(t)=left(left(t-1/2right){left(t-2right)}^4{left(t+1/2right)}^3,left(t-1/2right){left(t-2right)}^4{left(t+1right)}^3right)\ {}{mathbf{Q}}_4(s)=left(left(s-1/2right)left(s-2right){left(s+2right)}^2,left(s-1/2right){left(s-2right)}^2left(s+1right)right)end{array}right.$$


$$left{begin{array}{c}{mathbf{P}}_8(t)=left(left(t-1/2right){left(t-2right)}^4{left(t+1/2right)}^3,left(t-1/2right){left(t-2right)}^4{left(t+1right)}^3right)\ {}{mathbf{Q}}_8(s)=left(left(s-1/2right){left(s-1right)}^3{left(s+1right)}^4,left(s-1/2right){left(s-2right)}^4{left(s+1right)}^3right)end{array}right.$$


Table 1 Transversal intersections
Fig. 7
figure 7

Computing time t in milliseconds vs accuracy ε of curve pairs with degrees (4, 4), (8, 4), and (8, 8) from the top to down. a Transversal intersections; b Tangent intersections

The five algorithms are applied to three pairs of Bézier curves with tangent intersections. Table 2 and Fig. 7b report the number of pairs of iterations and the computing time in milliseconds of various desired accuracies ε for computing the tangent intersections between the three curve pairs with various degrees. Experimental results show that the quadratic and cubic clipping techniques are better than Bézier clipping; however, compared with quadratic clipping based on hybrid curves or a degree reduction, the cubic clipping techniques show no substantial improvements. This is due to the fact that all clipping algorithms require a large number of binary subdivisions for tangent intersections.

$$left{begin{array}{c}{mathbf{P}}_4(t)=left(2t-1,-4{t}^4+8{t}^3-4t+1.5right)\ {}{mathbf{Q}}_4(s)=left(2s-1,4{s}^4-8{s}^3+4s-1right)end{array}right.$$


$$left{begin{array}{c}{mathbf{P}}_8(t)=left(2t-1,-20{t}^8+80{t}^7-112{t}^6+56{t}^5-4t+1.7031right)\ {}{mathbf{Q}}_4(s)=left(2s-1,4{s}^4-8{s}^3+4s-1right)end{array}right.$$


$$left{begin{array}{c}{mathbf{P}}_8(t)=left(2t-1,-20{t}^8+80{t}^7-112{t}^6+56{t}^5-4t+1.7031right)\ {}{mathbf{Q}}_8(s)=left(2s-1,20{s}^8-80{s}^7+112{s}^6-56{s}^5+4s-1.2031right)end{array}right.$$


Table 2 Tangent intersections

To compare these six algorithms numerically, statistics are generated on 40,000 pairs of randomly generated polynomial curves of degree 4–10 for single and multiple intersections. Figure 8 shows computing time needed to achieve the given accuracy of the five algorithms. The relative computing iterations and computing time for these tests are listed in Table 3. As shown in Table 3, 3-HybClip requires 2% fewer iterations and 8% less time than 3-HybClip* [14]. In addition, 3-HybClip has 2% fewer computing iterations than 3-DegClip, and at least 10% fewer iterations than 2-HybClip and 2-DegClip. With respect to the computing time, 3-HybClip is at least 60% faster than 3-DegClip and 2-DegClip, and at least 30% faster than 2-HybClip.

Fig. 8
figure 8

Statistical comparisons: Computing time t in seconds vs accuracy ε. a Single intersections; b Multiple intersections

Table 3 Relative computing iterations N and computing time t

Rights and permissions

Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit


This article is autogenerated using RSS feeds and has not been created or edited by OA JF.

Click here for Source link (