A Highly Accurate Approximation of Conic Sections by Quartic Bézier Curves
Zhi Liu^{1,}^{ *}, Na Wei^{1}, Jieqing Tan^{1}, Xiaoyan Liu^{2}
^{1}School of Mathematics, Hefei University of Technology, Hefei, China
^{2}Department of Mathematics, University of La Verne, La Verne, USA
Email address:
To cite this article:
Zhi Liu, Na Wei, Jieqing Tan, Xiaoyan Liu. A Highly Accurate Approximation of Conic Sections by Quartic Bézier Curves. Applied and Computational Mathematics. Vol. 5, No. 2, 2016, pp. 40-45. doi: 10.11648/j.acm.20160502.11
Abstract: A new approximation method for conic section by quartic Bézier curves is proposed. This method is based on the quartic Bézier approximation of circular arcs. We give the upper bound of Hausdorff distance between the conic section and the quartic Bézier curve, and also show that the approximation order is eight. And we prove that our approximation method has a smaller upper bound than previous quartic Bézier approximation methods. A quartic G^{2}-continuous spline approximation of conic sections is obtained by using the subdivision scheme at the shoulder point of the conic section.
Keywords: Conic Section, Quartic Bézier Curve, Hausdorff Distance, Approximation, G^{2}-Continuous, Subdivision Scheme
1. Introduction
It is well-known that besides the straight line, the conic sections are the simplest geometric entity. Conic sections are widely used in the fields of CAGD or CAD/CAM. Since the most of conic sections cannot be accurately represented by polynomials in explicit form, the parameter polynomials are used to approximate the conic sections. Bézier curves and surfaces [1-4] are the modeling tools widely used in CAD/CAM systems. Most of the previous work on conic sections approximation is based on quartic Bézier curves.
In 1997, Ahn and Kim [5] presented the approximation of circular arcs by quartic and quintic Bézier curves with approximation orders eight and ten. The approximation of circular arcs by quartic Bézier curves with approximation order eight were represented in [6-8]. Fang [9] presented a method for approximating conic sections using quintic polynomial curves. The constructed quintic polynomial curve has G^{3}-continuity with the conic section at the end points and G^{1}-continuity at the parametric mid-point. Floater [10] found that the approximation of the conic section by Bézier curve of any odd degree n has optimal approximation order 2n. Ahn [11] presented two methods of the quartic Bézier approximation of the conic section. Hu [12] gave a method for approximating conic sections by constrained Bézier curves of arbitrary degree. In 2014, Hu [13] provided a new approximation method of conic sections by quartic Bézier curves, which has a smaller error bound than previous quartic Bézier approximations.
The outline of this paper is as follows: In section 2, we present a new approximation method for conic sections by quartic Bézier curves, and give an upper bound on the Hausdorff distance between the conic section and the quartic Bézier curve. It is shown that the approximation order is eight. And we prove that our approximation method has a smaller error bound than previous quartic Bézier approximations. Finally, we illustrate our results by some numerical examples.
2. Quartic Bézier Approximation of Conic Sections
In this section, we give a new highly accurate approximation method of conic section by quartic Bézier curves. The conic section can be represented as [14]
,
where , , are the control points, is the weight associated with , is the quadratic Bernstein polynomial given by
It is also well known that is an ellipse when , a parabola when and a hyperbola when .
The quartic Bézier curve used to approximate the conic section is given by
where are the control points, are the quartic Bernstein polynomials defined by
Lemma 1. [15] Suppose that is any continuous curve which lies entirely inside the (closed) triangle such that and . Then
(1)
where is the Hausdorff distance [12] defined by
,
and f: is a function defined by
(2)
where are the barycentric coordinates with respect to . Any point can be expressed as . The curve satisfies the equation for .
The control points of the approximation curve can be expressed as
, , , , ,
where is the midpoint of and . In order to ensure that the approximation curves is contained in , and must satisfy and .
The point lies on the line segment joining two points and m, and has the barycentric coordinates with respect to
(3)
Obviously satisfy. Substituting Eq.(3) into Eq.(2), we can get
(4)
where
Suppose has zeros at . Then from it follows . But will tend to infinity as tends to 1, which does not meet our requirement. So we choose
(5)
Substituting Eq.(5) into Eq.(4), we can get
(6)
where
(7)
The approximation curve contacts with the conic at and 1 with multiplicity at least two respectively. If and are the roots of , we can get
(8)
By Eqs. (6), (7) and (8) we can get the leading coefficient of as follows
Since the approximation curve is chosen to contact with the conic at with multiplicity 2,1,2,1 and 2, we have
From , it follows
(9)
The value of is only determined by . If we want to determine an upper bound on the Hausdorff distance between the approximation curves and the conics, we need to obtain the range of to ensure that the approximation curve lies inside .
Theorem 1. If the weight satisfies , then the curve lies inside , where and .
Proof. According to the convex hull property of Bézier curves, the quartic Bézier curve lies inside when and .
Substituting into Eq. (5), we can get
.
Differentiating with respect to gives
Since the equation has no real roots, there are only two possibilities, either , or for all .
From , it follows for all . Therefore is a monotonically increasing function with respect to for . It is easy to get , . Let . Then
.
Similarly, differentiating with respect to gives
The equation has a unique zero . Since , we have for any .
In summary, we have , for .
Theorem 2. For , the Hausdorff distance between the conic section and the approximation curve is bounded as
(10)
where
Proof. The polynomial has the maximum at in the interval [0, 1]. By Eq.(1) and Eq.(9), we can get the value of . The proof of Theorem 2 is completed.
Floater [15] gave the result that and are , where is the maximum length of the parametric interval under subdivision. So according to the error bound, the approximation order of the approximation curve in Theorem 2 is eight. The error of Hu’s approximation method [13] is smaller than that of other previous quartic Bézier curve approximation methods. Next, we will prove our error bound is smaller than that of Hu’s method.
Hu showed in [13] that for
(11)
where
.
Theorem 3. For , the upper bound on the Hausdorff error (10) by our method is smaller than that by Hu’s method, i.e., .
Proof. Comparing in (10) with in (11) reveals that to show is equivalent to proving the following inequality
It is obvious that for according to Fig 1. Therefore
as asserted.
3. Numerical Examples
Example 1. Let the conic section be given with the control points , , and the weight , as shown in Fig 2(a). The quartic Bézier has the control points , , , , , as shown in Fig 2(b). The Hausdorff error bound is
by Theorem 2 in our method. Obviously, this error bound is smaller than that with Hu’ s method, which is
obtained by (11).
(a) the conic section
(b) the quartic Bézier approximation
Example 2. Let the conic section be given with the control points , , and the weight , as shown in Fig 3(a). The quartic Bézier has the control points , , , as shown in Fig. 3(b). The Hausdorff error bound is
by Theorem 2 in our method. Obviously, this error bound is smaller than that with Hu’ s method, which is
obtained by (11).
(a) the conic section ;
(b) the quartic Bézier approximation
In addition, if the bound on the Hausdorff error is larger than a user-specified error tolerance, we can consider the subdivision scheme for , consisting of alternately subdividing at the shoulder point and normalizing each subcurve, as stated in [15]. Using this subdivision scheme, the composite curve of the quartic Bézier approximation curve is globally G^{2} continuous. Suppose the conic section is subdivided at into two parts and . Then and have control points as
and the weight associated with the control points and .
In Example 2, If the error tolerance is , then we should split the conic at into two segments and , as shown in Fig 4(a), at the shoulder point by the subdivision scheme proposed in [16].
Using our method, the quartic Bézier approximations and have the Hausdorff error bounds
The composition curve of and yields the quartic G^{2}continuous spline approximation of the conic section , as shown in Fig. 4(b).
(a)The conic section and .
(b) The composite curve of and .
4. Conclusion
We give a new approximation method for conic section by quartic Bézier curves, and prove that our approximation method has a smaller error bound than previous quartic Bézier approximations. Although the approximations are not optimal, but the result is high accuracy. The next question considered is to find a better zeros sequence in order to have smaller error bound.
Acknowledgements
The authors would like to thank the referees for their valuable comments which greatly help improve the clarity and quality of the paper.
This work was supported in part by the National Natural Science Foundation of China (Grant No. 61472466 and 11471093), Key Project of Scientific Research, Education Department of Anhui Province of China under Grant No. KJ2014ZD30. The Fundamental Research Funds for the Central Universities under Grant No. JZ2015HGXJ0175.
References