# Approximate Implicitization of Parametric Curves Using Cubic Algebraic Splines

Authors: Xiaolei Zhang; Jinming Wu
Journal: Mathematical Problems in Engineering
 (2009)

---

## Abstract

This paper presents an algorithm to solve the approximate implicitization of planar parametric curves using cubic algebraic splines. It applies piecewise cubic algebraic curves to give a globalG2 continuity approximation to planar parametric curves. Approximation error on approximate implicitization of rational curves is given. Several examples are provided to prove that the proposed method is flexible and efficient.


---

## Body

## 1. Introduction

Parametric curves/surfaces and implicit curves/surfaces are two important topics in computer-aided geometry design and geometric modelling. With the parametric form, it is easy to generate points on a general curve/surface and plot it. On the other hand, it is convenient to determine whether a point is on, inside, or outside a given solid with the implicit treatments.For any rational parametric curve/surface, we can convert it into implicit form. However, for a general parametric curve/surface, we usually cannot compute its exact implicit form. Even though its exact implicit form can be computed, the curve/surface implicitization always involves relatively complicated computation and the degree of the implicit curves/surfaces is high. Another difficulty is that implicit curves/surfaces may have unexpected components and self-intersections which lead to computational instability and topological inconsistency in geometric modeling. All these unsatisfied properties limit the applications of the exact implicitization (especially surface implicitization) in practical fields.Due to these reasons, finding approximate implicitization of parametric curves/surfaces has some practical significance. In recent years, many researches have proposed several approaches to solve this problem [1–10]. The earlier work on approximate implicitization was done by Velho and Gomes [1], who presented an approximate implicitization scheme from parametric surfaces to implicit surfaces based on wavelet analysis. In 1999, Sederberg et al. [2] proposed an approach to solve approximate implicitization problem by using monoid curves and surfaces. The method used by Sederberg was made more available in Dokken’s work [3, 4]. In 2004, Chen and Deng [6] presented the concept of interval implicitization of rational curves and developed the corresponding effective algorithm. In 2006, Li et al. [7] considered the approximate implicitization of planar parametric curves by using the piecewise quadratic Bézier spline curves with G1 continuity. In 2007, Wang and wu [8] discussed the approximate implicitization of general parametric curves based on radial basis function networks and multiquadric (MQ) quasi-interpolation. Very recently, Wu et al. [9, 10] discussed the approximate implicitization of parametric surfaces with the introduction of normal constraint points based on multivariate interpolation by using compactly supported radial basis functions, and approximate implicitization of parametric curves by using quadratic algebraic splines.In this paper, an algorithm is proposed to solve the approximate implicitization of planar parametric curves using cubic Bernstein-Bézier implicit curves. Our piecewise cubic curves are used to give a globalG2 continuity approximation, because they keep the same endpoints, the corresponding tangent directions, and curvatures at the separated points with the approximated segments. Approximation error on rational curves is also given.


## 2. Cubic Bernstein-Bézier Implicit Curve

In this section, some concepts and results on Bernstein-Bézier implicit curve are presented. For more details, the readers may refer to [11–13] and references therein.ByT:=[p1p2v12] we denote a triangle with vertices p1=(x1,y1),p2=(x2,y2), and v12=(x12,y12), and by [p1p2] we denote the line passing through the points p1 and p2. If we denote area ([v1v2v3]) as the area of triangle [v1v2v3], then the barycentric coordinates (u,v,w) of any point p=(x,y) with respect to T are defined by
(2.1)u=area(p,v2,p12)area(v1,v2,p12),v=area(v1,p,p12)area(v1,v2,p12),w=area(v1,v2,p)area(v1,v2,p12).Thus, any pointp=(x,y) with respect to T can be described as
(2.2)p=up1+vp2+wv12,u+v+w=1.The Bernstein polynomials are shown as follows:(2.3)Bijk3(u,v,w)=3!i!j!k!uivjwk,i+j+k=3.When any of the following is true:i,j,k<0 and i,j,k>3, the Bernstein polynomial Bijk3(u,v,w) is set to zero.Therefore, the Bézier triangle patch of degree three in Bernstein form is(2.4)f(u,v,w)=∑i+j+k=3bijkBijk3(u,v,w),
where all bijk are called Bézier control points (see Figure 1).Figure 1
The control points of a Bézier triangle patch of degree three.Definition 2.1.
Letf(u,v,w) be defined as (2.4), the cubic Bernstein-Bézier implicit curve 𝒞 on the triangle T:=[p1p2v12] is defined to be the zero contour of f(u,v,w), that is,
(2.5)𝒞:={(u,v,w)∣f(u,v,w)=0}.Theorem 2.2 (see [12]).
The directional derivative of Bézier triangle patch at the pointp=(u,v,w) with respect to the direction α=(α1,α2,α3) is given by
(2.6)Dαf(u,v,w)=3∑i+j+k=2[α1bi+1jk+α2bij+1k+α3bijk+1]Bijk2(u,v,w).Lemma 2.3.
For the triangleT:=[p1p2v12] and f(u,v,w) defined as in (2.4), if b300=b201=0, then the curve 𝒞 passes through p1 and is tangent with the line [p1v12] at p1. Similarly, if b030=b021=0, then 𝒞 passes through p2 and is tangent with the line [p2v12] at p2.Proof.
Since the barycentric coordinate ofp1 and direction [p1v12] with respect to the triangle T:=[p1p2v12] is (1,0,0) and (1,0,-1), respectively. Then the curve 𝒞 passes through p1 and is tangent with the line [p1v12] at p1 if and only if f(1,0,0)=0 and D(1,0,-1)f(1,0,0)=0. Thus, we get b300=b201=0 with Theorem 2.2. The later of this lemma can be proved similarly.Lemma 2.4.
Letf(u,v,w) be defined as (2.4). Its curvature of 𝒞 at p1 is given by
(2.7)κ1=|b102b210|μ1,whereμ1=2|(x2-x1)(y12-y1)-(y2-y1)(x12-x1)|((x12-x1)2+(y12-y1)2)3/2.
Similarly, its curvature of 𝒞 at p2 is given by
(2.8)κ2=|b012b120|μ2,whereμ2=2|(x1-x2)(y12-y2)-(y1-y2)(x12-x2)|((x12-x2)2+(y12-y2)2)3/2.Proof.
It can be derived from the curvature formula [14] of implicit curves:
(2.9)κ=-(-fy,fx)(fxxfxyfyxfyy)(-fyfx)(fx2+fy2)3/2,
where fx=(∂f/∂u)(∂u/∂x)+(∂f/∂v)(∂v/∂x)+(∂f/∂w)(∂w/∂x) and the other expressions can be understood similarly.If the equation of cubic Bézier curvef(u,v,w) in the triangle T:=[p1p2v12] is expressed in the form of
(2.10)f(u,v,w)=b2103u2v+b1203uv2+b1116uvw-κ1μ1b2103uw2-κ2μ2b1203vw2-w3,
with the restrictions of b210>0 and b120>0, then from Lemmas 2.1 and 2.2, we can easily have the following.Proposition 2.5.
For the triangleT:=[p1p2v12] and f(u,v,w) is defined as (2.10), then the curve 𝒞:={(u,v,w)∣f(u,v,w)=0} has the following properties:      (i)
𝒞 passes through the points p1 and p2.,(ii)
𝒞 is tangent with line [p1v12] at p1, and tangent with line [p2v12] at p2, respectively,(iii)
the curvatures of𝒞 at the points p1 and p2 are κ1 and κ2, respectively.The following result is due to Xu et al. [13].Proposition 2.6.
For the triangleT:=[p1p2v12] and let f(u,v,w) be defined as in (2.10), then the curve 𝒞 is D1([p1p2v12],v12,p1p2)-regular, that is, the straight lines that passes through v12 and the point on the line [p1p2] intersecting the curve 𝒞 exactly once in the interior of the triangle T. Moreover, 𝒞 has an arc from p1 to p2, no inflection point or singular point in the interior of T, and convex inside the triangle.It is noted out that our constructed cubic algebraic curve (2.10) is coincided with the reduced form in [15, 16], where they use them to construct a family of G1 and G2 continuous algebraic splines.


## 3. Approximate Implicitization of Parametric Curves

Given a planar parametric curveC(t)=(x(t),y(t)),t∈[0,1], where x(t) and y(t) are arbitrary functions, such as trigonometric and exponential functions.


### 3.1. Curve Segments

In order to solve the approximate implicitization problem using cubic algebraic splines, a basic problem is how to divide the planar parametric curves into several segments. Some concepts and definitions are reviewed. For more details, the readers may refer to [7].A natural idea is to divide the parametric curve into several curve segments possessing relatively good shape, separated by the following three types of critical points.(i)
A pointC(t0) is called a cusp point of parametric curve C(t) if x′(t0)=y′(t0)=0.(ii)
A pointC(t0) is called an inflection point of C(t) if x′(t0)y′′(t0)-x′′(t0)y′(t0)=0 and x′(t0)≠0.(iii)
A pointC(t0) is called a vertical point of C(t) if x′(t0)=0 and y′(t0)≠0.A parametric curveC(t) is called normal if it has a finite number of critical points and at each critical point the tangent direction can be defined as follows.(1)
IfC(t0) is not a cusp point, then the tangent direction is (x′(t0),y′(t0)).(2)
IfC(t0) is a cusp point, we assume that s-=limt→t0-y′(t)/x′(t) and s+=limt→t0+y′(t)/x′(t). If s-(s+) is a finite number, we define T-=(1,s-)(T+=(1,s+)). If s-(s+) approaches to infinity, we define T-=(0,1)(T+=(0,1)), where T- and T+ are called the left and right tangent directions of point C(t0).Letp0 be a cusp point, and let T- and T+ be the left and right tangent directions. Then the lines passing through p0 and with directions T- and T+ are called the left tangent line and right tangent line of C(t) at the point p0, respectively.A curve segmentC(t)=(x(t),y(t)),t∈[t1,t2] is said to be triangle convex if the left tangent line and right tangent line meet at v12 and the line segment p1p2 and the curve segment C(t),t∈[t1,t2] form a convex region inside the triangle [p1p2v12].For any parametric curveC(t), its curvature formula at any regular point C(t) is given by
(3.1)κ(t)=|x′(t)y′′(t)-x′′(t)y′(t)|(x′(t)2+y′(t)2)3/2.The curvature at each critical point can be defined as follows.(1)
Ifp0=C(t0) is a vertical point, then its curvature is κ(t0).(2)
Ifp0=C(t0) is a cusp point, we assume κ-=limt→t0-0κ(t) and κ+=limt→t0+0κ(t), where κ- and κ+ are called the left and right curvatures of the curve C(t) at the point p0.(3)
Ifp0=C(t0) is an inflection point, then its curvature is zero.Throughout this paper, we directly adopt the dividing algorithm in [7] to divide the input normal parametric curve into several triangle convex segments, separated by the above three types of critical points.


### 3.2. Segments Approximation

Letti,i=0,1,…,n be the parametric values corresponding to the separated points and two endpoints. For each i,i=0,1,…,n-1, let vi,i+1=(xi,i+1,yi,i+1) be the intersection point of the right tangent line at pi=(x(ti),y(ti)) and the left tangent line at pi+1=(x(ti+1),y(ti+1)). Here, all the triangles [pipi+1vi,i+1],i=0,1,…,n-1, are called the control triangles of C(t).Next, we show how to approximate each curve segmentC(t),t∈[ti,ti+1] in its control triangle [pipi+1vi,i+1] by using a cubic Bernstein-Bézier implicit curve 𝒞i={(ui,vi,wi)∣f(ui,vi,wi)=0} (see Figure 2). Here, f(ui,vi,wi) is assumed to be
(3.2)f(ui,vi,wi)=b210(i)3ui2vi+b120(i)3uivi2+b111(i)6uiviwi-κ1μ1b210(i)3uiwi2-κ2μ2b120(i)3viwi2-wi3,
where (ui,vi,wi) are the barycentric coordinates with respect to the triangle [pipi+1vi,i+1].Figure 2
Curve segmentC(t),t∈[ti,ti+1] is approximated by using 𝒞iThe remaining three free parametersb210(i),b120(i), and b111(i) in (3.2) can be determined by the following optimization problem:
(3.3)minH(b210(i),b120(i),b111(i)),whereH(b210(i),b120(i),b111(i))=∫titi+1(f(ui(t),vi(t),wi(t)))2dt,
under the constraints b210(i)>0 and b120(i)>0.Here,(ui(t),vi(t),wi(t)) are the barycentric coordinates of the point p=(x(t),y(t)) with respect to the triangle [pipi+1vi,i+1], they are univariate functions in variable t. So, by Gi(t), we denote Gi(t)=f(ui(t),vi(t),wi(t)).The integral involves complicated computations and can be evaluated by numerical method such as Gaussian quadrature [17].Proposition 3.1 (see [17]).
Letxk,k=1,2,…,n be the zeros of the orthogonal polynomial Legendre Pn(x)=(1/znn!)(dn/dxn)(x2-1)n and let Ak=2/((1-xk2)[Pn′(xk)]2),k=1,2,…,n, be the corresponding weights related to Ln(x). Then the quadrature formula
(3.4)∫-11f(x)dx=∑k=1nAkf(xk)
of this type has algebraic accuracy 2n+1.Any other interval[ti,ti+1] of integration must be transformed into the standard interval [-1,1]. From now on, we let y=(1/2)[(ti+1-ti)x+(ti+ti+1)] and x∈[-1,1] is transformed into y∈[ti,ti+1]. Therefore, the numerical integration that we wish to minimize in (3.3) can be reduced:
(3.5)H(b210(i),b120(i),b111(i))=∫titi+1Gi(t)2dt=ti+1-ti2∑k=1NAkGi(yk)2,
where yk=(1/2)[(ti+1-ti)xk+(ti+ti+1)],k=1,2,…,n.


### 3.3. Approximation Error

Given the rational parametric curve segment,(3.6)C(t)=(x(t)w(t),y(t)w(t)),t∈[ti,ti+1],
where x(t),y(t),w(t) are polynomials.Suppose its approximated curve in the interior of its control triangle[pipi+1v12] is
(3.7)𝒞i={(u,v,w)∣si(u,v,w)=0}.
In this section, we will discuss the approximation error between C(t),t∈[ti,ti+1] and 𝒞i.Let(ui(t),vi(t),wi(t)) be the barycentric coordinates of the point p=(x(t)/w(t),y(t)/w(t)) with respect to the triangle [pipi+1vi,i+1]. The approximation error is defined by
(3.8)E(si)=maxti<t<ti+1|Ei(t)|,Ei(t)=si(ui(t),vi(t),wi(t)).Here|si(ui(t),vi(t),wi(t))| denotes the algebraic distance between the point p=C(t),t∈(ti,ti+1) and its approximated curve 𝒞i.Theorem 3.2.
With the above notations,(3.9)E(si)≤Mhi4,hi=ti+1-ti,
where M is a positive number.Proof.
Obviously, we have(3.10)Ei(t)=si(ui(t),vi(t),wi(t))=Gi(t)w(t)3,t∈[ti,ti+1].
Since𝒞i interpolates the two endpoints pi=C(ti) and pi+1=C(ti+1), and keeps tangent directions at them, then it follows easily that
(3.11)Ei(ti)=Ei(ti+1)=0,Ei′(ti)=Ei′(ti+1)=0.
This fact is equal to Gi(ti)=Gi(ti+1)=0 and Gi′(ti)=Gi′(ti+1)=0. It yields
(3.12)Gi(t)=(t-ti)2(t-ti+1)2ri(t).
If we let hi=ti+1-ti, then maxti<t<ti+1(t-ti)2(t-ti+1)2=hi4/4 from simple computation.
Thus, if we set
(3.13)maxti≤t≤ti+1ri(t)w(t)3=4M,
then E(si)=maxti<t<ti+1|Ei(t)|≤Mhi4. This completes the proof.Theorem 3.3.
With the above proposed method, one obtains a piecewiseG2 continuous cubic algebraic curve which keeps the convexity of the original normal curve.Proof.
TheG2 continuity of the piecewise cubic approximate splines is a direct consequence of the fact that the cubic algebraic curves have the same tangent directions and curvature with the original curve. Furthermore, the curve is divided into triangle convex segments and the cubic curve segments are convex with no inflection points, which also keep the convexity of the curve.


### 3.4. Main algorithm

The algorithm of approximate implicitization for planar parametric curves using a cubic algebraic spline is outlined in what follows.Algorithm 3.4.
Approximate implicitization using cubic algrbraic spline.Input:
A normal parametric curveC(t)=(x(t),y(t)),t∈[0,1], and a sufficiently small positive number ε.Output:
A cubic algebraic spline𝒞={(u,v,w)∣s(u,v,w)=0} satisfying each E(si)<ε.Step 1:
Divide the normal parametric curve into several triangle convex segments using the dividing algorithm [7]. Let ti,i=0,1,…,n be the parametric values corresponding to the critical points and two endpoints. For each i=0,1,…,n, compute the left and right directions Ti- and Ti+, left and right curvatures κi- and κi+ at C(ti).Step 2:
On each interval[ti,ti+1],i=0,1,…,n-1, perform the optimization problem (3.3) to compute the cubic curve segment 𝒞i={(ui,vi,wi)∣si(ui,vi,wi)=0}.Step 3:
IfE(si)>ε, then we subdivide the interval [ti,ti+1] and repeat Step 2 on each subinterval.


## 3.1. Curve Segments

In order to solve the approximate implicitization problem using cubic algebraic splines, a basic problem is how to divide the planar parametric curves into several segments. Some concepts and definitions are reviewed. For more details, the readers may refer to [7].A natural idea is to divide the parametric curve into several curve segments possessing relatively good shape, separated by the following three types of critical points.(i)
A pointC(t0) is called a cusp point of parametric curve C(t) if x′(t0)=y′(t0)=0.(ii)
A pointC(t0) is called an inflection point of C(t) if x′(t0)y′′(t0)-x′′(t0)y′(t0)=0 and x′(t0)≠0.(iii)
A pointC(t0) is called a vertical point of C(t) if x′(t0)=0 and y′(t0)≠0.A parametric curveC(t) is called normal if it has a finite number of critical points and at each critical point the tangent direction can be defined as follows.(1)
IfC(t0) is not a cusp point, then the tangent direction is (x′(t0),y′(t0)).(2)
IfC(t0) is a cusp point, we assume that s-=limt→t0-y′(t)/x′(t) and s+=limt→t0+y′(t)/x′(t). If s-(s+) is a finite number, we define T-=(1,s-)(T+=(1,s+)). If s-(s+) approaches to infinity, we define T-=(0,1)(T+=(0,1)), where T- and T+ are called the left and right tangent directions of point C(t0).Letp0 be a cusp point, and let T- and T+ be the left and right tangent directions. Then the lines passing through p0 and with directions T- and T+ are called the left tangent line and right tangent line of C(t) at the point p0, respectively.A curve segmentC(t)=(x(t),y(t)),t∈[t1,t2] is said to be triangle convex if the left tangent line and right tangent line meet at v12 and the line segment p1p2 and the curve segment C(t),t∈[t1,t2] form a convex region inside the triangle [p1p2v12].For any parametric curveC(t), its curvature formula at any regular point C(t) is given by
(3.1)κ(t)=|x′(t)y′′(t)-x′′(t)y′(t)|(x′(t)2+y′(t)2)3/2.The curvature at each critical point can be defined as follows.(1)
Ifp0=C(t0) is a vertical point, then its curvature is κ(t0).(2)
Ifp0=C(t0) is a cusp point, we assume κ-=limt→t0-0κ(t) and κ+=limt→t0+0κ(t), where κ- and κ+ are called the left and right curvatures of the curve C(t) at the point p0.(3)
Ifp0=C(t0) is an inflection point, then its curvature is zero.Throughout this paper, we directly adopt the dividing algorithm in [7] to divide the input normal parametric curve into several triangle convex segments, separated by the above three types of critical points.


## 3.2. Segments Approximation

Letti,i=0,1,…,n be the parametric values corresponding to the separated points and two endpoints. For each i,i=0,1,…,n-1, let vi,i+1=(xi,i+1,yi,i+1) be the intersection point of the right tangent line at pi=(x(ti),y(ti)) and the left tangent line at pi+1=(x(ti+1),y(ti+1)). Here, all the triangles [pipi+1vi,i+1],i=0,1,…,n-1, are called the control triangles of C(t).Next, we show how to approximate each curve segmentC(t),t∈[ti,ti+1] in its control triangle [pipi+1vi,i+1] by using a cubic Bernstein-Bézier implicit curve 𝒞i={(ui,vi,wi)∣f(ui,vi,wi)=0} (see Figure 2). Here, f(ui,vi,wi) is assumed to be
(3.2)f(ui,vi,wi)=b210(i)3ui2vi+b120(i)3uivi2+b111(i)6uiviwi-κ1μ1b210(i)3uiwi2-κ2μ2b120(i)3viwi2-wi3,
where (ui,vi,wi) are the barycentric coordinates with respect to the triangle [pipi+1vi,i+1].Figure 2
Curve segmentC(t),t∈[ti,ti+1] is approximated by using 𝒞iThe remaining three free parametersb210(i),b120(i), and b111(i) in (3.2) can be determined by the following optimization problem:
(3.3)minH(b210(i),b120(i),b111(i)),whereH(b210(i),b120(i),b111(i))=∫titi+1(f(ui(t),vi(t),wi(t)))2dt,
under the constraints b210(i)>0 and b120(i)>0.Here,(ui(t),vi(t),wi(t)) are the barycentric coordinates of the point p=(x(t),y(t)) with respect to the triangle [pipi+1vi,i+1], they are univariate functions in variable t. So, by Gi(t), we denote Gi(t)=f(ui(t),vi(t),wi(t)).The integral involves complicated computations and can be evaluated by numerical method such as Gaussian quadrature [17].Proposition 3.1 (see [17]).
Letxk,k=1,2,…,n be the zeros of the orthogonal polynomial Legendre Pn(x)=(1/znn!)(dn/dxn)(x2-1)n and let Ak=2/((1-xk2)[Pn′(xk)]2),k=1,2,…,n, be the corresponding weights related to Ln(x). Then the quadrature formula
(3.4)∫-11f(x)dx=∑k=1nAkf(xk)
of this type has algebraic accuracy 2n+1.Any other interval[ti,ti+1] of integration must be transformed into the standard interval [-1,1]. From now on, we let y=(1/2)[(ti+1-ti)x+(ti+ti+1)] and x∈[-1,1] is transformed into y∈[ti,ti+1]. Therefore, the numerical integration that we wish to minimize in (3.3) can be reduced:
(3.5)H(b210(i),b120(i),b111(i))=∫titi+1Gi(t)2dt=ti+1-ti2∑k=1NAkGi(yk)2,
where yk=(1/2)[(ti+1-ti)xk+(ti+ti+1)],k=1,2,…,n.


## 3.3. Approximation Error

Given the rational parametric curve segment,(3.6)C(t)=(x(t)w(t),y(t)w(t)),t∈[ti,ti+1],
where x(t),y(t),w(t) are polynomials.Suppose its approximated curve in the interior of its control triangle[pipi+1v12] is
(3.7)𝒞i={(u,v,w)∣si(u,v,w)=0}.
In this section, we will discuss the approximation error between C(t),t∈[ti,ti+1] and 𝒞i.Let(ui(t),vi(t),wi(t)) be the barycentric coordinates of the point p=(x(t)/w(t),y(t)/w(t)) with respect to the triangle [pipi+1vi,i+1]. The approximation error is defined by
(3.8)E(si)=maxti<t<ti+1|Ei(t)|,Ei(t)=si(ui(t),vi(t),wi(t)).Here|si(ui(t),vi(t),wi(t))| denotes the algebraic distance between the point p=C(t),t∈(ti,ti+1) and its approximated curve 𝒞i.Theorem 3.2.
With the above notations,(3.9)E(si)≤Mhi4,hi=ti+1-ti,
where M is a positive number.Proof.
Obviously, we have(3.10)Ei(t)=si(ui(t),vi(t),wi(t))=Gi(t)w(t)3,t∈[ti,ti+1].
Since𝒞i interpolates the two endpoints pi=C(ti) and pi+1=C(ti+1), and keeps tangent directions at them, then it follows easily that
(3.11)Ei(ti)=Ei(ti+1)=0,Ei′(ti)=Ei′(ti+1)=0.
This fact is equal to Gi(ti)=Gi(ti+1)=0 and Gi′(ti)=Gi′(ti+1)=0. It yields
(3.12)Gi(t)=(t-ti)2(t-ti+1)2ri(t).
If we let hi=ti+1-ti, then maxti<t<ti+1(t-ti)2(t-ti+1)2=hi4/4 from simple computation.
Thus, if we set
(3.13)maxti≤t≤ti+1ri(t)w(t)3=4M,
then E(si)=maxti<t<ti+1|Ei(t)|≤Mhi4. This completes the proof.Theorem 3.3.
With the above proposed method, one obtains a piecewiseG2 continuous cubic algebraic curve which keeps the convexity of the original normal curve.Proof.
TheG2 continuity of the piecewise cubic approximate splines is a direct consequence of the fact that the cubic algebraic curves have the same tangent directions and curvature with the original curve. Furthermore, the curve is divided into triangle convex segments and the cubic curve segments are convex with no inflection points, which also keep the convexity of the curve.


## 3.4. Main algorithm

The algorithm of approximate implicitization for planar parametric curves using a cubic algebraic spline is outlined in what follows.Algorithm 3.4.
Approximate implicitization using cubic algrbraic spline.Input:
A normal parametric curveC(t)=(x(t),y(t)),t∈[0,1], and a sufficiently small positive number ε.Output:
A cubic algebraic spline𝒞={(u,v,w)∣s(u,v,w)=0} satisfying each E(si)<ε.Step 1:
Divide the normal parametric curve into several triangle convex segments using the dividing algorithm [7]. Let ti,i=0,1,…,n be the parametric values corresponding to the critical points and two endpoints. For each i=0,1,…,n, compute the left and right directions Ti- and Ti+, left and right curvatures κi- and κi+ at C(ti).Step 2:
On each interval[ti,ti+1],i=0,1,…,n-1, perform the optimization problem (3.3) to compute the cubic curve segment 𝒞i={(ui,vi,wi)∣si(ui,vi,wi)=0}.Step 3:
IfE(si)>ε, then we subdivide the interval [ti,ti+1] and repeat Step 2 on each subinterval.


## 4. Numerical Examples

In this section, some numerical examples are provided to illustrate that the proposed approximate implicitization method is flexible and effective.Example 4.1.
Consider the following curves from [6, 7]:
(4.1)C1(t)=(5t3+2t2,t4-3t3+2t2),C2(t)=(-5t-100t2+250t3-240t4+87t5-1-30t2+80t3-75t4+25t5,-5t-60t2+150t3-120t4+35t5-1-30t2+80t3-75t4+25t5),C3(t)=(sin(2t)+ln(5t4+2)+3t2,3et2-1+cos(t5)+2t7).
The parameters for curves of C1(t),C2(t), and C3(t) take values in [-1,1],[0,1], and [-1,1]. Their approximate cubic algebraic splines are shown in Figures 3, 4, and 5 and their approximation errors are listed in Tables 1, 2, and 3.
In the following figures, we simultaneously give the original parametric curves, the cubic algebraic splines, and the separated points, denoted by black line, red line, and black dots, respectively. Bys1 and s2, we denote the two segments in the left picture of Figure 3. By s11 and s12, we denote the two segments of which s1 is subdivided in Figure 3(b). Other notations can be understood similarly.
We list the exact implicit form of the first two curves with Gröbner bases method asgi(x,y)=0,i=1,2. Whereas, curve C3(t) does not have an exact implicit form. 							(4.2)g1(x,y)=336x2-55x3+x4-672xy-683x2y+336y2-1325xy2-625y3,g2(x,y)=608755200000x-3333251200000x2+1480428000000x3-249967600000x4+14475896875x5-608755200000y+9279481600000xy-2693703200000x2y+373486700000x3y-18653234375x4y-6920238720000y2-1644719360000xy2+108348060000x2y2+6461128750x3y2+3839471936000y3+507225156000xy3-55873524750x2y3-1083739330400y4+6038594775xy4+87948048293y5.
With comparison to the expressions of exact implicitization, we also list the implicit forms of the two approximate segments forC1(t) in Figure 3(a) as follows:
(4.3)s1(x,y)=-1.001x+0.321x2-0.211x3+1.001y-2.676xy+0.284x2y-1.891y2+0.939xy2+0.409y3,s2(x,y)=0.464x-0.101x2+0.005x3-0.464y+0.252xy-0.111x2y-2.118y2-4.625xy2-12.972y3.Table 1
Approximation error of curveC1(t).
s1s2s11s12s21s22t(-1,0)(0,1)(-1,-0.5)(-0.5,0)(0,0.5)(0.5,1)Error0.0410.0230.0090.0160.0140.004Table 2
Approximation error of curveC2(t).
s1s2s3s11s12t(0,0.6)(0.6,0.8)(0.8,1)(0,0.3)(0.3,0.6)Error0.0470.0040.0390.0060.018Table 3
Approximation error of curveC3(t).
s1s2s3s4s21s22s31s32t(-1,-0.8)(-0.8,-0.26)(-0.26,0.7)(0.7,1)(-0.8,-0.6)(-0.6,-0.26)(-0.26,0.4)(0.4,0.7)Error0.0350.0430.0340.0730.0080.0120.0130.009C1(t) and its approximate cubic algebraic splines.
(a)(b)C2(t) and its approximate cubic algebraic splines.
(a)(b)C3(t) and its approximate cubic algebraic splines.
(a)(b)


## 5. Conclusion

We have described an algorithm to solve approximate implicitization of planar parametric curves using piecewise cubic algebraic splines. With the proposed algorithm, we obtain a globalG2 continuous cubic algebraic spline which keeps the direction, the curvature, and the convexity of the original normal parametric curve with simple computation. The proposed method is flexible and effective from the numerical examples.However, the proposed algorithm is hard to be generalized to solve approximate implicitization of parametric surfaces directly. Therefore, the problem on approximate implicitization of parametric surfaces by algebraic spline surfaces remains to be our future work.



---

*Source: 327457-2009-11-25.xml*