Voronoi图画法的改进与实现

1 引言计算几何在计算机辅助设计、计算机图形学及机器人等领域有着重要的应用。Voronoi图是计算几何的一个重要分支。在计算几何中,Voronoi图理论成功地解决了找最近点、求最大空圆、求n个点的凸包、求最小树等问题。另外,Voronoi图在物理、生态、城市规划等许多领域都有重要应用。所谓Voronoi图,简单地说,就是对平面上任意给定的n个点,根据这些点的位置,将平面分割成n部分,得到一种对平面的分割图     

近似线性平均复杂性的平面点集Voronoi图增量算法的设计与实现

1 引言 Voronoi图是计算几何学科的一个重要结构,在模式识别、计算机图形、计算机辅助设计等领域有广泛的应用。平面点集Voronoi图的常用构造算法有三类:分治法、平面扫描法和增量算法。由于增量算法不仅适用于静态点集,而且还适用于动态点集,因而受到重视。 Voronoi图增量算法中的关键工作是最近邻的选择和搜索。已有算法大都采用随机穷举法,因而效率较低。本文首先介绍了Voronoi图的翼边数据结构表示方法,在增量算法时间复杂性分析的基础上,提出了应用桶技术选择生成子并提     

利用类Delaunay三角剖分实现Voronoi图

1引言 计算几何在计算机辅助设计、计算机图形学(特别是三维图形生成技术)及机器人等领域是非常重要的.特别在近年来,受到了学术界的极大关注.Voronoi图是计算几何的一个重要分支.在气象、生态、空中交通管制、城市规划等领域都得到广泛应用.     

一种改进的Voronoi图增量构造算法

Voronoi图是计算几何中的一种重要几何结构,也是计算几何的重要研究内容之一,如今已经在图形学、地理信息系统、机械工程、机器人等领域得到广泛应用。增量法是最常用的构造Voronoi图的方法,但一般实现方法中点的定位时间比较长。扫描线算法可以视为一种特殊的增量法,时间复杂度为O(nlog n),但需要构造比较复杂的数据结构。为了更有效地构建Voronoi图,提出了一种改进的Voronoi图增量构造算法,该算法是通过对已有的生成Voronoi图的增量法进行分析,并结合它们的优点,采用扫描线的方式,通过右凸链的结构来定位新插入的点,实现了Voronoi图的逐步构造。和扫描线算法类似,其时间复杂度为O(nlog n),但算法更简洁,且便于理解和编程实现。     

一种平面点集Voronoi 图的细分算法

Voronoi 图是计算几何中的重要概念之一,在计算机图形学、计算几何、 计算机辅助几何设计、有限元网格划分、机器人轨迹控制、模式识别、气象学和地质学研究 中得到广泛应用。借助于四叉树和区间算术,提出了一种新的构造平面点集Voronoi 图的细 分算法, 并且和经典的增量算法、栅格扩张法进行了比较, 结果显示新细分算法更为有效。 最重要的是细分算法原理简单,很容易编程实现。     

粗糙域Voronoi图离散生成算法研究

Voronoi图是计算几何的一个重要分支,粗糙域Voronoi图是Voronoi图概念在复杂生成面上的扩展。提出了粗糙域Voronoi图的概念并利用A‘算法计算生成面上点与各母点的最短路径对其进行离散生成。为了降低粗糙域Voronoi图离散生成算法的复杂度,对粗糙域下A’算法估价函数权值与粗糙域粗糙特性的关系进行了深入探索。实验结果表明,A’算法估价函数权值与粗糙域粗糙特性正相关,并以此获得r算法估价函数的最优权,大大降低了粗糙域Voronoi图离散生成算法的复杂度。     

Voronoi区域面积的计算方法

1 引言在计算几何中,Voronoi图理论成功地解决了找最近点,求最大空圆,求n个点的凸包,求最小树等问题。此外,Voronoi图还在生态研究、城市规划以及优化配置等许多领域有重要应用。为简化书写,本文在下面的叙述中,将“Voronoi”简记为“V-”,如“V-图”指的是"Voronoi图”,“V-区域”指的是“Voronoi区域”,等等。     

一种基于点集自适应分组构建Voronoi 图的并行算法

论文提出一种基于点集自适应分组构建Voronoi 图的并行算法,其基本思 路是采用二叉树分裂的方法将平面点集进行自适应分组,将各分组内的点集独立生成 Voronoi 图,称为Voronoi 子图;提取所有分组内位于四边的边界点,对边界点集构建Voronoi 图,称为边界点Voronoi 图;最后,针对每个边界点,提取其位于Voronoi 子图和边界点Voronoi 图内所对应的两个多边形,进行Voronoi 多边形的合并,最终实现子网的合并。考虑到算法 耗时主要在分组点集的Voronoi 图生成,而各分组的算法实现不受其他分组影响,采用并行 计算技术加速分组点集的Voronoi 图生成。理论分析和测试表明,该算法是一个效率较高的 Voronoi 图生成并行算法。     

基于层次Voronoi图的点群相似度算法

通过对空间点群的自适应聚类方法构建层次Voronoi图,以此层次Voronoi图为切入点,计算点群的拓扑、密度和范围的相似度,结合有关标准差的数理统计方法,计算角度、距离的相似度。在各维度的相似度基础上,使用其几何平均值作为点群整体相似度的度量标准,优化点群相似度的计算方法,并通过实验证明算法的可行性     

增删点后的Voronoi 图生成算法

Voronoi 图可广泛应用于模式识别、计算机图形学、计算机辅助设计、地 理信息系统等领域。利用Voronoi 图及其对偶图Delaunay 三角网构建的不规则三角网TIN 能充分地反映地形地貌特征,对TIN 的统一管理和动态调用可较好地应用到数字高程模型 的建立中。通过联机增量和减量算法来来实现增删点后的Voronoi 图的生成,具有能够动态 修改点集、速度快、效率高等优势。     

Power图的性质及构造算法研究

点集的Power图是点集Voronoi图的推广,特别适用用来解决涉及球（圆)的几何问题,文中首先对Power图的基本性质进行了几何化的证明;之后,研究了权为负数时对Power图的影响,指出在Power图的理论中允许权为负数,从而Power图可以应用到具有负权性质的领域;最后,给出了平面点集的Power图的构造算法,该算法到用Power图与正则三角化互为对偶的原理,在点集的正则三角化的基础上构造Power图,同时给出了实例以说明算法的有效性。     

多连通域Voronoi图的算法及数据存储

通过对两种主要单连通域Voronoi图算法的剖析,改进初始化算法和数据结构,得到便于工程应用的单连通域Voronoi算法,并将波阵面传播的思想扩展应用到求多连通域的Voronoi图,形成新的多连通域问题算法,从而解决了工程中特别是分层制造技术中Voronoi图应用的一般性问题.     

基于改进Voronoi区域面积的Mark Meyer曲率估算方法

以微分几何曲率计算公式为理论基础,对常用的Mark Meyer离散点云曲率估算方法进行改进,提出基于Voronoi区域面积的改进Mark Meyer算法。针对Mark Meyer算法中Voronoi区域面积的计算进行改进,对于Voronoi区域中存在钝角的情形进行详细论述并且改进钝角三角形的计算公式,同时给出更为准确的面积计算方法。将该算法应用于球面、柱面、抛物面、马鞍面,计算结果表明该算法提高了离散点云曲率估算的精度和稳定性。     

平面上可相交凸多边形的Voronoi图

传统的多边形的Voronoi图存在不能相交的问题,以至于无法将其应用于计算机视觉、生态学等领域中的多边形相交情况.为了解决多边形相交情况下的最邻近空间划分问题,提出了可相交凸多边形的Voronoi图.首先定义可相交凸多边形的Voronoi图;然后阐述相交多边形特有的Voronoi边的区域化现象,证明了其发生的充要条件,进一步揭示了相交多边形与不相交多边形之间的关系;最后提出Voronoi图的生成算法,并用代码实现.实验结果表明,该算法能够有效地解决多边形相交的问题,突破了不能相交的限制,为计算机视觉、生态学等领域的实际应用提供了理论基础.     

点至平面代数曲线正交投影计算的混合算法EI北大核心CSCD

点至平面代数曲线的正交投影计算在计算机图形学、计算机辅助几何设计领域,特别是交互式设计等应用中有着非常重要而广泛的运用.基于牛顿梯度下降法、切线和曲率圆形成中点的中点脚点法,以及混合几何加速正交法的计算方法,提出一种混合算法用于计算点到平面代数曲线的正交投影问题.首先,采用牛顿梯度下降法使初始迭代点落在平面代数曲线上;其次,利用切线和曲率圆所形成的中点作为脚点,再结合牛顿梯度下降法,将落在平面代数曲线上的迭代点逐渐挪动至正交投影点很靠近位置;最后,使用混合几何加速正交法得到正交投影点.采用3个封闭平面代数曲线实例进行实验,通过收敛性计算验证,结果表明当测试点比较远或代数曲线次数比较高时,该算法是鲁棒和高效的.     

基于各向异性质心Voronoi图的网络异常检测技术

网络异常检测技术是入侵检测研究领域中的重要内容,但在检测率和误报率上存在相互制约的问题,导致实际应用中性能不高。基于各向异性质心Voronoi图,提出一种新的网络异常检测算法。在新算法中,首先对数据集用各向异性质心Voronoi图进行聚类,然后计算每个数据点的点密度,判断数据点是否正常。通过KDD Cup1999数据集的实验测试表明,新算法具有较高的检测率和较低的误报率。     

多边形中的点可见性快速算法

针对点的可见性计算这一计算几何中的基础问题,提出一种支持任意查询点的可见多边形快速计算的基于多边形Voronoi图的点可见性算法.以与Voronoi骨架路径对应的Voronoi通道概念,以及相应的局部最短路径概念为基础,按照深度优先策略对Voronoi图进行遍历,在计算Voronoi骨架路径的同时计算局部最短路径,并基于局部最短路径计算所遍历的多边形边的可见部分.该算法可以处理“带洞”多边形,而且只对多边形进行局部访问;对于“带洞”多边形,由于该算法的数据结构比较简单、剖分空间合理且易于实现,因此仅需O(n)空间和O(nlgn)预处理时间.最后给出了在三维室内虚拟场景设计与漫游系统中的应用实例,结果表明文中算法是实际可行,且运行时间与点的可见多边形的边数和多边形的边数均呈线性关系.     

基于MapReduce的加权Voronoi图并行算法设计及应用

针对大规模数据的加权Voronoi图实现的复杂性和计算精度低问题, 采用欧氏距离法, 设计和实现了一种基于MapReduce编程模型的并行栅格加权Voronoi图的生成算法, 并将其成功应用于石家庄桥东区超市的推荐服务。该算法计算精度高, 同时可适用于任意点、线、面及复合发生元的加权Voronoi图的计算。实验结果表明, 算法在处理大规模栅格数据时能明显提高栅格Voronoi图的生成速度, 并能为用户推荐综合因素优选的超市。     

关于k(1≤k＜n)阶Voronoi图生成算法的研究

k( 1≤k 相似文献   

基于Voronoi图的最近邻查询的研究

移动查询点的最近邻查询是移动计算和现实生活应用中一种很基本也很重要的查询类型.基于Voronoi图的最近邻查询在计算几何中已被研究了相当长一段时间.但在以往的研究中基于Voronoi图的最近邻查询究竟是基于何种具体的索引结构去实现对查询空间的搜索的,却很少被提及.本文把传统的R树和Voronoi图在解决最近邻查询问题中的优越性相结合,提出了一种新的索引结构:VR树.进而给出了基于VR树索引结构的1NN查询算法.