（基础数学专业论文）voronoi区域重心计算的研究.pdf

学位论文原创性声明 本人所提交的学位论文v o r o n o i 区域重心计算的研究，是在 导师的指导下，独立进行研究工作所取得的原创性成果。除文中已经 注明引用的内容外，本论文不包含任何其他个人或集体己经发表或撰 写过的研究成果。对本文的研究做出重要贡献的个人和集体，均己在 文中标明。 本声明的法律后果由本人承担。 论文作者( 签名) ：易词目 2 0 0 7 年3 月1 0 日 学位论文原创性确认书 学生曼墨垫所提交的学位论文c v o r o n o i 区域重心计算的研 究，是在本人的指导下，由其独立进行研究工作所取得的原创性成 果。除文中已经注明引用的内容外，该论文不包含任何其他个人或集 体已经发表或撰写过的研究成果。 指导教师( 签名) ：裂窘酉豢 一。了年s 其b 摘要 对公共设施进行选址是城市规划中经常遇到的问题。在选址过程中，我们希 望既要充分体现该设施的利用价值、最大范围地服务社会，又要减少或避免由于 各设施的重复覆盖所造成的资源浪费。v o r o n o i 图在区域分割方面有着非常重要 的应用。本文针对这一问题，对v o r o n o i 区域重心的计算方法进行了研究。因为 平面图形的重心通常被认为是该区域的平衡位置，若公共设施越接近平衡位置， 在分布上显然应该是越均匀的。此结论可为选址位置的调整提供适当的参考和理 论依据。随后，本文以石家庄市长安区附近的中学为例对本问题进行了说明和讨 论。 在文章的结尾处提出了有待解决的问题：考虑到一些实际因素( 如人口分布、 经济发展状况等) ，选址的最佳位置就不一定是区域的几何重心，而更应该是带 有实际意义属性值的重心。本文给出了解决该问题的一些设想。 最后，对涉及到的算法，在附录中给出了用v i s u mc + + 语言实现的主要源 程序。 关键词：v o r o n o i 图，离散，重心。空问均值 2 a b s t r a c t t oc h o o s et h el o c a t i o no fp u b l i cf a c i l i t i e si st h ec o m m o np r o b l e mi nc i t y p l a n n i n g t h ev a l u eo fp u b l i cf a c i l i t i e ss h o u l db ec o m p l e t e l yr e f l e c t e d o no n eh a n d , t h e ys h o u l db ef u l l yu s e dt om a k eac o n t r i b u t i o nt os o c i e t y ；o nt h eo t h e rh a n d ，t h e r e p e t i t i o no ff a c i l i t i e sc o n s t r u c t i o ns h o u l db er e d u c e do rc u td o w nt oa v o i dt h ew a s t e o fr e s o u r c e s v o r o n o id i a g r a mp l a y sv e x ) , i m p o r t a n tr o l ei na r e ad i v i s i o n t h et b e s i s a t t e r n p t st os t u d yt h ew a y st oc a l c u l a t et h ec e n t e ro fg r a v i t yo fv o r o n o ia r e a b e c a u s e t h ec e n t r eo fg r a v i t yo fp l a n ef i g u r ei su s u a l l yt a k e na st h eb a l a n c e dp o s i t i o no ft h e a r e a , t h en e a r e rp u b l i cf a c i l i t i e sa l ea r r a n g e dt ob a l a n c e dp o s i t i o n ，t h em o r eb a l a n c e d t h ed i v i s i o ni s t h ec o n c l u s i o nc a nb et a k e na sc e r t a i nr e f e r e n t i a la n dt h e o r e t i c a l f o u n d a t i o nf o rt h ea d j u s t m e n to ft h ec h o o s i n go ft h ef a c i l i t i e sl o c a t i o n t h et h e s i s m a k e se x p l a n a t i o na n da r g u m e n to nt h eb a s eo f t h ee x a m p l eo f t h em i d d l es c h o o ln e a r c h a n g a nd i s t r i c t ，s h i j i a z h u a n gc i t y a tt h ee n do ft h et h e s i s t h ei m p o r t a n tp r o b l e m sd e m a n d i n gp r o m p ts o l u t i o na r e p o s e d ：s o m ep r a c t i c a lf a c t o r sl i k et h ed i s t r i b u t i o no fp o p u l a t i o na n dt h ec o n d i t i o no f e c o n o m i cd e v e l o p m e n tp r o v et h a tt h eb e s tp o s i t i o nm a yn o tb et h eg e o m e t r i cc e n t r eo f g r a v i t y , r a t h e ri ts h o u l db et h ec e n t r eo fg r a v i t yw i t i ip r a c t i c a la t t r i b u t ev a l u e t h e t h e s i sa s s u m e ss o m es o l u t i o n st ot h ep r o b l e m f i n a l l y , t h ea p p e n d i xp r o v i d e st h em a i n s o u r c ep r o g r a mi nv i s u a lc + + k e yw o r d s ：v o r o n o id i a g r a m ，d i s c r e t e ，t h ec e n t r eo fg r a v i t y , t h et y p i c a lv a l u eo f 3 第一章绪论 v o r o n o i 图是一种重要的几何结构，它反映的是以某种距离作为度量，给定 点集对研究区域进行的一种分割结果。该结果能较好地显示出区域中各点之间的 邻近关系以及某点在区域内的影响范围等信息，具有重要的应用价值。如科学家 用之研究宇宙的结构；考古学家用它来识别新石器时代不同部落影响下的地区： 气象学家在仪器不足的情况下估算降雨( 雪) 量：城市建设部门用来进行公共设 施的选址定位；生物学家用来研究毛细血管供应肌肉组织的情况等等，以上这些 研究都可以用v o r o n o i 图的概念来解释。 1 1v o r o n o i 图的历史与发展 v o r o n o i 图有着非常古老的历史，早在1 7 世纪中叶d e s c a r t e s 就使用了类 似今天的加权v o r o n o i 图的结构对太阳系及其环境中的物质分布进行分析 1 。 v o r o n o i 图这一概念是数学家p e t e rg u s t a vl e j e u n ed i r i c h l e t 与g e o r g e s v o r o n o i 在1 9 0 8 年首次提出的。之后在他们的著作中d i r i c h l e t 讨论了二维和 三维的情况，而v o r o n o i 则论述了m 维的情况 2 3 】后来，俄国数字理论学家 b o r i sn i k o l a e v i t c hd e l o n e 把d i r i c h l e t 和v o r o n o i 的名字与这种结构联系起 来，并创造了d i r i c h l e t 域( d i r i c h l e td o m a i n ) 和v o r o n o i 域这两个最常遇 到的术语。广泛的应用价值不断吸引人们投入大量的精力去研究v o r o n o i 图，后 来它被广泛地应用到化学、物理学、几何学、生态学、社会经济等领域中。 随着对v o r o n o i 图研究的深入及它所渗入领域的不断增加，普通v o r o n o i 图已经远远不能满足实际的需要，人们逐渐开始研究v o r o n o i 图在各方面的扩 展：如将生成元由点扩展到一般几何图形；将2 维平面内的v o r o n o i 图扩展到m 维空间如曲面v o r o n o i 图 4 5 】；将欧氏度量扩展到厶或k 等其它度量 6 ：引入 了高阶v o r o n o i 图、加权v o r o n o i 图 7 8 】、障碍v o r o n o i 图、动态v o r o n o i 图 9 】， 1 0 】等等。各种类型的y o r o n o i 图的生成算法及应用也日渐成熟起来，而且越来 越受到人们的关注。 6 1 2 计算几何与v o r o n o i 图 近年来，v o r o n o i 图被纳入计算几何的范畴。计算几何是随着计算机发展起 来的一门学科，尤其是近年来计算机科学与技术取得了飞速发展，特别是计算机 在图形图像处理方面得到了广泛的应用，使人们对计算几何的研究f 1 益重视。计 算几何是研究如何高效处理通过视觉器官等途径获取的几何信息，从理论上探讨 计算的可行性与复杂性，开发高速处理几何信息的方法，并对方法的性能作出评 价。而且它在计算机辅助设计、地理信息处理、计算机图形学、模式识别、机器 人、最优化配爱、物理学等许多领域都有着重要的应用。v o r o n o i 图是计算几何 的一个重要分支，在计算几何理论和应用中发挥着很大作用。在计算几何中， v o r o n o i 图理论成功地解决了找最近点、求最大空圆，求n 个点的凸包以及求最 小树等问题。 1 3 论文的研究内容 v o r o n o i 图最重要的应用之一就是进行区域分割。利用v o r o n o i 图，根据需 要可以将平面划分为若干v o r o n o i 区域，在实际应用中，研究v o r o n o i 区域的一 些特征参数是很有必要的。本文给出了求v o r o n o i 区域重心的两种计算方法，讨 论了重心在公共设施选址问题中的应用。并以石家庄市长安区附近9 所中学为 例，对该问题进行了分析和说明。最后根据实际需要，提出了本问题的进一步扩 展。 1 4 论文的结构安排 本文第一章简要介绍了v o r o n o i 图的历史和发展情况、计算几何与v o r o n o i 图之间的关系，并介绍了本文所研究的内容；第二章给出了v o r o n o i 图的定义、 性质及应用；第三章介绍离散v o r o n o i 图，其中包括离散v o r o n o i 图的定义、生 成法及算法生成中的几个关键问题；第四章讨论v o r o n o i 图区域重心的计算方 法，其中包括重心的计算方法、v o r o n o i 区域重心计算的基本思想、算法、结果 分析及应用实例；第五章结束语：最后是本文所参考的文献：附录中给出了用 v i s u a lc + + 语言实现的主要源程序。 第二章v o r o n o i 图 先来看一个简单的例子。 儿童就近入学问题：在一个城市中，适龄儿童如 何选择距家最近的学校入学。当然最直接的方法是 算出居住地与各小学之间距离，取其最小者然而 对于一个城市的上万名儿童的就近入学问题，上述 方法显然不可取。事实上，我们可以根据学校的位 置，在平面上作出一个分割图( 如图1 ) ，点表示学 图1 校，被线分割成的各区域可看作每个小学的“势力范围”，该范围即为小学的招 生范围。这种图形就是v o r o n o i 图。 2 1v o r o n o i 图的定义 首先给出平面v o r o n o i 图较直观的定义。 定义2 1 给定平面上有限个( 大于1 个) 点的集合，按照欧氏距离将平面 上的所有点分配给指定点集中距它最近的点。最终将平面分成了若干区域，一旦 平面点集给定，则这种区域图便唯一确定了。我们称该图形为由这个点集生成的 平面v o r o n o i 图，形成v o r o n o i 图的区域的边界称为v o r o n o i 多边形。通常就称 其为v o r o n o i 图及v o r o n o i 多边形。 下面给出精确的数学定义： 由 定义2 2 给定平面上的点集s = 扫。，p ：，p 。 ， y a p ) = n 扫p ( p ，p ) d ( p ，p ，) j ( f = i ，2 ，疗) j ，i 所给出的对平面的分割，称为以p ( f = 1 , 2 ，刀) 为生成 元( 或母点) 的v o r o n o i 图，简称v 图( 如图2 ) 。记 为v o r ( s ) 。 图2 其中，d ( p ，a ) 为p 和p i 问的欧氏( e u c l i d ) 距离。该图中的顶点和边分别简 8 称为v 顶点和v 边。区域圪( 只) 称为p ，的v o r o n o i 区域，简称为v 区域。由定 义易知圪( 只) 是到p 的距离比到其它生成元的距离都小的点的集合。图1 中的 点表示生成元，线表示v o r o n o i 边。 由定义容易看出： ( 1 ) 圪( n ) 是到p ，距离比到其他生成元距离都小的点的集合。 ( 2 ) 匕( p ) 是n - 1 个半平面的交。定义中集合 p i d ( p ，p 。) d ( p ，p i ) ) 是个半 平面。 ( 3 ) 匕( 只) 是不多于珂- i 条边的凸多边形，称为p 的v o r o n o i 多边形或 v o r o n o i 区域。 ( 4 ) l s 卜n 时，v o r ( s ) 划分平面成h 个多边形域，每个多边形域屹( p ，) 包含 且只包含s 中的一个点。 ( 5 ) v o r ( s ) 的边是s 中某个点对的垂直平分线上的一条线段或者半直线，为 所在的两个多边形所共有。 ( 6 ) v o r ( s ) 中有的多边形域是无界的。 2 2v o r o n o i 图的基本性质【t l 】 性质i生成元a 的v o r o n o i 区域v ( p ) 无界的充分必要条件是 p 。b c h ( p ) ，其中。b c h ( p ) 表示生成元集合s 的凸壳边界。 性质2n 个点的点集p 的v o r o n o i 图至多有2 玎一5 个顶点和3 n 一6 条边。 性质3 每个v o r o n o i 点恰好是三条v o r o n o i 边的交点。 性质4 点集p 中的点p ，的每一个最近临近点确定v ( p ) 的一条边。 2 3v o r o n o i 图的应用 2 3 1 在计算几何理论中的应用 ( 1 ) 最近邻近问题 9 问题i ：给定点集s = p l ，p29 eo * ，p ) 及点q ，在s 中寻找距离q 最近 的点( 或者若q s ，则求出平面上所有距q 最近的点) 。 问题2 ：对于给定点集s 中的每个点只，寻找距只最近的点p i 。 解决方法：根据指定点集构造v o r o n o i 图，则问题转化为寻找q 落在哪个 v o r o n o i 区域的问题：q s 时，q 所在的v o r o n o i 多边形内的点都是距q 最近的 点。 ( 2 ) 最大化最小角的三角剖分 在分析复杂形状的结构性质时，通常用到有限元分析技术。首先，将研究的 领域划分成有限元，而后用离散方法求解模拟结构力学的微分方程。为了求解过 程的稳定性，需要提高划分的质量，即要使所有三角形最大化最小角，这就是与 v o r o n o i 图紧密相关的d e l a u n a y 三角剖分。 ( 3 ) 最大空圆问题 给定平面上一个点的点集s ，寻找一个不包含s 中点的最大圆，并且该圆的 圆心在点集的凸壳c h ( s ) 的内部。可以证明此时q 必与v o r o n o i 顶点重合，从而 可用v o r o n o i 图解得。 ( 4 ) 最小生成树 点集s 的最小生成树( m s t ) 是连接s 中所有点的最小长度的树。例如许多 局域网络用树的形式生成基节点，m s t 是最小化总线路长度的网络拓扑。已经证 明m s t 是d e l a u n a y 三角剖分的一个子集。 2 3 2 在最优化配置领域的应用 v o r o n o i 图还解决了使交通费用最小的设施配置问题；移动设施服务点的最 优配置一移动图书车问题；使利用者限制最小的优化配置一一校区的合理划分 问题；最短网络光缆线路问题：平均使用时间最少的点设置公交车站牌 设置问题：基站配置与信号测试点选址问题等等。 2 3 3 在几何形体重构中的应用 几何形体重构就是根据测量得到的几何形体边界或内部的离散采样数据，重 新构造出几何形体的形状。此类问题在地理、地质、机械、医学等领域都有着很 i o 强的实用背景。 2 3 4 在物理、化学和分子生物学中的应用 在几十年前，v o r o n o i 图就开始被用来分析物质的微观结构。在这些领域 v o r o n o i 图的生成元通常是原子、分子或离子，它们的位置通常通过计算和测量 得到。通过计算生成的v o r o n o i 图的体积、表面积等参数，可以得到物质微观形 态的分布情况。 2 3 5 其他应用 v o r o n o i 图在模式识别，特别是对文字的识别、在机器人领域、数据压缩、 图象处理、移动通讯中的频率分配、树皮、皮肤纹路的模拟、神经网络以及数学 规划、天体动力学、地质统计学、机械制造、误差评价等领域都有着诸多重要的 应用。 第三章离散v o r o n o i 图 p l ( 毛，y t ) 、办( j 2 ，y 2 ) 的距离定义为d ( a ，p 2 ) = ( j i - x 2 ) 2 + ( y l - y 2 ) 2 。 设p 1 ，p ：，p 。为屏幕上的n 个点，则p ，的离散v 区域定义为 扣雌羔篡o r ：n ，f 弦o r 。五 o 圪( p 。) = 爿 。 d t p ，p t ) = d t p ，p j l d 2 + 2 万+ 1 已画成封闭的圆 用新的变量保存p 中的所有信息： 用新的变量p o l d 保存的头结点：此语句只执行一次 删除此生成元： j + + ： p = p n e x t ： 指向下一个生成元 ) i + + ： 步五：横向及纵向两次扫描全屏幕，如果某一象素点与其后继象素点颜色不同， 便将其置为黑色： 步六：横向( 或纵向) 扫描全屏幕，将非黑色象素点置为白色； 结束。 步七：p = p o l d ； 当p 不为空时，执行下列操作： p x 一= p 工一p _ 一； p _ y - = p _ y - p _ 一： ( t ，j ，一) 为重心坐标，若用公式( 7 ) 此处应为： l i p 寸x = p _ x p n - i - p _ x ，p y = p 斗y p j n + p y 在屏幕上画出重心坐标： p = p n e x t ： 4 2 3 算法说明 计算机中数据的存储空间是有限的，根据公式( 6 ) 计算重心坐标需要累加 t x , 或只，如果结果太大可能会造成数据的溢出，于是可将公式( 6 ) 化为： 坤l z - i i = 业孚笪= 丢塾 甩疗：? = 三窆一x o ) 训 ，i 扭i = 丢私训+ 三窆i i i = 丢私刮1 嘶 = 丢妻c t 训+ 同理 2 1 歹= 2 l 2 警= 去喜( ”一y 0 ) + ( 7 ) 其中，( x 。，儿) 为生成元坐标。 这样，只需累加( 一) 和( m 一儿) ，其数据结果将大大减小，有效 地减少和避免了误差的产生。 4 2 4 结果分析 图1 0 是运行结果的一部分： 图1 0 图中，黑点表示生成元的位置，十字图形的交叉点表示重心的位置。可以 看出：有的v o r o n o i 区域的重心与生成元的偏差很大，而有的却非常接近。通过 观察发现：生成元与重心偏离较大的区域。通常它们的分布是不均匀的( 如图 l o 中左侧部分的生成元，其分布过于集中) 。 关于重心计算问题的一点说明： 求解过程中累加出的每个v o r o n o i 区域的点的个数珂，可以作为该v o r o n o i 区域的面积。对于一些实际问题如服务设施的选址，了解某设施所覆盖区域的范 围，既可以最大程度的服务社会，又可以有效地避免重复设置带来的浪费。而 v o r o n o i 区域是不规则的凸多边形，直接求此类图形的面积通常用积分法和公式 法。这两种方法分别需要求出被积函数和顶点坐标，对于不规则的图形这是很困 难的。用像素个数表示面积同样能得到想要的结果，而且易于实现。下表是生成 元为1 0 0 0 的v o r o n o i 图的部分v o r o n o i 区域面积的列表： 4 3v o r o n o i 区域重心的应用 在生活中我们往往会遇到这种情况：某学校或服务性单位为了进一步的发展 需要设立新校区或新的服务网点；或者为了迎合城市建设和发展的整体规划，需 要在位置上做出调整对于此类问题，如以学校位置的调整为例，我们可以先根 据初步的考察决定各学校的大概位置，然后以它们为生成元做出v o r o n o i 图。求 出重心坐标后，观察其与生成元的位置关系，如果相去甚远，则说明该生成元的 位罱有待调整。重心是使区域达到平衡的位置，使生成元适当地接近重心，在实 际中更具有合理性，而且经过这样调整后的生成元分布更加均匀 应用实例下图是石家庄市区图( 部分) ，下面以该地区的几所中学为例进行分 析。 以这些学校为生成元，做出v o r o n o i 图，如下： 图中，圆点代表学校的实际位置，黑线所围成的区域是各学校的势力范围 即v o r o n o i 区域，十字交叉点是各v o r o n o i 区域的重心位置。可以看出，第十二 2 4 中学位置最接近重心，依照本文的分析，它的位置最为合适。有些学校则与重心 偏离较大，如四十中和华通职业中学位置比较集中。若以重心位置作为参考，从 整体上看分布会更加均匀，更加合理。 4 4 问题的进一步扩展 在以上的讨论中，我们仅仅将v o r o n o i 区域看作是一个单纯的几何图形，以 区域中的点作为研究对象，然而在处理具体问题时，它往往具有一定的实际意义。 还拿上面的选址问题来说，学校位置的确定，不能只从单纯的地理位置来考虑， 还要综合一些社会因素如该地区的人口分布，并且研究的对象通常会变为某个平 面空间单元如一个居民区。这时，学校的最佳位置就不一定是区域的几何重心而 是区域的空间均值所在的位置。 空间均值是空间数理统计中的一个基本统计量，它的定义为 1 4 ： 设= 为第i 个平面空间单元的属性值，给定其重心的直角坐标( 工，y ) ，则由 一个平面空间单元组成的区域的空间均值被定义为一个坐标点( i ，歹) ，其中 孑= ( z ) “) 歹= ( z ，y 。) “e z ，) ( 8 ) 可见，空间均值指示的是空间现象属性数据“重心”的空间位置。若上式中 的属性值为平面空间单元的面积，则空间均值就是区域的几何重心。当某一空间 现象的空间均值显著区别于区域几何重心，便指示了这一空间现象的不均衡分 布，或称“重心偏离”。偏离的方向指示了空间现象的“高密度”部位，偏离的 距离则指示了均衡程度。 公式( 8 ) 可以看作是本章第一节重心计算法中的公式( 5 ) 的扩展：将原来 的质量历。扩展为空间单元的属性值z ，。在实际应用中，计算某区域重心时，我 们可以先将该区域划分为若干个小的空间单元( 如居民小区) ，每个小空间单元 的中心坐标记作( 一，门) ，用z ，表示不同意义的属性值( 如人口) ，利用公式( 8 ) 即可求出带有实际意义属性值的重心坐标。 以上说明仅为本人的一些构想，尚未实现，此问题有待进一步研究。 第五章结束语 致谢 在论文完成之际，由衷感谢对我进行过悉心指导和无私帮助的导师张有会教 授。从本文的结构安排到具体的撰写工作张老师倾注了很多心血。一年多来，张 老师渊博的学识、严谨的治学作风、诲人不倦的教学态度，都使我受益匪浅。特 别是在学习和工作过程中，张老师都给予了我极大的帮助和鼓励。这些必将成为 我今后学习工作中一笔巨大的精神财富。 借此机会，谨向尊敬的张老师致以崇高的敬意! 向所有给予我帮助和鼓励的老师和同学表示由衷的感谢! 最后，向本文所引用参考文献的作者表示深深的谢意! 参考文献 【l 】s p a t i a lt e s s e l l a t i o n ：c o n c e p ta n da p p l i c a t i o no fv o r o n o id i a g r a m s a t s u y u k i o k a b e ，b a r r yb o o t s ，k o k i c h is u g i h a r a , s u n gn o kc h i n 【2 gv o r o n o i ，n o u v e l l e sa p p l i c a t i o n sd e sp a r a m 6 t e r sc o n t i n u sal at h 6 0 d ed e sf o r m e s q u a d r a t i q u e s p r e m i e rm d m o i r e ：s u rq u e l q u e sp r o p f i e t e 6 sd e sf o r m e sq u a d r a t i q u e s p o s i t i v e sp a r f a i t s ，j r e i n ea n g e w ，m a t h ，1 3 3 ，9 7 - 1 7 8 ，1 9 0 7 【3 gv o r o n o i ，n o u v e l l e sa p p l i c a t i o n sd e sp a r a m d ：t e r sc o n t i n n sal at h 6 0 r i ed e sf o r m e s q u a d r a t i q u e s d e u x i 6 m em 6 m o i r e ：r e e h e r c h e ss u rl e ap a r a l l d l l 0 6 d r e sp r i m i t i v e s , j r e i n e a n g e w m a t h ，1 3 4 ，1 9 8 - 2 8 7 ，1 9 0 8 ；1 3 6 ，6 7 1 8 1 ，1 9 0 9 4 a u g e n b a u mjm ，p e s k i ncs o nt h ec o n s t r u c t i o no ft h ev o r o n o im e s ho na s p h e r e j j o u r n a lo f c o m p u t a t i o n a lp h y s i c s ，1 9 8 5 ，5 9 ：1 7 7 1 9 2 【5 a i c h h o l z c r o ，e ta 1 s k e wv o r o n o i d i a g r a m s j i n t e r n a t i o n a l j o u r n a lo f c o m p u t a t i o ng e o m e t r ya n da p p l i c a t i o n s ，1 9 9 9 9 ( 3 ) ：2 3 5 - 2 4 6 【6 p a p a d o p o i l oe ，l e ed t c r i t i c a la r e ac o m p u t a t i o n - an e wa p p r o a c h e b o l h t t p w e b e e c s n w u e d u d t l e e i s p d 9 8 p s 【7 a u r e n h a m m e rf p o w e rd i a g r a m s ：p r o p e a i e s ，a l g o r i t h m s ，a n da p p l i c a t i o n s j j o u m a lo nc o m p u t i n g ，1 9 8 7 ，1 6 ( 1 ) ：7 8 9 6 【8 w i l lh p r a c t i c a la n de f f i c i e n tc o m p u t a t i o no f a d d i t i v e l yw e i g h t e dv o r o n o ic e l l sf o r a p p l i c a t i o n si nm o l e c u l a rb i o l o g y 【e b o l 却r p i n f e t h z c h p u b p u b l i c a t i o n s t e e h - r e p o r t s 3 x x 3 0 0 p s p z 【9 a l b e r s g c ta 1 v o r o n o id i a g r a m so fm o v i n gp o i n t s j i n t e r n a t i o n a lj o u r n a lo f c o m p u t a t i o n a lg e o m e t r y & a p p l i c a t i o n s ，1 9 9 8 ，8 ( 3 ) ：3 6 5 3 8 0 【1 0 】d e f a b r i t i i sgc o v e n e ypvm u l t i s e a l em o d e l i n go f c o m p l e xf l u i d s e b o l h t t p ：w w w c h e m q m w a c u k c c s g d f s g i c r a y 9 9 p s g z 【1 l 】fp r e p a r a t a , mis h a m o s c o m p u t a t i o n a lg e o m y ：a ni n t r o d u c t i o n n e wy o r k ： s p r i n g e r - v e r l a g ，1 9 8 5 【1 2 】渡边贵史。村岛定行。2 次元摊散术i ：i _ 囡童0 ( 1 ) o 计算畴同t 描c 方法。日本鼋子情报通信输文菇，d - iv 0 1 j 7 9 一d in o 3p p 1 1 4 1 2 2 1 9 9 6 1 3 】朱德祥，运用重心概念处理几何问题。楚雄师范学院学报，1 9 8 7 年0 4 期。 【1 4 6 r i f f i t hd t h e o r yo fs p a t i a ls t a t i s t i c s i n ：g a i l e ，g l a n d w i l l m o t tcj ( e d s ) s p a t i a ls t a t i s t i c sa n dm o d e l s d o r d r e c h t ：d r e i d e l p u b li s h i n gc o m p a n y ，1 9 8 4 3 - 1 5 1 5 章毓晋，图像处理和分析基础。高等教育出版社，2 0 0 2 年7 月 1 6