用细分螺线插值容许G2Hermite数据

邓重阳

（杭州电子科技大学理学院，浙江 杭州 310018）

用细分螺线插值容许G2Hermite数据

邓重阳

（杭州电子科技大学理学院，浙江 杭州 310018）

为使几何细分方法生成的平面螺线段插值平面容许G2Hermite数据，基于平面双圆弧插值理论提出了该方法首末端点处新的细分规则。理论分析表明，修改后的细分方法所得极限曲线是曲率单调、不变号的螺线段，且插值首末端点处的点、切向、曲率。数值算例表明，修改后的细分方法收敛速度较快，极限曲线具有较好的形状。

平面螺线；容许G2Hermite数据；Hermite插值

螺线段是曲率单调上升或下降且不变号的曲线。因为不含曲率极值点和尖点，螺线段被认为是光顺曲线[1]。螺线设计在数学上的重要性体现于它在工程设计领域[2]及美学领域[3]中的重要应用上。

为了使两段螺线段在连接点处达到G2连续，设计螺线时要求螺线段能插值两端点及两端点处的切向、曲率，即要插值两点G2Hermite数据。螺线段只能插值特定的两点G2Hermite数据，称为容许G2Hermite数据。Meek和Walton用回旋螺线和一段圆弧[4]、一段指定的螺线和一段圆弧[5]插值容许 G2Hermite数据。Ait Haddou和Biard[6]用一对毕达哥拉斯曲线（Pythagorean Hodograph 曲线，简称PH曲线）的渐开线所形成的螺线来插值容许G2Hermite数据。Kuroda和Mukai[7]则用圆弧段的渐开线所形成的螺线来插值 G2Hermite数据。近年来，用（有理）Bezier曲线[8-9]和 PH 曲线[10-13]构造螺线来插值容许G2Hermite数据成为一个研究热点。但据我们所知，还没有文献涉及用细分方法所得螺线段插值容许G2Hermite数据的问题。

用插值型细分方法构造插值曲线曲面是计算机辅助几何设计中一种重要的造型方法。它具有算法简单、适用于多分辨率造型等诸多优点。但与参数曲线曲面插值方法、隐式曲线曲面插值方法等造型方法相比，插值型细分方法所得插值曲线曲面的质量难以保证，且形状难以控制。例如，以四点插值细分法[14]为代表的线性细分方法受人为痕迹、多余拐点等不良现象所困扰，而以基于几何特征为代表的非线性插值型细分方法[15-16]则连续阶不高，且其收敛性的证明较为复杂。最近，我们提出了生成螺线段的几何细分方法[17]，但该方法只能匹配G1Hermite数据。本文在该方法的基础上，基于双圆弧插值的理论修改其端点处的细分规则，使该方法生成的螺线能插值给定容许G2Hermite数据。

1 记号及背景知识

1.1 记号及初始假设

本文中，逆时针方向旋转的角为正角，顺时针方向旋转的角为负角。点 pk与 pk之间的距离ii+1记为或

因为本文所得插值曲线为曲率不变号的螺线，不失一般性，我们假定所有初始给定的角都是正角。

1.2 容许G2Hermite 数据

G2Hermite数据记为(A, T ,κ ;B,T ,κ )，也

AA BB可记为(A, TA,OA;B, TB,OB)，其中TA,TB为 A,B两点处的单位切向量， κA,κB分别为 A,B两点处的曲率， OA,OB分别为 A,B两点处曲率圆的圆心。若记 rA= 1/κA,rB= 1/κBA,B两点处曲率圆的半径，则不失一般性，我们可以假定 κA＞ κB≥ 0。

给定G2Hermite数据{A, TA,κA;B,TB,κB}，记αA,αB分别为从 TA到AB 和从AB到 TB的角。若κA＞ κB≥ 0，则{A ,TA,κA;B,TB,κB}为容许G2Hermite数据，即存在螺线插值它的充要条件[12]（如图1所示）。

1） αA＞ αB＞0

2） 圆 OA（以 OA为圆心，为半径）内含于圆 OB（以 OB为圆心，为半径）。

图1 容许G2Hermite数据

1.3 双圆弧

设A，B为相异两点，TA，TB为A，B 两点处的单位切向。记从TA到AB的角为 αA，从AB到TB的角为 αB。令O为插值 A,B两点且对弦AB的张角为 π− (αA+ αB)/2的圆弧段，如图2中的虚线所示圆弧段，则双圆弧的连接点在且只在圆弧段O上[18]。令J为双圆弧的连接点，T为J点处两圆的公共切向量，θ为从TA到T 的角，为了控制双圆弧的形状，一般取θ为控制双圆弧曲线的自由参数。

如果 αA,αB同号，则插值A，B两点，TA，TB两切向的双圆弧为C形，否则为S形。由于本文考虑螺线插值，所以只讨论C形双圆弧。对于自由参数θ，在大部分情况下，θ = α是一个比较合适的选择[19]，如图2所示。

图2 平面C形双圆弧

由以上两式易知， rL,rR都是关于θ的减函数[18]。所以我们有

引理 1 对于G1Hermite数据{A, TA;B,TB}，TA到AB的角记为α，AB到 TB的角记为β，且α ＞ β，插值{A, TA;B,TB}的双圆弧连接点所在圆弧段为O。 P1,P2为圆弧段O上的两点。若∠ AOP1＜∠ AOP2，则rR(P1) ＜rR(P2),rL(P1) ＜ rL(P2)。

引理 2 容许G2Hermite 数据

(A, TA,κA;B,TB,κB)中，若 κA＞ κB≥ 0，则在插值(A, TA;B,TB)的双圆弧中，存在以P为连接点的双圆 弧 使 得 rB＞ rL(P )＞ rR(P )＞rA。 这 里rA= 1/κA,rB=1/κB。

证 明 令圆 OA，圆 OB(圆心分别为 OA,OB)是 A,B两点处的曲率圆。

容许G2Hemite 数据(A, TA,κA;B,TB,κB)，由κA＞ κB≥0得0 ＜ αB＜ αA。

记O为插值A，B两点且对线段AB的夹角为 π− (αA+ αB)/2的圆弧（图3中虚线所示圆弧段）。记O在点A处的切向量为 TCA，则从 TCA到AB的角为(αA+ αB)/2。所以圆O与圆 OA有两个交点。显然A为圆C与圆 OA的一个交点。记圆O与 OA的另外一个交点为 A'，由(αA+αB)/2＜αA可知， A'在 A, TA,AB所确定区域内。同理，圆O与 OB除了交点B之外，还有一个交点 B'，且 B'在B, −TB,BA所确定的区域内，如图3所示。

图3 满足半径单调条件的双圆弧

由κA＞ κB≥ 0知 OB内含于 OA，所以 B' 介于 A',B之间。设P为圆弧段O上介于 A'B'的一点，以P为连接点且插值(A, TA;B,TB)的双圆弧的半径分别为 rR(P),rL(P )，由引理 1可得rB＞ rL(P ) ＞ rR(P )＞rA。证毕。

2 细分方法

给定初始的容许G2Hermite数据 {p00,T00,O00; p0,T0,O0}，在第 k个细分步骤中，我们保持老11 1顶点不变，但老顶点重新标记为 pk+1= pk，在每两个老顶点 pik,pik+1之间根据两点 pik,pik+1及其切向(在端点处还要用到曲率信息)插入一个新点，并对新点列的每一个点定义一个切向使细分进行下去。下面我们分别阐述加入新点的规则及确定切向的规则。

2.1 加入新点的规则

我们把加入新点的规则按相邻两点是否为端点分为3类：相邻两点都是端点；相邻两点都不是端点；相邻两点有一个是端点。下面分别介绍这3类确定新点的规则。

2.1.1 相邻两点都是端点

实际上，这种情况只在第1步细分的时候出现。此时，对于初始的容许 G2Hermite数据确定点 p1的方法是：1

设插值 p00,p10两点且对线段 p00p10张角为π− (α + β)/2的圆弧段为O，其圆心记为O（图4中虚线所示圆弧段），圆 O00(圆心为 O00，半径为与圆弧段O的交点为 A'; 圆 O0(圆心为1 O10，半径为与圆O的交点为 B'。∠ A'OB'的平分线与圆弧段O的交点即为 p11。

图4 相邻两点都是端点时的加入新点规则

2.1.2 相邻两点都不是端点

2.1.3 相邻两点有一个是端点

这种情形实际上还可以分成两种情况：pk,pk为 pk,pk或 pk,pk。这两种情况下的规ii+1012k−12k则是完全类似的。

1） pik,pik+1为 p0k,p1k

否则，令 p1k+1为插值的双圆弧的连接圆弧上满足以下条件的点

2.2 确定切向的规则

其中

3 光滑性分析

文献[17]已经证明了生成平面螺线的几何细分方法的收敛性和光滑性。由于本文算法仅对端点处的规则做了修改，所以只要对端点说明其收敛性和光滑性即可。

定 理 第1节所定义的细分方法细分容许G2Hermite数据所得极限曲线是插值的平面螺线。

证 明 与文献[17]相同的方法可以证明极限曲线的收敛性、G1、G2连续性以及极限曲线是螺线。在这里我们仅证明极限曲线插值容许G2Hermite数据的两个端曲率即可。

由第3.1节的加入新点规则可知，

所以极限曲线插值两个端曲率，证毕。

4 数值算例

我们已在很多实例中检验了本文算法，本节给出 4个有代表性的数值算例。所有实例中，对于每一个实例，我们画出了7个细分步骤后的离散点列，如图5中各图的蓝色实线及其离散曲率，如图5中各图的红色实线，每个离散点列有257个点。为了更好地了解极限曲线的性质，我们在图中画出每个点的离散曲率，如图5中红线，其长度为实际曲率的0.2倍，即此点及附近三点所确定的圆在此点处的曲率。令点 pk处的离散曲率为 κk，记ii我们在表1中给出了每个细分步骤后的 Dk及从表1可知，基本上处于0.5至0.8之间，所以相邻两点间的离散曲率之差以较快的速度趋向于0。

表1 每个细分步骤后 Dk, Dk /Dk−1的变化情况

图5 细分实例

5 结 论

本文介绍了一种用几何细分方法生成的螺线插值容许 G2Hemite数据的方法。其方法仅在第一步细分规则及两端点处的细分规则做了修改，其余点处的细分规则与生成螺线段细分方法完全相同。理论分析表明，本文所述细分方法所得点列收敛于一条螺线段，且插值两端点处的G2Hermite数据; 数值算例表明，其算法运算稳定，收敛速度较快。

[1] Farin G. Curves and surfaces for computer aided geometric design [M]. A Practical Guide, fourth ed., Academic Press, San Diego, 1997: 364.

[2] Gibreel G M, Easa S M, Hassan Y, et al. State of the art of highway geometric design consistency [J]. Journal of Transportation Engineering, 1999, 125(4): 305-313.

[3] Burchard H G, Ayers J A, Frey W H, et al. Approximation with aesthetic constraints [M]. Designing Fair Curves and Surfaces, SIAM, 1994: 3-28.

[4] Meek D S, Walton D J. Clothoid spline transition spirals [J]. Mathematics of Computation, 1992, 59: 117-133.

[5] Meek D S, Walton D J. Planar spirals that match G2hermite data [J]. Computer Aided Geometric Design, 1998, 15: 103-126.

[6] Ait H R, Biard L. G2approximation of an offset curve by Tschirnhausen quartics [C]//Dahlen M, Lyche T, Schumaker LL (Eds), Mathematical Methods for Curves and Surfaces. Vanderbilt University Press, 1995: 1-10.

[7] Kuroda M, Mukai S. Interpolating involute curves[C]// Cohen A, Rabut C, Schumaker LL. Curve and Surface Fitting, Saint Malo, 1999. Vanderbilt University Press, Nashville, 1999: 1-8.

[8] Frey W H, Field D A. Designing Bezier conics segments with monotone curvature [J]. Computer Aided Geometric Design, 2000, 17(6): 457-483.

[9] Dietz D A, Piper B. Interpolation with cubic spirals [J]. Computer Aided Geometric Design, 2004, 21(2): 165-180.

[10] Habib Z, Sakai M. On PH quintic spirals joining two circles with one circle inside the other [J]. Computer Aided Design, 2007, 39(2): 125-132.

[11] Habib Z, Sakai M. G2Pythagorean hodograph quintic transition between two circles with shape control [J]. Computer Aided Geometric Design, 2007, 24(5): 252-266.

[12] Walton D J, Meek D S. G2curve design with a pair of pythagorean hodograph quintic spiral segments [J]. Computer Aided Geometric Design, 2007, 24(5): 267-285.

[13] Goodman T N T, Meek D S, Walton D J. An involute spiral that matches G2Hermite data in the plane [J]. Computer Aided Geometric Design, 2009, 26(9): 733-756.

[14] Dyn N, Levin D, Gregory J A. A 4-point interpolatory subdivision scheme for curve design [J]. Computer Aided Geometric Design, 1987, 4(4): 257-268.

[15] Yang Xunnian. Normal based subdivision scheme for curve design [J]. Computer Aided Geometric Design, 2006, 23(3): 243-260.

[16] 邓重阳, 汪国昭. 曲线插值的一种保凸细分方法[J].计算机辅助设计与图形学学报, 2009, 21(8): 1042-1046.

[17] Deng Chongyang, Wang Guozhao. Generating planar spiral by geometric subdivision scheme [J]. Science of China, Series F, Information Science. 2009, 52(10): 1821-1829.

[18] 苏步青, 刘鼎元. 计算几何[M]. 上海科学技术出版社, 1985: 195-204.

Spiral-preserving geo2metric subdivision scheme for admissible G Hermite interpolation

Deng Chongyang
( College of Science, Hangzhou Dianzi University, Hangzhou Zhejiang 310018, China )

To interpolate admissible G2Hermite data, this paper proposes a modified geometric subdivision scheme with new subdivision rules near the end points of the curve. The method is based on the theory of planar biarc curve interpolation. Theoretical analysis shows that the limit curves of the modified subdivision scheme are planar spirals, which are curves of one-signed, monotone increasing or decreasing curvature. Numerical examples show that the modified subdivision scheme converge rapidly, and the limit curves are with nice shape.

planar spiral; admissible G2Hermite data; Hermite interpolation

TP 391

A

2095-302X (2012)02-0039-06

2011-09-29

国家自然科学基金数学天元青年基金资助项目（10926058，11026107）；国家自然科学基金青年基金资助项目（61003194）

邓重阳（1976-），男，湖南隆回人，副教授，博士，主要研究方向为计算机辅助几何设计与图形学。