黄树培， 郑红婵， 闫飞一， 胡 韵

（西北工业大学应用数学系，陕西 西安 710129）

3点Binary插值细分法的性质以及应用

黄树培， 郑红婵， 闫飞一， 胡 韵

（西北工业大学应用数学系，陕西 西安 710129）

为了使细分格式具有好的性质：如光滑性、保凸性，提出了 3点 binary插值细分格式，然后分析了该细分格式的连续性、保凸性以及分形等性质与参数之间的关系，最后给出了该细分格式性质的一些应用。

插值细分格式; 连续性; 保凸性; 分形性质

细分是一种有效的曲线曲面造型技术。由于具有算法简单、易于实现等优点，因此广泛地应用于计算机图形学、计算机辅助几何设计、计算机动画、逆向工程以及医学图像处理等领域。

细分格式根据极限曲线曲面是否经过初始控制顶点，可分为插值细分格式和逼近细分格式。通常逼近细分格式生成的极限曲线更光滑，例如Siddiqi和Ahamd[1]提出了3点binary逼近细分格式，其极限曲线是 C2连续的；Siddiqi和Rehan[2]提出了一个改进的4点binary逼近细分格式，其极限曲线可以达到 C5连续。由于具有插值的性质，因此在实际应用中插值细分格式比逼近细分格式更有吸引力。Dyn等[3]提出了 4点binary插值细分格式，其极限曲线是C1连续的；Weissman[4]提出了6点binary插值细分格式，其极限曲线可以达到 C2连续。在这基础上，后来又出现了一些其他改进的binary插值细分格式如蔡志杰[5]，并分析了其光滑性等基本性质。

Bézier方法是一种几何造型方法，其优点是具有保形性，但其缺点之一是不具有插值性质，于是为了满足插值性质以及保形性质，丁友东和华宣积[6]提出了一类保凸的非线性插值细分格式。

在分形理论中，分形的生成时非常重要的。有很多方法可以用来生成分形，例如，Bahar[7]利用函数迭代系统的方法；Prusinkiewicz和Lindenmayer[8]利用L系统的方法；齐东旭和戈建涛[9]利用细分的方法等。

在实际应用中有时要求极限曲线具有好的性质：如光滑性、局部性和保凸性等。于是本文构造了一个3点binary插值细分格式，其极限曲线是 C1连续的。该细分格式具有好的性质：局部性，3点细分格式的支撑宽度是 4，Dyn等[3]

中的4点插值细分格式是也 C1连续的，但其支撑宽度是6。保凸性：当给定的初始数据为严格凸时，3点binary插值细分格式的细分参数满足一定条件时，极限曲线也是凸的。同时还可以发现细分曲线的形状与细分参数有一定的关系，可以控制曲线的膨胀与收缩，而且当细分参数在一定的条件下时，细分格式可以产生分形曲线。

1 预备知识

其中 J0为初始有序控制顶点的有限下标集，设

为第k次细分后的有序控制顶点集， Jk为相应的有限下标集。均匀稳定的binary细分法可表示为：

定义1 由 maskα 确定的多项式称为细分法S的生成多项式。

定理1[10]若细分法S一致收敛，则其，满足

细分法的收敛性与光滑性分析可归结为向量值函数的分量的收敛性与光滑性分析，而每个分量是由同一细分法产生的标量函数，因此只需要对初始控制实数集进行分析。

定理2[10]设细分法S的满足式(1)，则存在一个细分法 S1，满足

S1称为S的一阶均差细分法,S称为基细分法。 S的 n阶均差细分法 Sn的 mask为则 其 生 成 多 项 式 为

定理3[10]细分法S一致收敛当且仅当细分法对任何初始数据一致收敛于0。

定理4[11]设细分法S的maskα满足式(1)。若 存 在 正 整 数L及 实 数 c, 0 ≤ c＜1,使则细分法S一致收敛。

根据定理1和定理4，当细分法S及其i阶均差细分法 Si（i = 1,2,… ,n ）的 mask和分别满足

2 3点Binary插值细分格式

下面给出单参数的3点binary插值细分格式：

经过变形可化为：

其中，a为细分参数。

3 3点Binary插值细分格式的性质

下面研究本文提出的3点binary插值细分格式的性质：光滑性、保凸性以及分形性质。

3.1 连续性

下面利用生成多项式的方法来分析 3点binary插值细分格式的连续性。

因为满足式(1)，故有

因为 α（1）满足式(2)，故有

实验发现：当 a＜ 0时，极限曲线向外膨胀；当 a＞ 0时，极限曲线向内收缩；当 a= 0时，极限曲线为初始控制多边形。

3.2 保凸性

定理5 当初始数据是严格凸时，3点插值细分格式是保凸的。

利用二阶差分定义：

得到相应的二阶差分格式：

其中

证明由于而因此，当 a＜ 0时，＞ 0。

假设k时，命题成立。下面证明 k+1时，命题也成立。

因此，该细分格式对于严格的凸数据是保凸的。

3.3 分形性质

即

相应的特征方程是：

即

相应的特征方程是：

由于初始条件

可知式(6)的特解为

其中

由式(7)可知，式(4)可化为

其特解为

其中

由于

其中

c1,c2同式(7)。

定理6 当0＜ a＜时，3点binary插值细分法的极限曲线是分形曲线。

证明当0＜ a＜时，由式(8)和式(9)归纳推理可知，经k次细分后位于和之间的2k个小边向量可表示为

其中， αij≠ 0,1 = 1,2,3。通过计算可知，当

4 数值算例

下面给出关于3点binary插值细分格式性质的算例。

图中的蓝色实线表示初始控制多边形，‘*’表示初始数据点，其他颜色的实线表示细分格式生成的极限曲线。

图1 3点插值格式（绿线）与文献[1]中的3点逼近格式（红线）生成极限曲线的比较

图2 细分参数a影响细分极限曲线

图3中初始数据为 y-4= 16, y-3= 9, y-2=4, y-1= 1, y0= 0, y1= 1, y2= 4, y3= 9, y4= 16。品红色实线表示 3点插值格式满足保凸条件时细分八次的极限曲线；绿色实线表示细分格式不满足保凸条件时细分八次的极限曲线。

图3 细分格式满足保凸条件和不满足保凸条件

图4 细分格式在a=时生成的分形曲线

从图1中可以看出本文细分格式生成的插值细分曲线不具有几何上的对称性，但与逼近细分曲线比较起来具有保留初始数据的特点。从图2和图4可以看出细分曲线的形状要受细分参数a的影响。而从图3可以得出初始数据的性质和细分参数a共同决定细分格式的保凸性。

5 结 论

本文提出了一个3点binary插值细分格式，分析了该细分格式的连续性、保凸性以及分形等性质与细分参数之间的关系：

本文提出的细分格式为实际应用（如保凸性）以及快速生成分形曲线提供了一种方法。

[1] Siddiqi S S, Ahamd N. A new three point approximating C2subdivision scheme [J]. Applied Mathematics Letters, 2007, 20(6): 707-711.

[2] Siddiqi S S, Rehan K. Improved binary four point subdivision scheme and new corner cutting scheme [J]. Computers and Mathematics with Applications, 2010, 59(8): 2647-2657.

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

[4] Weissman A. A 6-point interpolatory subdivision scheme for curve design [D]. Tel-Aviv University, 1989.

[5] 蔡志杰. 变参数四点法的理论及其应用[J]. 数学年刊, 1995, 1(4) : 524-531.

[6] 丁友东, 华宣积. 一类非线性细分格式的保凸与分形性质[J]. 软件学报, 2000, 11(9) : 1263-1267.

[7] Bahar S. Chaotic orbits and bifurcation from a fixed point generated by an iterated function system [J]. Chaos, Solitions & Fractals, 1995, 5(6): 1001-1006.

[8] Prusinkiewicz P, Lindenmayer A. The algorithmic beauty of plants [M]. New York: Springer-Verlag, 1990.

[9] 齐东旭, 戈建涛. 点解序列与分形构造 Ⅰ[ J]. 北方工业大学学报, 1993, 5(3): 1-13.

[10] Dyn N. Subdivision schemes in computer-aided geometric design. Advances in Numerical Analysis(Light W, ed.)[M]. Clarendon Press, 1992: 36-104.

[11] Cavaretta A S, Dahmen W, Micchelli C A. Stationary subdivision [J]. Memoirs of the American Mathematical Society, 1991, (93): 1-186.

Properties and Applications of a 3-point Binary Interpolatory Subdivision Scheme

Huang Shupei, Zheng Hongchan, Yan Feiyi, Hu Yun
(Department of Applied Mathematics, Northwestern Polytechnical University, Xian Shaanxi 710129, China)

In order to make the subdivision scheme which has good properties, such as continuity, preserving-convexity, a 3-point binary interpolatory subdivision scheme is proposed. Then, the relationship between the properties including continuity, preserving-convexity and fractal property and the parameter are analyzed. Finally, some applications are given about the properties of the subdivision scheme.

interpolatory subdivision schemes; continuity; preserving-convexity; fractal property

TP 391

A

2095-302X (2014)01-0031-06

2013-05-07；定稿日期：2013-05-21

国家自然科学基金资助项目（61070233）

黄树培（1987-），男，河南许昌人，在读硕士研究生。主要研究方向为计算机辅助几何设计、计算机图形学。E-mail：hsp_0906@163.com