基于坡度自适应的机载LiDAR分割算法

本文提出了一种适用于离散LiDAR数据的区域生长算法:将离散点云数据重采样为规则格网,通过坡度自适应区域生长法分割规则格网,获得不同的面片;建立各个分割面片之间的拓扑关系,将分割面片划分为粗差、植被、建筑物和地面;检测原始激光脚点到DTM的距离,判断是否为地面点。文中采用ISPRS提供的测试数据验证了算法分割的有效性。     

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

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

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

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

椭球面三角形外心的地图代数解法

椭球面三角形外心到3个相邻顶点的大地线距离都相等。面向椭球面空间的外心大地坐标的求解对于椭球面Voronoi图的生成和椭球面Delaunay三角网的构造具有重要作用。利用基于地图代数理论的矢栅结合方法,首先基于地图代数测地变换建立高精度椭球面空间距离场,再通过边界跟踪配对确定外心所在的栅格范围,最后通过数值计算内插生成初始等距点并不断逼近外心的精确大地坐标。试验结果表明,采用本文方法求解的椭球面三角形外心大地坐标,在103~104 km跨度内其定位误差小于0.001m,且算法非常适用于海量空间数据的高精度快速计算。     

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

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

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

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

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

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

基于O-QTM的球面VORONOI图的生成算法

提出了基于“Q－QTM”（Octahedral Quaternary Triangular Mesh）剖分的球面Voronoi图的格网生成算法；首先介绍了球面的QTM格网划发和编码方法，并根据地址码进行邻近球面三角形的探索；然后，参照数学形态学原理，重新定义了球面三角网的膨胀操作和膨胀算子，利用球面实体的递归膨胀来生成球面Voronoi图。应用VC^ 语言在OpenGL3维平台上开发了相应的实验程序，实验结果表明：利用此算法可生成球面上任意实体的Voronoi图，且生成点、弧和曲面Voronoi图的时间复杂度是一样的；而其误差受球面距离的影响较小，主要与球面实体的位置有关。最后给出了本文研究的结论及进一步的工作。     

栅格法构建沃罗诺伊图的扫雷算法

沃罗诺伊(Voronoi)图在很多领域都具有广泛应用,因此构建Voronoi图具有重要的现实意义。本文基于栅格法提出了一种新的Voronoi图构建算法——扫雷算法。该算法不需要欧氏距离计算,能减少计算耗时,并可通过改变相关参数实现对生成的Voronoi图的精度控制,同时可用于广义Voronoi图的构建。经过实验和精度评定得出,扫雷算法能很好地构建生长元为点、线、面的Voronoi图,并具有较高的生成精度。     

面向雷利法则的加权Voronoi图生成方法

Voronoi图及其生成是计算几何的重要内容。针对传统栅格加权Voronoi图的权重界定局限性,以及栅格数据下Voronoi图生成的计算效率问题,本文研究了基于雷利法则的生长元规模权重和栅格欧氏距离变换权重作为综合权重条件下,规避单图幅背景栅格与每一生长元之间的距离计算,根据生长元各自距离变换图幅构建栅格加权Voronoi图,即雷利Voronoi图（Reilly Voronoi diagram,RVD）的地图代数生成方法。经试验验证,该方法生成的Voronoi图不仅完善了传统的权重因素,而且避免了因背景栅格与生长元的距离运算、判断而产生的大量计算,证明了该方法的切实可行性。     

一种面向多尺度面状居民地匹配的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的位置精...     

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

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

顾及方向关系的农村居民地聚类方法

农村居民地空间分布具有独特的规律性和复杂性,Voronoi图在表达居民地分布特征方面有显著优势。针对当前空间聚类较少考虑实体方向关系的问题,基于Voronoi图提出一种顾及方向关系的农村居民地聚类方法。首先,构建距离约束的Voronoi图,并构建居民地实体间的Voronoi邻近图;然后,利用无向特征与有向特征来综合评价居民地实体间的聚集强度;最后,消除聚集强度小于阈值的实体对的邻近关系,得到聚类结果。采用浙江省宁波地区部分农村居民地数据进行实验,结果表明,所提方法能够有效聚类不同分布模式的居民地,聚类结果符合人的认知习惯。     

梯度Voronoi图及其构建算法

以生长速度为视角,普通Voronoi图及权重Voronoi图是理想欧氏平面上的生长元匀速生长结果。然而,以Voronoi图为基础的实际分析与建模情况不尽如此,通常表现为非理想平面的非匀速生长过程。本文以权重距离函数描述各向异性的非理想平面,以其时间消耗导数一致性形式化生长速度,定义一种新的Voronoi图——梯度Voronoi图。通过以高程变化诱发的梯度生长为例,借助栅格空间中形态学膨胀操作,给出梯度Voronoi图的典型构建算法。算例与分析表明,在等距离边界、势力范围与邻近关系表达方面,梯度Voronoi图更具优势。     

四孔六边形全球离散格网一致瓦片层次结构编码运算

全球离散格网系统是支持多源地球空间信息融合处理的有效解决方案,格网系统单元层次关系及全球统一编码运算是研究难点。首先,根据四孔六边形剖分特点,提出封闭二十面体表面的一致瓦片层次结构;然后,利用复进制数建立一致瓦片层次结构的编码数学模型,并等价设计全球统一编码运算、编码邻近查询、编码与地理坐标转换等算法;最后,设计了格网层次结构验证和编码运算效率测试实验。实验结果表明,一致瓦片层次结构的编码与地理坐标转换平均效率分别约是同类成果的2.74、1.73倍,编码邻近查询平均效率约是其7.46倍,且随着格网层次升高,效率优势更显著;与同类成果相比,所提方案瓦片具有一致性,且数量更少,算法复杂度低;层次结构的原理简明易懂,计算机执行效率高,可为多源对地观测数据统一组织管理、处理分析提供理论和技术支撑。     

局部区域多孔径六边形格网系统快速生成算法

六边形全球离散格网系统是支持多源地球空间信息融合处理的优选解决方案,相关研究已引起学术界广泛关注。相较于完整的全球格网,局部不规则区域格网的应用需求更加广泛,相关生成算法是当前六边形全球离散格网系统研究的重要问题之一。将二十面体相邻三角面组合为菱形逻辑结构,在此基础上,提出一种局部区域多孔径六边形格网系统生成算法。首先,分析格网剖分类型,建立离散整数坐标系,描述多孔径六边形格网单元空间位置;其次,将局部区域分解到球面二十面体的菱形逻辑结构上创建子区域;然后,根据子区域边界设计外接最小菱形遍历算法,剔除与目标区域无关单元;最后,遍历最小菱形,生成多孔径局部格网。对比实验结果表明,提出的算法具有灵活性好、效率高等优点,生成的多孔径六边形格网用于栅格数据组织,可显著减少数据量,具有较好的应用潜力。     

基于模糊思想的改进Voronoi图模型

针对传统Voronoi图模型在空间划分时考虑因素单一、依赖欧氏距离等问题,提出了一种基于模糊理论的改进Voronoi图模型。将带模糊边界的Voronoi图模型应用到武汉市消防调度系统的模拟突发事件处理中,结果表明,相比传统的Voronoi图模型,能够提高空间划分精度,将应急调度的准确度提高20%以上。