 Computer Science and Application 计算机科学与应用, 2011, 1, 39-43 http://dx.doi.org/10.12677/csa.2011.12009 Published Online September 2011 (http://www.hanspub.org/journal/csa/) Copyright © 2011 Hanspub CSA The Voronoi Diagram of Two-Dimensional Shape with Algebraic Curve Boundary Huahao Shou1, Ziwei Yuan1, Yongwei Miao2, Liping Wang3 1College of Science, Zhejiang University of Technology, Hangzhou 1 College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 3College of Busin ess and Administration, Zhejiang University of Technology, Hangzhou Email: shh@z j u t .edu.cn Received: Jul. 12th, 2011; revised: Jul. 25th, 2011; accepted: Aug. 9th, 2011. Abstract: Voronoi diagram is one of the most important computational geometry concepts. It is applied widely in computer graphics, computation geometry, finite element grid partition, robot trajectory control, pattern recognition, meteorology and geology. Current 2D Voronoi diagram algorithms are constructed under the conditio n of point set, po lygon or 2D shape with parametric curv e boundary. Due to the manipulation dif- ficulty of algebr a curve, Voronoi diagra m of 2D shap e with algebraic curve boundar y has not yet got solved . Based on interval analysis and subdivision algorithm, a new algorithm to construct the Voronoi diagram of 2D shape with algebraic curve boundary is given in this paper. Keywords: Voronoi Diagram; Algebraic Curve; In terval Analysis; Subdivision Algorithm 以代数曲线为边界的二维形体的 Voronoi图 寿华好 1，袁子薇 1，缪永伟 2，王丽萍 3 1浙江工业大学理学院，杭州 2浙江工业大学计算机科学与技术学院，杭州 3浙江工业大学经贸管理学院，杭州 Email: shh@zjut.edu.cn 收稿日期：2011 年7月12日；修回日期：2011 年7月25 日；录用日期：2011 年8月9日 摘 要：Voronoi 图是计算几何中的重要概念之一。在计算机图形学、计算几何、有限元网格划分、 机器人轨迹控制、模式识别、气象学和地质学研究中得到广泛应用，现有的二维 Voronoi 图算法都是 基于平面点集，多边形，或者以参数曲线为边界的二维形体的范围内解决的。由于代数曲线的难操作 性，以代数曲线为边界的二维形体的Voronoi 图算法一直未得到解决。本文在区间分析和细分算法的 基础上，提出了以代数曲线为边界的二维形体的 Voronoi 图新算法。 关键词：Voronoi 图；代数曲线；区间分析；细分算法 1. 引言 在不同的领域，Voronoi图有时也被称为 Thiessen 多边形、Dirichrit 网格、或Wigner-Seitz 域等。Voronoi 图的基本定义和算法可见于许多计算几何教科书。它 是关于空间邻近关系一种基础数据结构。Voronoi 图 有二维和三维、狭义和广义、一阶和高阶之分[1]。其 中最基本、应用最广泛和研究最深入的还是二维欧氏 空间平面点集 Voronoi 图，平面线集和面集Voronoi 图可以通过平面点集 Voronoi 图处理近似获得[2]。平 面点集 Voronoi 图常用构造算法主要包括矢量方法[3] 和栅格方法，基于矢量的方法有增量构造算法、分治 法、减量算法、平面扫描算法、间接法[1]；基于栅格 的方法有邻域栅格扩张法和栅格邻近归属法[4,5]。在 矢 量方法中，增量构造算法的时间复杂度为 2 On ，分  寿华好 等以代数曲线为边界的二维形体的图 40 | Voronoi 治法、减量算法和平面扫描算法的时间复杂度为 ，间接法的时间复杂度取决于其对偶 Delaunay 三角网获取的时间复杂度。现有矢量构造算 法存在计算繁琐、数据结构复杂、存在累计误差、存 储空间开销大等不足，而简单的栅格构造算法在精度 与空间复杂度以及时间复杂度之间存在严重矛盾，一 般只适用于精度和效率要求较低、小规模数据场合， 而且获得的只是近似的 Voronoi 图，所以应用范围受 到限制[5]。 log 2On n 在Voronoi 图中，被用来划分空间的各个基本图 形元素一般被称为站点。最基本的 Voronoi 图是以平 面点为站点的平面点集 P的Voronoi 图，它将平面划 分成凸多边形形状的 Voronoi 区域，P中的每个站点 ，对应一个这样区域，使得 内的任何点距离， 比距离其它站点近。Voronoi 图的定义可以推广到三 维或高维，也可以推广到二阶或高阶(以两个站点或多 个站点为一组划分邻近区域)，也可以推广到 或 i pi vi vi p L 1 L 等其他度量，也可以进一步推广到站点包括线段或多 边形的广义 Voronoi 图[1,2]，也可以有距离的推广、生 长元的推广等[6]。著名的应用包括机器人运动规划、 形状表示、转换和网格生成[2]。 前面提到的 Voronoi图主要针对的是点集模型、 多边形模型和参数曲线曲面模型[7]，而计算机辅助几 何设计中曲线的表示有参数形式和代数形式，曲线的 参数和代数表示在几何造型中各有优缺点，CAGD 中 同时采用曲线的两种表示法，两种形式间的转换成为 必须解决的课题。参数曲线的代数化总是可以实现的， 但大部分代数曲线都不能精确参数化。近年来随着计 算机计算能力的大幅提升，代数曲线曲面在几何造型 和图形学中的应用越来越多[8]，在对用代数曲线曲面 造型的几何体进行后续操作(比如中轴提取，形状匹 配，有限元网格划分)的时候经常需要先知道该几何体 的Voronoi 图，从而用代数曲线曲面构造的二维或者 三维形体的 Voronoi图计算也就显得十分必要。然而 到目前为止对于代数曲线曲面的 Voronoi 图计算还未 有人涉及。本文在区间分析[9]和细分算法的基础上提 出了一种以代数曲线为边界的二维形体的 Voronoi 图 新算法。基本思想是通过对代数曲线段进行采样得到 几组像素点集合，从而以代数曲线为边界的二维形体 的Voronoi 图计算转换为求解最短距离至少在两组以 上像素点集合处达到的像素全体，在求解过程中借助 于四叉树和区间算术进行加速。 2. 算法 假设 1,0fxy , 2,0fxy, , ,0 n fxy 是给定的 n条平面代数曲线，其中 1, f xy , 2, f xy , , , n f xy是二元多项式，这 n条平面代 数曲线构成了一个二维形体，所考虑的平面矩形区域 是 ,, x xyy ，像素点大小(即像素点的长度或宽度) 为 。计算该平面矩形区域内这n条代数曲线所围成 的二维形体的 Voronoi 图，相当于计算该平面矩形区 域内到这些代数曲线的最短距离至少有两处达到的像 素点全体。 算法的第一个关键步骤是首先利用四叉树和区间 算术将这 n条代数曲线离散化。即分别找出包含这 n 条代数曲线的像素点的 n个集合 1 11111 1 ,, k iii i i A ab cd ，， 1 ,, n k nnininin i Aabcd i 。先通过修正仿射算术[10] 计算 1, f xy 在 ,, x xyy 上的取值范围 11 , f f ， 然后判断 11 , f f 是否包含 0，如果 11 , f f 不包含 0， 说明 ,, x xyy 内不包含代数曲线 1,fxy 0 ，则 抛弃该区域，否则如果 11 , f f 包含 0，说明 ,, x xyy 有可能包含代数曲线 1,0fxy ，则将 该平面矩形区域在中点处一分为四，通过四叉树算法 的递归过程使得细分后的区域逐渐减小，一直细分到 区域的大小即区域的长和宽都小于等于一个像素的大 小 为止，如果还是排除不掉，则将该区域存入 1 A ， 同理可得 2 A ，，n A 。这里特别值得一提的是：如 果不用四叉树，那么需要对每个像素进行判断，比较 费时间。而使用四叉树，那么当 11 , f f 不包含 0时， 整个区域 ,, x xyy 可以抛掉，不需要对这个区域 内的像素作进一步的判断，而能不能把一个不包含代 数曲线的区域成功地抛掉又取决于所使用的区间算术 的精确度，这也是为什么我们选用相对比较精确的修 正仿射算术的原因。总之四叉树数据结构和相对比较 精确的区间算术可以起到计算加速的作用。 算法的第二个关键步骤是计算出平面矩形区域 ,, x xyy 内到这 n组像素集合 1 A ，2 A ， ，n A 最 Copyright © 2011 Hanspub CSA  寿华好 等以代数曲线为边界的二维形体的图41 | Voronoi 短距离至少在两处达到的像素点集合 M。这个问题仍 然是通过区间算术和四叉树解决的，先用普通区间算 术逐个计算平面矩形区域 ,, x xyy 和像素 111 1 ,, iii i ab cd之间的区间距离 2 2 111 1 ,,,,, iiiii i ggxxabyycd ， 再令 1 11 min i ik lg ， 1 11 min i ik h g，那么区间 11 ,lh就 是平面矩形区域 ,, x xyy 到代数曲线 1 A 的最短距 离区间，同理可得平面矩形区域 ,, x xyy 到代数 曲线 2 A 的最短距离区间 22 ,hl 平面矩形区域，， ,, x xyy 到代数曲线 n A 的最短距离区间 , nn lh。 再令 ，，则 1 min i in ll 1 min i in hh ,lh是平面矩形区 域 ,, x xyy 到n条代数曲线的最短距离区间。如 果 ,lh与 ,,1 ii lhi n 中只有一个区间相交，那么 ,, x xyy 不可能包含Voronoi 图的点，从而可以 抛弃 ,, x xyy ，但是如果 ,lh与 ,,1 ii lhi n 中 至少两个区间相交，则此时 ,, x xyy 可能包含 Voronoi 图的点，此时将 ,, x xyy 在中点处一分为 四，仍然是通过四叉树递归过程使得细分后的区域逐 渐减小，一直细分到区域的大小即区域的长和宽都小 于等于一个像素的大小 为止，如果还是排除不掉， 则将该区域存入 M。那么 M就是我们所要计算的以代 数曲线为边界的二维形体的Voronoi 图。具体算法如 下： (1) 输入代数曲线段的多项式函数表达式 1, f xy ， 2, f xy ， ， , n f xy，以及所在的平面 矩形区域 ,, x xy y 和像素的大小 。 (2) 利用修正仿射算术计算 1, f xy 在区域 ,, x xyy 上的取值范围 11 , f f ，如果 11 , f f 不包 含0，则将该区域剔除，否则将该区域在其中点处一 分为四个小区域，对每个小区域重复步骤(2)，一直细 分到区域的大小为小于等于一个像素的大小 为止， 如果还是排除不掉，则将其存入1 A ，最后得 1 11111 1 ,, k iii i i A ab cd 。 (3) 同理可得 ，， 。 2 22222 1 ,, k iii i i Aabcd , inini cd 1 , n k nnin i Aab (4) 利用普通区间算术计算 2 2 111 1 ,,,,, iiiii i ggxx abyycd ， 然后令 11 11 11 ,, min min i ik ik lhg g i ，同理可得 22 ,lh，， , nn lh，再令 ， 1 min i in ll 1 min i in hh ， 如果 ,lh与 ,,1 ii lhi n 中只有一个区间相交，那么 抛弃 ,, x xyy ，如果 ,l h与 ,,1 i hi n i l至少 两个区间相交，则将区域 中 ,, x xyy 在其中点处一 分为四个小区域，对每个小区域重复步骤(4)，一直细 分到区域的大小为小于等于一个像素的大小 为止， 如果还是排除不掉，则将其存入M。 (5) 作出代数曲线 1 A ，2 A , , n A 以及 Voronoi 图M，算法结束。 3. 实例 我们用 Mathematica5.0 编程实现上面的算法，并 在中央处理器为 Intel® Pentium® CPU T2330 @ 1.60 GHz 的微机系统里运行该程序进行了一些实例的计 算，下面给出四个例子。 例1：两条代数曲线分别取为直线1 fy 和抛物 线 2 211 42 fyx 1 4 在平面区域 0,1 0,1内的 部分。这两条代数曲线的方程相对来说比较简单。图 1是计算结果：总的 CPU 运行时间是 2044.63 秒，总 的细分次数是 3301 次，包括两条代数曲线构成的 2 维形体和它们的Voronoi 图在内的总的像素是3884 个。从图 1可以看出，Voronoi图与中轴(medial axis) 的不同之处。 0.2 0.40.6 0.81 0.2 0.4 0.6 0.8 1 CPU Time Used: 2044.63 Second; Number of Total Subdivisions: 3301; Number of Total Pixels: 3884. Figure 1. Voronoi diagram of two algebraic Curves (simple case) 图1. 两条代数曲线的 Voronoi 图(简单情形) Copyright © 2011 Hanspub CSA  寿华好 等以代数曲线为边界的二维形体的图 42 | Voronoi 例2：两条代数曲线分别为一条星形线 22 22 21fxy 33 11fxy和一个圆 ，在平面区域 1,1 1,1内的部分。星形线是 6次曲线，相对上 面例 1而言， 包 ， 稍微复杂一些。图 2是计算结果：总的 CPU 运行时间为 11,094.1 秒，总的细分次数是 6763 次，括两条代数曲线构成的 2维形体和它们的 Voronoi 图在内的总的像素是8288个。 例3：三条代数曲线分别为圆弧 22 11， 22 1 fx y 211fx y 2 2 331fx y，在平面区域 3 0.5,0.5 ,0 2 内的部分。图3是计算结果：总 的CPU 运行时间为 40,181.2 秒，总的细分次数是 , 1 1 1 平面区域 14 432 次，包括三条代数曲线构成的 2维形体和它们 的Voronoi 图在内的总的像素是 4494 个。 例4：四条代数曲线分别是圆弧 22 1 ， ， 111fx y 22 211fx y 22 311fxy 22 ， 411fxy ，在 1,1 1,1内 的部分。图 4是计算结运行时间果：总的 CPU 为 32,607.9 秒，总的细分次数是 21,097 次，包括四条代 数曲线构成的 2维形体和它们的 Voronoi 图在内的总 的像素是 5116个。 -0.75 -0.5 -0.2500.250.5 0.751 -0.75 -0.5 -0.25 0 0.25 0.5 0.75 1 CPU Time Used: 11,094.1 Second; Number of Total Subdivi- Figure 2.(complex case) sions: 6763; Number of Total Pi x els: 8288 Voronoi diagram of two algebraic Curves 图2. 两条代数曲线的 Voronoi图(复杂情形) -0.4 -0.2 00.2 0.4 -0.8 -0.6 -0.4 -0.2 0 CPU Time Used: 40,181.2 Second; Number of Total Subdivi- sions: 14,432; Number of Total Pixels: 4494 Figure 3. Voronoi diagram of three algebraic Curves 图3. 三条代数曲线的 Voronoi 图 -0.75 -0.5 -0.25 00.250.50.75 1 -0.75 -0.5 -0.25 0 0.25 0.5 0.75 1 CPU Time Used: 32,607.9 Second; Number of Total Subd 4. 结论 从上面四个实例可以看出，本文提出的算法可以 准确 ivi- sions: 21,097; Number of Total Pixels: 5116 Figure 4. Voronoi diagram of four algebraic Curves 图4. 四条代数曲线的 Voronoi 图 地计算出以平面代数曲线为边界的二维图形的 Voronoi 图。然而我们也 注意 到本 算法 得到 的是 一个 包含 Voronoi 图的像素点的集合，由于区间算术的保 守性，有些邻近 Voronoi 图但是不应包含于 Voronoi 图的像素点有可能会由于无法排除而被保留了下来， 这使得所得到 Voronoi 图的图像比实际要粗一些。此 外本算法本质上是一个基于像素级操作的算法，虽然 借助于于四叉树和区间算术进行了加速，但运算速度 Copyright © 2011 Hanspub CSA  寿华好 等 | 以代数曲线为边界的二维形体的 Voronoi 图 Copyright © 2011 Hanspub CSA 43 然科学基金(61070126, 61070135) 和浙 参考文献 (References) 设计[M]. 北京: 清华大学出 河海, 姜友华. 一种新的构建 . Voronoi图生成的栅格算法[J]. 武汉测绘科技 理论及应用研究[M]. 北京: 关于一般图形 Voronoi 图的 Tian. 2D piecewise algebraic splines for implicit ll, 仍然比较慢。如何对本算法得到的Voronoi 图进行细 化以及进一步提高运算速度是我们下一步要做的工 作。 5. 致谢 本文受国家自 江省自然科学基金(Y1100837)资助。 [1] 周培德. 计算几何—算法分析与 版社, 2000: 146-216. [2] F. P. 普雷帕拉塔, M. I. 沙莫斯. 计算几何导论[M]. 北京: 科 学出版社, 1990: 226-277. [3] 代晓巍, 李树军, 刘晓红. Voronoi图增点构造算法研究[J]. affi 测绘工程, 2007, 16(1): 19-22. [4] 王新生, 刘纪远, 庄大方, 毋 Voronoi 图的栅格方法[J]. 中国矿业大学学报, 2003, 32(3): 293-296. [5] 李成名, 陈军 大学学报, 1998, 23(3): 208-210. [6] 蔡强. 限定Voronoi 网格剖分的 北京邮电大学出版社, 2010: 5-6. [7] 张友会, 浅野哲夫, 小保方幸次. 近似构造法的研究[J]. 数值计算与计算机应用, 2002, 9(3): 217-225. [8] Q. D. Li, J. modeling. ACM Transactions on Graphics, 2009, 28(2): 1-13. [9] R. E. Moore. Interval analysis. Englewood Cliffs: Prentice-Ha 1966. [10] H. H. Shou, H. W. Lin, R. Martin, and G.-J. Wang. Modified ne arith metic is more accurate than centered interval arithmetic or affine arithmetic. Lecture Notes in Computer Science, 2003, 2768: 355-365. |