线/面Voronoi图的分解合并生成算法

Voronoi图生成算法受到计算效率或生长源类型的限制,难以支撑线/面生长源Voronoi图的构建。本文提出一种生成线/面生长源Voronoi图的分解合并算法,其主要过程是将线/面生长源离散为特征点表达,通过特征点交叉建立最近特征点对,并以最近特征点对Voronoi子区域的交来部分地代替线/面生长源的等距离边界,算法以前后迭代离散计算的Voronoi子区域面积差分作为条件,可有选择地将部分生长源置入迭代过程,使线/面生长源Voronoi子区域逐步调整并达到精度要求。     

线状障碍物的可视最短路径Voronoi图生成

对偶生成法和直接修正法是构造可视最短路径Voronoi图的两种基本途径。本文提出了分段剖分、整体剖分和统一剖分的修正思路;放宽了以往修正法中障碍物端点必为生长点的限制,并提出了能有效处理公共边的分簇算法和最适搜索算法,实现了在有限制的线状障碍物下对普通Voronoi图的有效修正,以生成可视最短路径Voronoi图。     

圆形剖分再生长的扩展Voronoi图构建方法

针对传统Vonoroi图生成过程中存在的局限性,根据各种Voronoi图生成算法的原理和特点,该文融合Delaunay算法和模拟生长算法的思想,提出了一种基于圆形剖分再生长的扩展Voronoi图生成方法.根据任务要求自定义生长函数,实现初始圆的扩展生长,达到成熟条件时停止生长;计算相邻圆之间的交点并作交线,通过一定处理后得到对应生成元的Voronoi图边界,遍历所有生长圆即可得到全域Voronoi图.通过仿真验证了该方法的可行性,易于拓展到加权Voronoi图的构建,为Voronoi图的构建提供了一种技术手段,且该方法更简洁直观.     

改进的加权Voronoi图ArcGIS矢量生成算法

加权Voronoi图是根据生成元权重划分空间的方法,广泛应用于地学领域。针对传统加权Voronoi图ArcGIS矢量生成算法不能处理重叠点、复杂多边形及更新操作等问题,该文提出了一种改进算法,结合C#和ArcEngine,利用增量法思想,通过重叠点处理、区域分割合并、加权区域重分类、加权区域重划分等方法实现,可嵌入ArcGIS应用软件使用或独立运行,具有良好的可用性,精度高,便于数据库存储管理,扩展了加权Voronoi图在地学领域的应用。     

利用质心Voronoi图对地形自适应简化的算法

地形简化算法利用少量有效的地形信息表达整体地形,能很好地解决海量地形数据与计算机硬件之间的矛盾,同时满足多尺度地形应用需求。针对现有地形简化算法难以兼顾局部地形起伏与地形整体特征的问题,提出一种基于质心Voronoi图的地形自适应简化算法。首先,利用质心Voronoi图的特点,以地形起伏度作为密度函数生成质心Voronoi图;然后,利用分布在地形起伏较大区域的质心Voronoi图种子点及大多分布在地形特征线上的Voronoi区域顶点重构地形;最后,通过原始地形与重构地形的特征线验证地形简化的效果,并与三维道格拉斯-普克（3D DouglasPeucker,3D DP）算法进行精度对比。实验结果表明,从简化地形中提取的山脊线、山谷线、等高线等地形特征线与原始地形的重叠度均较高,算法能较好地保持地形整体特征;且在相同的简化级别下,算法的简化误差小于3D DP算法,具有较高的地形简化精度。     

基于道路网络分析的Voronoi面域图构建算法

提出一种基于网络分析的Voronoi面域图和加权Voronoi面域图构建算法。鉴于道路网络在城市中心地、公共设施引力传导与功能覆盖上的重要作用,采用网络最短路径距离分析和最短路径时间分析构建的Voronoi面域图可以模拟出中心功能的辐射影响范围空间划分的实际情形,进而为空间分析和空间优化提供有力支持。算法过程主要包括:设施邻近道路结点检索和分界结点计算;基于网络最短路径分析Dijkstra算法和分界结点计算的网络Voronoi划分;基于空间离散化、邻近道路分析的空间Voronoi划分及其矢量化处理算法。计算实验结果表明本文提出算法可靠和高效,能够模拟出具有预期精度和形态复杂的网络Voronoi面域图形。     

横-纵扫描的Voronoi图栅格生成算法

Voronoi图是计算几何学中一个重要数据结构,在诸多领域具有广泛的应用。栅格扫描算法符合计算机离散特征,优化了欧氏距离算法,是最优的栅格Voronoi图生成算法之一。但是,由于栅格单元距离与欧氏距离的差异,在扫描过程中部分单元的归属不可避免地产生一定的误差,使栅格Voronoi图的应用受到一定限制。本文针对传统扫描算法存在的误差缺陷,提出了一种基于横-纵扫描的栅格Voronoi图改进生成算法。首先,深入分析了传统扫描算法产生误差缺陷的原因和区域分布特征;然后,以3×3邻域为模板,在一个正常周期的水平(横向)扫描后,增加一个周期竖直(纵向)扫描,即通过横-纵两个周期扫描实现Voronoi图的准确生成;最后,应用不同的栅格数据进行了试验对比,结果表明:改进后的算法既具备扫描算法效率上的优势,同时解决了原算法扫描的误差缺陷,在高效生成的同时把误差限制在一个格网以内。     

离散地形曲面上的精确Voronoi图直接生成算法

Voronoi图是地学计算中的一个基本结构,但是在地形曲面上,它还缺乏能与平面Voronoi图媲美的精度和成熟的算法。在离散地形曲面的不规则三角网格网上引入计算几何的测地距离场,从格网边上的距离场奇点逐步生长代表平分线的双曲线,由双曲线的排列得到离散曲面的精确划分,再将划分的面片聚类,生成精确的测地Voronoi图(geodesic Voronoi diagram,GVD)。然后,从定量与定性两方面对精确Voronoi图进行了检验,证明GVD可以给地形曲面空间分析带来基础性改进。基于奇点生长和双曲线排列的直接算法避免了现有算法对格网面片的过度细分与预处理,整体上直观易行,为数字地形分析发展严密的Voronoi图分析提供了有益探索。     

基于六边形网格的球面Voronoi图生成算法

利用二十面体施奈德等积多面体投影构建了球面多分辨率六边形层次网格;通过边界四元组将六边形单元分解到四元三角形及其子单元中处理;利用改进的四元三角网编码方案建立了网格的数字空间、单元层次编码模型和不同实体在球面上的表达方法。在此基础上,提出了球面Voronoi图的生成算法。实验结果表明该算法与现有算法相比具有更高精度。     

两种地图点群综合算法的比较

通过搭建实验程序,分别对基于非加权Voronoi图和加权Voronoi图的点群自动综合算法进行验证,详细对比和分析两种算法计算结果对点群的统计信息、拓扑信息、度量信息和专题信息的传递情况,计算部分结果的相似度,从而得出加权Voronoi图点群综合算法更优的结论。     

基于面向对象的Voronoi图生成算法

面向对象方法是当前较为流行的程序设计方法。针对目前一些生成Voronoi图的算法中所存在的不足，探讨面向对象技术在Voronoi图的生成中的应用。     

基于多层次QTM的球面Voronoi图生成算法

随着格网层次的增大,基于全球离散格网的球面Voronoi图生成算法的格网数据量与Voronoi图生成时间都呈指数增长,在高层次时容易出现算法效率较低,甚至内存溢出无法执行等情况。利用球面四元三角格网的层次性,提出了一个基于多层次QTM的球面Voronoi图生成算法。首先用全球低层次QTM格网生成Voronoi图,然后对Voronoi边界格网进行再次剖分,得到下一层次的Voronoi图,重复进行,直至达到目标层次。实验结果表明,相对于单一层次的确定归属算法和扩张算法,该算法能够生成更高层次的Voronoi图,且效率较前两者分别提高了22倍和25倍(第9层)。     

基于结点逼近提取的平面点集Voronoi图构建算法

提出一种基于结点空间逼近、精确提取以及面向拓扑关系生成的2维平面点集的构建方法。主要给出了搜索矩形域及其剖分概念、Voronoi图的基本性质、矩形域与Voronoi图结点关系的定理及其证明、基于链队的矩形域剖分和结点逼近机制及结点提取策略、基于条带有序表的最近邻近发生元快速检索算法、矢量Voronoi图的拓扑关系建立算法等。经过算法分析和程序试验验证本文算法的时间复杂度为0（n log2 n）,本方法可以扩展到平面任意发生元Voronoi图的构建,具有简洁、高精度、鲁棒性、高效、适合于海量数据等特点,并且具有较好的实用价值和应用前景。     

增/删点后的Voronoi图构造法研究

论述了在原Voronoi图的基础上增加点和删去点后生成新Voronoi图的算法.在增点过程中,针对新增加点后不满足Delaunay三角网特性的情况,利用最大最小角规则进行局部优化,根据优化后的三角网生成新Voronoi图;在删点过程中,针对删点的不同位置情况,修改相应Voronoi域,生成新Voronoi图.     

脉冲耦合神经网络支持下的网络Voronoi图构建

针对网络Voronoi图中点与点之间通过实际路径距离而非传统欧式距离相连,在实际应用中较平面Voronoi图更加合理,该文提出了一种基于改进脉冲耦合神经网络的网络Voronoi图构建算法。借助模型的自动波发放及并行处理特性,较好地实现了基于路网的网络空间剖分,顾及了道路网及其点群自身属性对其服务范围的影响。实验表明,该算法实现了点群网络Voronoi图的构建,最短路径思想的引入使得构建的网络Voronoi图符合Voronoi图基本特征,可以用来表示点群的服务范围,不仅如此,算法的并行特性保证了算法的高效率。     

基于Voronoi图的空间关联规则挖掘方法研究

提出了利用Voronoi图作为辅助工具实现连续空间离散化的方法,并给出了基于Voronoi图构建空间事务数据库(spatial transaction database,STD)的算法。在此基础上,采用经典的Apriori算法来例证如何从STD中挖掘空间关联规则。实际算例验证了本文方法的可行性和有效性。     

局部动态最优Voronoi图的NNI算法及其在格网数字水深模型中的应用

在分析传统自然邻点插值(NNI)算法局限性的基础上,依据Voronoi单胞和Delaunay三角形的几何特性,提出基于局部动态最优Voronoi图的NNI算法。阐述该算法的基本原理和实现步骤,并在VC++环境下结合多波束测深数据对其在格网数字水深模型(Grid-DDM)中的应用进行了验证。试验表明该算法具有执行效率高、插值精度不丢失等优点。     

一种面向多尺度面状居民地匹配的Voronoi图自适应构建算法

针对现有基于发生元离散化思想的Voronoi算法在计算效率与边界位置精度之间难以平衡控制的问题,提出了一种基于邻居对分类插值策略的面向多尺度面状居民地匹配的Voronoi图自适应构建算法(adaptive Voronoi diagrams algorithm for matching multi-scale areal residential areas, AVARA)。首先,利用居民地多边形的质心构成的Delaunay三角网计算出居民地邻居对;其次,根据邻居对之间的最小距离及其最小面积外包矩形的边长最小值的大小关系将邻居对分类;然后,根据邻居对类别采用相应的方法在居民地边界上自适应地内插点;最后,基于内插点集及居民地的顶点集构建居民地的Voronoi图。利用1∶10 000和1∶50 000居民地数据进行了Voronoi图实验,结果表明,在1∶10 000数据中,AVARA在局部位置精度与时间性能方面均优于通视点法、3 m及6 m等间隔内插点法;在1∶50 000数据中,与30 m等间隔内插点法相比,AVARA取得了较高的局部位置精度;与15 m等间隔内插点法相比,AVARA的位置精...     

QTM格网空间中的球面Voronoi图并行生成算法

根据球面四元三角网（quaternary triangular mesh,QTM）的离散特征及图形处理器（graphics processing unit,GPU）的多线程原理,用距离的计算与比较代替传统的扩张操作,提出了一种基于QTM的球面Voronoi图并行生成算法,并给出了Voronoi边界提取算法。利用C++语言及统一计算设备架构（compute unified device architecture,CUDA）开发了实验系统。实验结果表明,本文算法能够在球面上快速生成点、线、面数据集的Voronoi图,且能够将Voronoi误差控制在两个格网以内。同时,GPU并行计算的使用,提高了算法的效率。     

基于六边形网格的球面Voronoi图生成算法

利用二十面体施奈德等积多面体投影构建了球面多分辨率六边形层次网格;通过边界四元组将六边形单元分解到四元三角形及其子单元中处理;利用改进的四元三角网编码方案建立了网格的数字空间、单元层次编码模型和不同实体在球面上的表达方法.在此基础上,提出了球面Voronoi图的生成算法.实验结果表明该算法与现有算法相比具有更高精度.