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

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

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

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

利用缓冲区动态生长模型进行岛屿自动选取

针对当前岛屿自动综合算法使用的Voronoi图在表达岛屿密集程度时存在缺陷，从而导致选取结果难以满足生产实际需要这一现状，提出一种利用缓冲区动态生长模型进行岛屿选取的自动选取方法。首先，从原理上分析了Voronoi图表达空间数据密集程度的缺陷，并设计了能克服此缺陷的缓冲区生长模型；然后，定义了距离矩阵、岛屿缓冲区标识和增长因子，构建了缓冲区生长模型；最后，通过对模型的动态构建和更新实现了岛屿的自动选取，并选取多组不同海域、不同分布特征的岛屿资料图进行了实验验证。实验结果表明，缓冲区生长模型有效解决了Voronoi图表达岛屿密集程度时的缺陷问题，与使用Voronoi图表达岛屿密集程度的岛屿选取方法相比，明显提高了岛屿选取的质量，且可适用于更多的复杂海域。     

导航电子地图增量更新方法研究

针对目前导航系统中普遍采用版本式整体替换方式进行地图数据更新,难以满足用户对数据现势性的要求,研究了导航电子地图动态增量更新的3个关键技术,实现了导航终端的在线增量更新,并在更新过程中对拓扑关系进行动态维护,有效提高了导航电子地图的更新效率。     

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

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

公开版地图数据库的快速更新方法研究

以福建省公开版地图数据库快速更新为例,研究公开版地图数据库快速更新的方法。针对数据精度没有基础地理信息数据库的数据精度高的特点,通过地图服务反馈、各类影像数据、车载导航数据采集等方法和渠道获取变化信息,建立"动态实时更新"的技术流程,同时通过DATE属性提取增量变化信息实现多级比例尺的联动更新。该方法已应用于福建省公开版地图数据库的快速更新,极大地提高了福建省公开版地图数据的现势性与准确性,应急保障出图能力也大大提升,可为其他省提供参考。     

点状地名信息的加权泰森多边形检索法

鉴于地名库中多数地名仅以中心点坐标形式记录其空间位置信息,缺乏其空间范围的具体描述,造成地名检索中的片面性和局限性,本文在深入分析地名及其空间属性、空间关系的基础上,考虑同类型地名的不同性质在检索中的重要作用,利用泰森多边形在地名边界近似中的优势,提出了针对点状地名信息的加权泰森多边形检索法,依据同类型地名的面积属性作为权重指标构建泰森多边形,以近似表达地名的空间范围,进而描述地名间的各类空间关系;并从拓扑关系、方位关系与距离关系3个方面给出了具体公式以计算地名间的空间相似性;最后以行政区划边界近似与检索为例验证该方法。试验结果表明,该方法可较好地近似表达地名空间范围及空间关系,增强了检索词与地理信息资源在空间位置上的相似性度量,检索结果优于传统方法。     

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

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

基于RS和GIS的区域可持续发展实践探讨——以陕西省为例

以陕西省为例,以各城市综合指标为权重计算加权Voronoi图,与陕西省行政区划图比较,研究陕西省的可持续发展能力,探讨RS和GIS作为一种数据获取手段和空间分析工具,在区域可持续发展研究中的作用。结果表明,RS和GIS可以很好地为区域可持续发展服务。     

基于水流扩展思想的网络空间Voronoi图生成

Voronoi图是地理空间设施分布特征提取的重要几何模型,基于不同的空间距离概念可建立不同的Voronoi图。本研究顾及城市网络空间中设施点的服务功能及相互联系发生于网络路径距离而非传统的欧式距离的事实,针对网络空间Voronoi图模型,建立一种网络空间Voronoi图生成的栅格扩展算法。首先对图结构的边目标剖分为细小的线性单元,称作网络空间的栅格化,引入水流扩展思想,将事件点发生源视为“水源”,以栅格单元长度为扩展步长,让水流方向沿着网络上的可通行路径同时向外蔓延,直至与其他水流相遇或者到达边的尽头。该算法可方便地加入网络图结构中的多种约束,如街道边的单向行驶、结点的限制性连接等实际空间限制条件。通过大规模实际数据的“数字城市”POI点服务范围的试验表明该算法的效率高。     

数字海图点群状特征的识别、量测与综合

空间分布特征的保持是点群自动综合的核心和难点所在,为此,本文定义了4个参量：分布范围、分布密度、分布中心和分布轴线,来描述点群目标的结构化信息。利用Delaunay三角网和Voronoi图两种模型,着重探讨了点群分布特征的识别和量测问题,并在识别与量测的基础上,通过Voronoi图的动态构建,给出了点群自动综合模型,通过实际岛群数据的检测,证明了模型的正确性与可行性。     

利用层次Voronoi图进行点群综合

通过距离权重描述点的重要程度,采用改进的k-means算法得到点群的聚类中心,进而以聚类中心为基础,构建了层次加权Voronoi图与Voronoi层次树结构.以点群的分布范围、排列方式与密度为度量,给出了基于Voronoi层次树结构的点群综合方法,确保了点群综合前后在空间形态分布上的一致性.结合地理统计学计算,对综合方法作了进一步的量化评估与优化.经验证,本文方法是可行、有效的.     

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

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

Allocation using a heterogeneous space Voronoi diagram

Spatial allocation is a fundamentally important process reflecting customer behavior, efficient service assignment, districting, etc., and is at the heart of many spatial analytical methods and processes. The Voronoi diagram has proven to be an important mathematical and geometric construct and has been widely applied in various fields because it is intuitive and efficient in the allocation and/or partitioning of space. However, existing Voronoi diagram approaches rely on the assumption that the attribute(s) of continuous space (non-generator points) is homogenous, which often is not the case for many application contexts. This paper introduces the concept of spatial heterogeneity in allocation. A new Voronoi diagram is defined—the heterogeneous Voronoi diagram. A geographic information system-based method is developed to derive the heterogeneous Voronoi diagram using discretized spatial allocation properties. Application of the heterogeneous Voronoi diagram is reported for a planning problem involving emergency drone delivery. Results show that response potential is over- and underestimated when heterogeneity and travel obstacles are disregarded. Further, feasibility, usefulness, and significance are demonstrated for incorporating geographic heterogeneity in the allocation process.     

保持空间分布特征的群点化简方法

群点目标隐含的空间结构化信息是空间分布分析、地图综合感兴趣的内容。对群点目标分布的信息内容区分为存在性、度量结构与拓扑结构，在Delaunay三角网及其对偶Voronoi图模型上对工量结构定义4个在量；分布范围、分布密度、分布中心及分布轴线，顾及视觉识别Gestalt邻近原则，运用三角形“剥皮”法，确立了非凸多边形所表达的群点分布范围，运用图像灰度表达群点分布密度并通过图像处理方法提取分布中心。建立了Voronoi图动态重建进行群点化简的方法，该方法通过边界点和内部点的分开处理，较好地保持了4个空间分布特征。     

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

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

Alternative Areal Decompositions: An Empirical Study

This article compares area data representation with several areal decomposition alternatives in order to determine any improvement to efficiency at the expense of accuracy. This article utilizes the Voronoi diagram as an underlying base data model, combines polygon partitioning and the Voronoi diagram to provide several alternative hybrid areal decompositions, and empirically examines the efficiency and effectiveness performance of these alternatives for popular GIS operations: geometrical, topological and reclassification operations. Experimental results reveal that most areal decomposition alternatives are likely to produce significant benefits in time efficiency while generating different levels of accuracy.     

Raster voronoi tessellation and its application to emergency modeling

Due to the advances in Web technologies,various raster maps are available through Web Map Services such as Google maps and Yahoo maps.These online maps are used to visualize diverse types of disasters.Understanding disasters with these online maps has become an important research issue.In this article,we propose a map-based general-purpose emergency management support system based on a computational model of generalized(multiplicatively weighted,order-k,and Minkowski-metric)Voronoi diagrams.The proposed system tessellates Web maps and models disasters(or emergency response units)having different weights in the complete order from 1 to k-1 in the three popular Minkowski metrics(Euclidean,Manhattan,and Maximum distance)pro-vide insightful information for various what-if emergency scenarios.The proposed map-based emergency management support system systematically supports neighboring queries,districting queries,location optimization queries,and routing queries.We pro-vide specific examples to illustrate how our system supports these queries.     

城市地价动态监测点设置的Voronoi方法

依据国家建设城市地价动态监测体系的要求，以济南市地价监测点的布设为数据基础，分析了利用一般方法布设地价监测点存在的问题，试验了利用Voronoi方法对其进行优化的算法思路，利用Voronoi方法对城市地价监测点布设的技术路线及其可行性进行了分析。     

影像增量动态更新与融合技术研究

在分析目前已有的一些影像数据更新方法的基础上,提出了一种影像增量动态更新与融合的新方法,该方法首先利用图幅格网索引图和新影像数据定位更新变化图幅和范围,然后对不同时期的影像数据进行镶嵌式的增量更新。针对不同时相影像数据间的色彩差异进行色彩均衡处理,而对于不同时相影像数据镶嵌边缘存在像元突变效应进行了基于卷积和反距离加权的图像平滑融合处理。本文对上述方法进行了实验论证和分析,结果表明,该方法具有计算效率高,镶嵌效果好,并对局部地区的影像更新有较好的实用性,解决了因资金、技术有限且局部地区变化速率快等的影像数据动态更新问题。