張松枝， 王旭輝， 唐 爍

（合肥工業(yè)大學(xué)數(shù)學(xué)學(xué)院，安徽 合肥 230009）

三次Bézier曲線與圓弧有重合點(diǎn)時(shí)的Hausdorff距離

張松枝， 王旭輝*， 唐 爍

（合肥工業(yè)大學(xué)數(shù)學(xué)學(xué)院，安徽 合肥 230009）

Hausdorff距離常用來度量兩條曲線的匹配程度，因此，它可以用來度量三次Bézier曲線與圓弧之間的逼近程度。論文給出了三次Bézier曲線與圓弧在中點(diǎn)重合時(shí)，它們之間的Hausdorff距離表達(dá)式；以及三次Bézier曲線與圓弧在一般情況重合（除端點(diǎn)外）時(shí)的 Hausdorff距離表達(dá)式。通過這些表達(dá)式可以直接得出三次 Bézier曲線與圓弧之間的Hausdorff距離。

Hausdorff距離；圓??；Bézier曲線

Hausdorff距離是用來度量兩個(gè)集合之間的最大不匹配程度，因此，Hausdorff距離經(jīng)常用在CAD/CAM 系統(tǒng)或是作為逼近理論，是非常重要的理論知識(shí)[1-3]。圓弧曲線是幾何造型中一種相當(dāng)基本的曲線類型，而基于多項(xiàng)式的CAD/CAM 造型系統(tǒng)并不能精確表示圓弧。由于目前通用的CAD/CAM 系統(tǒng)都包含了Bézier曲線，所以為了在不同的CAD/CAM系統(tǒng)之間傳遞數(shù)據(jù)，更好地應(yīng)用圓弧，人們常使用Bézier曲線逼近圓弧。在過去的 30多年里，已經(jīng)做出了大量的工作，例如Dokken，Ahn與Kim，F(xiàn)loater均對(duì)Bézier曲線逼近圓弧進(jìn)行了研究[1-10]。但是，對(duì)于一般曲線之間的 Hausdorff距離較難求得，本文主要給出了當(dāng)三次 Bézier曲線與圓弧有重合點(diǎn)時(shí)其Hausdorff距離的顯式結(jié)果。從而可以清楚的知道三次 Bézier曲線對(duì)圓弧的逼近程度，即通過Hausdorff距離誤差來討論三次Bézier曲線與圓弧的逼近程度。

1 中點(diǎn)重合時(shí)Hausdorff距離

1.1 相關(guān)定義

首先給出兩條曲線段之間的 Hausdorff距離的定義。給定兩條曲線段

P (t)與 Q (s)之間的Hausdorff距離定義如下：

圓弧是幾何造型中一類常用的曲線類型。對(duì)于一般的圓，人們可以通過坐標(biāo)平移、旋轉(zhuǎn)以及均勻放縮把其變?yōu)橐粋€(gè)圓心在坐標(biāo)原點(diǎn)的單位圓。在本文中，只考慮圓心在原點(diǎn)的單位圓上的圓弧曲線，而且假設(shè)圓弧的一個(gè)端點(diǎn)坐標(biāo)為(1,0)。設(shè)圓心位于原點(diǎn)的單位圓弧的參數(shù)表示如下：

相對(duì)于二次Bézier曲線，三次Bézier曲線具有更高的逼近精度。本文主要討論如何用三次Bézier曲線來逼近圓弧.為了更好的逼近圓弧，可給出下面基本要求：

1） Bézier曲線與圓弧有相同的起點(diǎn)和終點(diǎn)

2） Bézier曲線與圓弧在起點(diǎn)與終點(diǎn)處有相同的切向量，即

由于圓弧自身具有軸對(duì)稱性的性質(zhì)，那么就希望所構(gòu)造的三次Bézier曲線也具有軸對(duì)稱性。因此可設(shè)三次Bézier曲線的控制頂點(diǎn)如下：

1.2 中點(diǎn)重合時(shí)Hausdorff距離顯式表達(dá)式

由文獻(xiàn)[11-13]可知，對(duì)于任意兩條不同的曲線 P (t)與 Q (s)之間的Hausdorff距離，其滿足下列關(guān)系：

其中， P '(t)，Q '(s)分別為 P (t)關(guān)于變?cè)猼求導(dǎo)與 Q (s)關(guān)于變?cè)猻求導(dǎo)的求導(dǎo)。

易知給定圓弧式（1）上的(c os(θ) ,sin(θ))⊥(c os'(θ) ,sin'(θ) )，所以只需求t使其滿足關(guān)系式(x ( t),y( t) )⊥ (x '( t),y'( t) )即可。因此，可將求圓弧與三次Bézier曲線之間的Hausdorff距離轉(zhuǎn)換為求解方程

設(shè)t1,… ,tn為方程式（4）的解，則圓弧與Bézier曲線的Hausdorff距離為

以下將研究給定圓弧式（1）與給定三次Bézier曲線式（3）有中點(diǎn)重合時(shí)，其Hausdorff距離的距離表達(dá)式。

定理 1 給定圓弧式（1）及其對(duì)應(yīng)的三次Bézier曲線式（3）。當(dāng)圓弧與三次Bézier曲線在中點(diǎn)重合時(shí)，圓弧與三次 Bézier曲線之間的Hausdorff距離為

證明 三次 Bézier曲線式（3）的中點(diǎn)為P*(1/2) =(x(1/2),y (1/2))，由于其在圓弧上，可得 x( 1/2)2+ y(1/2)2=1，

即

求解可得

將

代入式（4），可得方程式（4）的根為：

由于

所以

1.3 一般點(diǎn)重合時(shí)的Hausdorff距離顯式表達(dá)式

以上文章給出的是當(dāng)圓弧式（1）與三次Bézier曲線式（3）在中點(diǎn)重合時(shí)的Hausdorff距離，那么當(dāng)圓弧式（1）與三次Bézier曲線式（3）在一般點(diǎn)重合時(shí)的Hausdorff距離又該如何計(jì)算。通過分析研究可得下述定理：

定理 2 給定圓弧式（1）及其對(duì)應(yīng)的三次Bézier曲線式（3）。當(dāng)圓弧式（1）與三次Bézier式（3）曲線在參數(shù) t0,t0∈ (0,1)處重合時(shí)：

1） 當(dāng) t0∈ (δ,1 - δ)時(shí)，圓弧式（1）與其對(duì)應(yīng)的三次Bézier曲線之間的Hausdorff距離為

2） 當(dāng) t0∈ (0,δ)或 t0∈ (1 - δ,1)時(shí)，圓弧式（1）與其對(duì)應(yīng)三次Bézier曲線之間的Hausdorff距離為

證明 假設(shè)三次 Bézier曲線在 t =t0, t0∈ (0,1)處與圓弧在(c os(β) ,sin(β) )點(diǎn)重合，可得

即

求解方程（5）可得h的值為

其中

根據(jù)假設(shè)我們?nèi)為正值h2，將h2代入三次∑3x( t) Bézier曲線P*(t) =p B3(t )，求解方程

ii i=0 x'( t) + y( t) y'( t )=0，可得

易知t1,t2, t3, t4, t5與α大小無關(guān)，且

我們令

通過計(jì)算可得，當(dāng)t0∈ (δ,1-δ)時(shí)，

當(dāng)t0∈ (0,δ)或 t0∈ (1 - δ,1)時(shí)，。證畢。

由以上內(nèi)容可知，圓弧式（1）與其對(duì)應(yīng)三次 Bézier曲線式（3）在 t0重合時(shí)的 Hausdorff距離與它們?cè)?-t0重合時(shí)的Hausdorff距離相等，即滿足了圖像的對(duì)稱性。

2 應(yīng)用實(shí)例

下面給出上述定理的應(yīng)用實(shí)例

例 1 給定圓弧角度 α=π/3,π/2,2π/3π時(shí)，與其對(duì)應(yīng)三次Bézier曲線式（3）在 t=1/2處重合，則可得到下列誤差圖形

例2 給定圓弧式（1）角度α =π/6,π/3, π/2,2π/3,3π/4,π時(shí)，與其對(duì)應(yīng)三次Bézier曲線式（3）在參數(shù) t0=1/3處重合時(shí)，則可得到下列誤差圖形

圖2 Hausdorff距離都在 1/2t=處取得

例3 給定圓弧式（1）角度α =π/3,π/2, 2π/3時(shí)，與其對(duì)應(yīng)三次Bézier曲線式（3）在參數(shù) t0=3/5處重合時(shí)，則可得到下列誤差圖形

圖3 Hausdorff距離都在t =(3 - 33 - 8 t0+ 8t 02)/6=1/5處取得

3 總 結(jié)

本文給出了圓弧式（1）的三次Bézier曲線，式（3）與圓弧式（1）在中點(diǎn)重合時(shí)，它們之間Hausdorff距離顯式表達(dá)式以及在一般情況下，t=t0(0 ＜ t0＜ 1)有重合點(diǎn)時(shí)，它們之間的Hausdorff距離顯式表達(dá)式。我們通過這些Hausdorff距離顯示表達(dá)式直接得出圓弧式（1）與三次Bézier曲線式（3）之間的Hausdorff距離。

[1] Kim S H, Ahn Y J. An approximation of circular arcs by quatic Bézier curves [J]. Computer Aided Geometric Design, 2007, 39:490-493.

[2] Ahn Y J. Conic approximation of planar curves [J]. Computer Aided Geometric Design 2001, 33(12):867-872.

[3] Farouki R T, Neff C A. Analytic properties of plane offset curves [J]. Computer Aided Geometric Design 1990, (7):83-99.

[4] Ahn Y J, Kim H O. Approximation of circular arcs by Bézier curves [J]. Journal of Computational and Applied Mathematics, 1997, 81(1):145-163.

[5] Ahn Y J. Helix approximations with conic and quadratic Bézier curves [J]. Computer Aided Geometric Design, 2005, 22:551- 565.

[6] Blinn J. How many ways can you draw a circle [J]. IEEE Computer Graphics Application, 1987, 7(8):39-44.

[7] Dokken T, Dachlen M, Lyche T, et al. Good approximation of circle by curvature-continuous Bézier curves [J]. Computer Aided Geometric Design, 1990, (7):33-41.

[8] Goldapp M. Approximation of circular arcs by cubic polynomials [J]. Computer Aided Geometric Design 1991, (8):227-238.

[9] 范勁松, 安 軍, 徐宗?。萌蜰URBS表示圓弧與整圓的算法研究[J]．計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 1997, 9(5):391-395.

[10] Ahn Y J, Kim H O, Lee K Y. G1 arc spline approximation of quadratic Bézier curves [J]. Computer Aided Geometric Design, 1998, 30(8):615- 620.

[11] Ahn Y J, Kim Y S, Shin Y S. Approximation of circular arcs and offset curves by Bezier curves of high degree [J]. J. Comp. Appl. Math, 2004, 167:181-191.

[12] Floater M. High-order approximation of conic sections by quadratic splines [J]. Computer Aided Geometric Design, 1995, 12(6):617-637.

[13] Floater M. An o(h2n) Hermite approximation for conic sections [J]. Computer Aided Geometric Design, 1997, 14:135–151.

Hausdorff Distance between Cubic Bézier Curve and Circular Arc with a Coincidence Point

Zhang Songzhi, Wang Xuhui, Tang Shuo
( School of Mathematics, Hefei University of Technology, Hefei Anhui 230009, China )

Hausdorff distance is often used to measure the distance between two curves. It can be used to measure the distance between cubic Bézier curve and circular arc. In the paper, the closed form of the Hausdorff distance between the circular arc and the cubic Bézier curve is given when they have a coincidence point.

Hausdorff distance; Circular arc; Bézier curve

TP 391

A

2095-302X (2013)02-0072-04

2012-06-20；定稿日期：2012-08-29

張松枝（1987-），女，安徽阜陽人，碩士研究生。主要研究方向?yàn)閿?shù)值逼近。Email：253209502@qq.com

王旭輝（1980-），男，安徽巢湖人，博士研究生。主要研究方向?yàn)橛?jì)算機(jī)輔助幾何設(shè)計(jì)。Email：xhw@hfut.edu.cn