三次Bézier曲線與圓弧有重合點時的Hausdorff距離

張松枝， 王旭輝， 唐 爍

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

三次Bézier曲線與圓弧有重合點時的Hausdorff距離

張松枝， 王旭輝*， 唐 爍

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

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

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

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

1 中點重合時Hausdorff距離

1.1 相關(guān)定義

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

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

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

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

1） Bézier曲線與圓弧有相同的起點和終點

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

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

1.2 中點重合時Hausdorff距離顯式表達式

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

其中， P '(t)，Q '(s)分別為 P (t)關(guān)于變元t求導與 Q (s)關(guān)于變元s求導的求導。

易知給定圓弧式（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）有中點重合時，其Hausdorff距離的距離表達式。

定理 1 給定圓弧式（1）及其對應的三次Bézier曲線式（3）。當圓弧與三次Bézier曲線在中點重合時，圓弧與三次 Bézier曲線之間的Hausdorff距離為

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

即

求解可得

將

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

由于

所以

1.3 一般點重合時的Hausdorff距離顯式表達式

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

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

1） 當 t0∈ (δ,1 - δ)時，圓弧式（1）與其對應的三次Bézier曲線之間的Hausdorff距離為

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

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

即

求解方程（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)，且

我們令

通過計算可得，當t0∈ (δ,1-δ)時，

當t0∈ (0,δ)或 t0∈ (1 - δ,1)時，。證畢。

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

2 應用實例

下面給出上述定理的應用實例

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

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

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

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

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

3 總 結(jié)

本文給出了圓弧式（1）的三次Bézier曲線，式（3）與圓弧式（1）在中點重合時，它們之間Hausdorff距離顯式表達式以及在一般情況下，t=t0(0 ＜ t0＜ 1)有重合點時，它們之間的Hausdorff距離顯式表達式。我們通過這些Hausdorff距離顯示表達式直接得出圓弧式（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]．計算機輔助設(shè)計與圖形學學報, 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-），女，安徽阜陽人，碩士研究生。主要研究方向為數(shù)值逼近。Email：253209502@qq.com

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