一种异质空间下加权Voronoi图的栅格生成算法

针对现有Voronoi图算法很多将被划分区域理想化为匀质空间，忽略了所依赖的传导方式及空间差异性的问题，该文提出了一种异质空间下加权Voronoi图的栅格生成算法。首先根据目标中心强度确定每个目标的影响权重，根据空间传导能力确定每个栅格的传导权重，然后进行十字交叉光栅扫描，在距离变换中按栅格对距离进行分解，将目标影响权重和栅格传导权重纳入变换公式，最后连通每个栅格到最近目标点的最短路径。该算法兼顾了目标中心强度、几何形状以及空间差异性，实现了异质空间下任意形状目标加权Voronoi图的生成。实验证明，该算法时间复杂度不受目标数量、分布和形状的影响，比普通Voronoi图算法更适合复杂空间下的城市影响范围划分。     

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

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

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

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

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

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

集成距离变换和区域邻接图生成Delaunay三角网的方法研究

基于距离变换和区域邻接图,提出了一种D-TIN(包括约束的D-TIN)的生成方法。利用D-TIN是Voronoi图的几何对偶这一特性,使用距离变换获取点的Voronoi图,使用区域邻接图获取点在该Voronoi图上的空间邻接关系,以生成D-TIN或者约束的D-TIN。实验表明,与经典的基于数学形态学生成的D-TIN和约束D-TIN的方法相比,本文算法可以分别提高约57.70%和56.64%的效率。     

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

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

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

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

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

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

高重叠度机载SAR影像镶嵌线自动生成及优化

针对传统的镶嵌方法无法实现高重叠度机载合成孔径雷达(SAR)影像快速、无缝镶嵌的问题,该文基于顾及重叠的面Voronoi图,提出了一种接缝线网络生成及优化方法。采用改进的八邻域边界跟踪算法提取影像有效区域并将其简化为四边形,利用改进的中轴线算法提取重叠区的接缝线并对影像有效区域进行切分生成互不重叠的Voronoi面,快速生成初始接缝线网络;提出了一套接缝线优化方法,实现了机载SAR影像高重叠度高、重叠情况复杂易导致的接缝线网络的孔洞消除。利用高分辨率机载SAR影像对本文算法进行验证,结果表明该方法有效克服了机载SAR影像镶嵌的小孔洞问题,能生成无缝且唯一的接缝线网络,从而实现影像的高效、自动镶嵌。     

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

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

基于Voronoi图的空间邻近定义与查询

首先在点Voronoi图的基础上,引进了空间目标的Voronoi图的定义,进而论述了空间目标Voronoi图在GIS中定义空间邻近及其邻近查询中的作用。最后给出了部分实验结果。     

基于Voronoi图的长春市变电站选址

利用Voronoi图的最邻近性和空心圆特征,结合实际用电需求,通过ArcGIS与Matlab进行迭代模拟分析,得到长春市规划变电站位置,从而为变电站的具体空间落位提供了可靠依据。     

顾及数据空间分布特性的模糊C-均值聚类算法研究

利用描述空间数据分布的Voronoi图的有关理论分析了样本空间数据分布特性，从理论上论述了样本集中各类样本数差异较大产生的根源，并在此基础上提出了一种顾及数据空间分布特性的模糊C—均值聚类算法。     

基于Voronoi图的空间方向关系形式化描述研究(一)

空间方向关系形式化描述模型是空间方向关系研究的难点和重点，目前尚无完善的模型出现。首先提出了影响空间方向关系的两个因素目标：一是两目标群凸壳的直径；二是目标的可视性。论述了运用平面目标Voronoi科作为两目标指向线的“替身”来描述方向关系在理论上的可行性。本文的结论是：Voronoi图是描述空间方向关系的良好工具。     

数字海图水深注记的自动选取

水深注记作为表示海底地形地貌特征的主要制图要素,它的正确选取对于保证航海安全、反映海底地貌起伏具有重要意义。针对传统的水深注记方法,该文提出一种顾及多重约束条件的水深注记选取方法。在总结水深注记综合约束条件基础上,以Vononoi图为支撑几何构造,对水深注记综合涉及的地形特征、空间分布特征、邻近特征3个方面的综合约束进行了形式化定义;借鉴人工选取的思想,在水深综合约束条件重要性排序的基础上,通过反映地形、空间分布、邻近关系等主体特征的重要水深的依次选取,以及背景水深的抽稀实现水深注记选取;最后以实测数据进行实验,验证该方法的有效性。     

基于Voronoi图的空间方向关系形式化描述模型

运用认知心理学信息加工的观点,建立了基于Voronoi图的空间方向关系形式化描述模型,并详细阐述了模型的逻辑结构、数据结构和空间方向的计算过程。为了验证模型的正确性,列举了该模型计算空间方向的几个例子,并总结了模型的优、缺点。     

平面离散点集拓扑邻近稳定区域计算模型

本文利用Voronoi图及其对偶Delaunay三角网研究了平面离散点集拓扑邻近稳定区域的计算方法,证明了点的拓扑邻近稳定区域必须满足的两个条件,给出了点的拓扑邻近稳定区域定量计算模型,并通过实验证明其正确性。     

梯度Voronoi图及其构建算法

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

混合三角网极化干涉SAR影像配准

干涉雷达配准过程中,像对间的变换模型可以通过有理多项式进行拟合,参数的解算需要均匀分布的高精度联系点,传统算法或者只重视联系点的权重,或者只考虑联系点的分布,极大地降低了多项式拟合的精度。提出一种兼顾联系点权重与分布的Voronoi图辅助配准算法,把该算法应用于中国西部某地区Cosmos-Skymed-1/2 X波段干涉数据的处理。实验表明,相对于现有方法,该算法可以提高匹配成功率,得到更高的相关系数,获得分布更均匀的联系点,从而解算出精度更高的变换参数。