A new fast algorithm for computing the distance between two disjoint convex polygons based on Voronoi diagram

Computing the distance between two convex polygons is often a basic step to the algorithms of collision detection and path planning. Now, the lowest time complexity algorithm takes O(logm+logn) time to compute the minimum distance between two disjoint convex polygons P and Q, where n and m are the number of the polygons’ edges respectively. This paper discusses the location relations of outer Voronoi diagrams of two disjoint convex polygons P and Q, and presents a new O(logm+logn) algo- rithm to compute the minimum distance between P and Q. The algorithm is simple and easy to implement, and does not need any preprocessing and extra data structures.

基于Voronoi图的空间点事件统计聚类方法

挖掘地理空间数据中点事件聚集模式对于揭示流行疾病、犯罪分布热点区域及城市基础设施空间分布格局等具有重要意义。针对不同形状、密度和大小的显著空间点聚集模式的识别,目前以空间扫描统计为代表的方法虽然可以对空间点聚类的显著性进行统计推断,减少虚假聚类结果,但其主要用于识别球形或椭圆形状的聚簇,对于沿着街道或河道分布的任意形状、不同密度的显著空间点聚簇识别还存在局限。因此,本研究提出一种基于Voronoi图的空间点聚集模式统计挖掘方法。首先,采用Voronoi图来度量空间点分布的聚集性,将空间点聚类问题转化为热点区域探测问题;其次,结合局部Gi*统计量探测统计上显著的空间点聚簇;最后,通过模拟数据和真实犯罪事件数据进行实验与对比分析。结果表明:本方法能够有效探测任意形状的空间点聚类,并对空间点簇的显著性进行统计判别,识别显著的空间点簇,减少随机噪声点的干扰;聚类识别结果优于现有代表性方法,如DBSCAN算法、空间扫描统计方法等。

基于非匀质空间下Voronoi图的城市影响范围研究

为解决城市影响范围研究中忽略非匀质空间的问题,本文以光栅扫描算法为基础,提出了一种非匀质空间下面状加权Voronoi图生成算法。首先,对面状目标和栅格空间赋予不同的权重;其次,采用3×3邻域模板进行十字交叉4次光栅扫描,在距离变换中按栅格像元传递权重对距离进行分解,完成非匀质空间下面状加权Voronoi图的生成;最后,以山西省11个地级市为研究区,进行了验证。结果表明,改进后的算法实现了非匀质空间面状加权Voronoi图的生成;相比点状加权V图,城市之间权重差异较大,距离较近时,面状加权V图更适合城市影响范围划分。

基于Voronoi的新型垂直自动泊车路径规划启发函数

即使对经验丰富的司机来说,停车也可能是一项艰巨的任务,尤其是在停车位很窄的老城区车位。考虑到Reeds-Shepp曲线和Dubins曲线的局限性,在满足启发函数设计原则的情况下不考虑车辆运动学约束,采用曼哈顿距离并引入广义Voronoi图设计Hybrid A*启发函数,并进行仿真分析。仿真结果表明,在设计的启发函数下规划的路径较为笔直和简洁,未出现不必要的倒车和不必要的转弯,较Reeds-Shepp曲线和Dubins曲线作为启发函数规划的路径有较大的改善。

基于Voronoi图的GIS空间分析研究

从GIS应用需求的角度 ,总结与分析了Voronoi图的基本性质 ,着重介绍了基于Voronoi图的空间分析方法与模型 ,包括地形分析、设施布局分析、数据概括和空间推理 ,并指出了进一步的研究与发展方向。

基于网络加权Voronoi图分析的南京市商业中心辐射域研究

道路网络在城市社会和经济活动中发挥重要作用,它是联系商业中心与需求间的桥梁,道路系统的更新与变化必然会对它们的关联产生影响。Voronoi图是划分势力空间的有效工具,基于道路网络分析构建的加权Voronoi图可以模拟城市商业中心功能辐射的实际情形。本文给出了基于道路网络分析的Voronoi图和加权Voronoi图构建方法,通过对各种Voronoi图的比较分析,认为基于网络路径时间分析构建的加权Voronoi面域图在商业中心辐射域模拟中最为有效。将空间相互作用和断裂点理论与网络加权Voronoi面域图相结合,模拟不同交通条件下南京市商业中心辐射域空间格局及其需求覆盖变化,并提取了辐射域的覆盖面积、覆盖人口、最远辐射路径距离和平均辐射路径距离等信息。对商业中心的地铁邻近度与其辐射域的扩张面积进行相关分析,采用域邻接矩阵描述空间划分平衡与不平衡之间的相互转变过程,可分析道路系统变更后商业中心之间空间竞争的变化趋势。分析结果表明商业中心的地铁邻近度与辐射域的扩张具有较大的相关性,快速轨道交通在商业中心空间竞争中发挥关键作用。

基于Voronoi图的林分空间模型及分布格局研究

以南洞庭湖龙虎山次生林为研究对象,建立林分Voronoi图模型,通过该模型表示林分空间结构特征,提取林木空间量化信息。在此基础上,引入变异系数量化Voronoi多边形面积的变化率,将林木空间格局分析转化为计算Voronoi图变异系数,并将计算结果与角尺度作相关性比较。结果表明:林分Voronoi图模型能准确表达林木邻接关系、相邻木距离及角度、空间密度等重要空间信息;大尺度取样时(76m以上),变异系数趋于稳定,林分整体空间格局呈接近随机分布的轻度聚集;Voronoi图变异系数和角尺度存在显著的正相关关系,进一步说明本研究格局分析方法的可行性和有效性;受多种因素影响,乔木层主要树种在不同发育阶段的空间格局表现出强烈的时间和空间动态特性,且小径木多为聚集分布,大径木呈轻度聚集或随机分布。基于Voronoi图的林分空间模型及格局分析方法,从空间上表征林木的生长繁育特性、种内种间关系、资源及环境分布特征,为计算几何方法应用于林分空间经营提供了新的思路。

基于VORONOI图的无人机空域任务规划方法研究

无人机任务规划系统对充分发挥无人机自主控制与飞行和自主执行任务的能力起着十分关键的作用。在分析VORONOI图的性质的基础上,以压制敌防空火力作战任务想定为背景研究基于VORONOI图的无人机任务规划技术,重点讨论了规划环境建模、航路代价计算和初始航路选择问题。最后对该方法进行了时间和空间性能分析。

基于Voronoi图的农村居民点空间分布特征及其影响因素研究--以北京市昌平区为例

采用GIS查询统计与Voronoi图CV值相结合的分析方法,研究了地形、公路及河流等环境因素对北京市昌平区农村居民点空间分布特征的影响。结果表明:地形是影响农村居民点空间分布的主导因素,平原地区农村居民点用地比例较高,规模较大,密度较高;山区农村居民点用地比例较低,规模相对较小,密度也较低。公路交通是影响农村居民点空间分布的重要因素,91.19%的农村居民点分布在距离主要公路距离小于1500m的范围内;河流对农村居民点分布也有一定影响,距离河流越远,农村居民点密度越低。

Voronoi图用于确定城市经济影响区域的空间组织

确定城市经济影响区域的空间组织是一项十分复杂的工作,在区域规划和城市规划中有着重要的理论和实际意义.目前,通常是利用数理统计的方法进行城市的分级,并以此来确定区域中的中心城市,未充分考虑区域空间中城市之间的竞争关系;确定城市经济影响区域时,往往采用断裂点公式来划定两两城市之间的分界线,当城市的数量较多时,这种方法有困难且工作十分繁杂.本研究提出可以用Voronoi图来确定各级城市的空间影响区,并利用Voronoi多边形邻居关系的性质来确定城市体系中不同等级城市之间的空间组织关系.

基于Voronoi图的测度点状目标空间分布特征的方法

点集的V orono i图是对点集的一种空间分割方式,不同分布的点集可以形成V orono i多边形面积的不同变化,可以通过计算点状目标的V orono i多边形面积的变异系数(CV值)方法,来分析点状目标的空间分布特征.基于国家资源环境数据库,进行了安徽省农村居民点的空间分布特征分析.结果表明安徽省农村居民点总体上属于集群分布,而各县市的分布规律是,中北部平原、低丘陵地区农村居民点呈随机分布,南部、西部山区呈集群分布.最近邻点指数和CV值的相关系数表明,两者之间存在显著的负相关关系.这表明,计算点状目标的V orono i多边形面积的变异系数方法,也是测度点状目标空间分布的一种简便有效的方法.

森林空间结构分析中基于Voronoi图的样地边缘校正

【目的】提出一种新的样地边缘校正方法——Voronoi图结点距离判定,为森林空间结构分析和调控提供技术支撑。【方法】为评估Voronoi图结点距离判定的性能,引入量化评估指标RMSE,采用角尺度、聚集指数和大小比数等空间结构指数构造RMSE,并通过设置不同场景的模拟样地和调查样地,将Voronoi图结点距离判定与其他校正方法进行比较和分析。【结果】缓冲区法、最近邻体校正、Voronoi图结点距离判定虽同属减少样本类校正方法,但各校正方法的性能及效果受到林木样本量、林木空间格局、空间结构指数、样地情况等因素影响,差异很大。缓冲区法虽简单易行,但样本浪费严重,且同时存在漏判和误判2种误差,其校正样地的RMSE曲线通常维持在较高水平。Voronoi图结点距离判定可视为缓冲距离随边界林木实际分布自适应变化的校正方法,具备更强的校正能力,能最大限度地排除样地外林木的边缘干扰,在角尺度、大小比数以及样本量充足的聚集指数计算中均优于其他校正方法,但也存在误判及样本利用率偏低等不足。最近邻体校正的性能介于缓冲区法和Voronoi图结点距离判定之间,其RMSE曲线的整体水平要高于Voronoi图结点距离判定。【结论】林木样本量与样地边缘校正密切相关,对于样地大小和林分密度的任何改变最终都体现在林木样本量的增减上,维持充足的林木样本对于样地校正尤为重要。林木空间分布是影响样地边缘校正的另一重要因素,当林木呈随机分布或均匀分布时,样地边缘校正的重要作用能得到更好体现。此外,样地经过校正后,各类空间结构指数的计算精度均能获得显著提高,且聚集指数的计算需要样地提供充足的林木样本量。

基于Voronoi图的丹顶鹤巢址空间格局分析

依据1996年、2003—2007年扎龙保护区丹顶鹤巢址数据,利用Voronoi图理论,分析了巢址的空间分布特征,计算了其拓扑指数—Voronoi图面积。结果表明,丹顶鹤巢址空间分布具有明显的空间聚类特征。以扎龙保护区的2006年巢址、居民点、国道和铁路为对象,构成其Voronoi图,较好地说明了人类活动对丹顶鹤巢址的空间格局的影响,研究结果对丹顶鹤栖息地的保护将起到重要作用。

基于带权Voronoi图与地标的空间位置描述

地标是最基本的空间知识,在空间知识的表达和推理中具有重要作用,常被用来作为空间位置描述的参照物。在实际中,不同地标在空间位置描述中的权重不同,如何考虑地标权重建立符合人类空间认知的形式化方法是空间知识表达的重要研究内容。该文从视觉、语义和空间结构等方面总结影响地标权重的因素,通过认知实验获取北京大学校园内10个地标的权重。在此基础上,基于带权Voronoi图提出生成指定目标对象空间位置描述的形式化方法,并采用认知实验中的数据,以北京大学为例,生成校园内4个指定目标对象的空间位置描述。最后分析了引起基于带权Voronoi图与地标空间位置描述不准确的因素,并提出下一步的研究方向。

基于Voronoi图和Delaunay三角网的林分空间结构量化分析

利用Voronoi图具有最近性、邻接性特点,以单株木视为平面点构建Voronoi图和Delaunay三角网,此结构具有以下特点:对象木的最近邻木株数与Voronoi图中相对应多边形边的数目相等;对象木与最近邻木的距离和Delaunay三角网的相对应边长相等;任意2个最近相邻木的夹角即为对应Delaunay三角网2条边的夹角。在广东湛江红树林国家自然保护区选择样地进行试验,把基于Voronoi图和Delaunay三角网计算林分空间结构指数的结果与最近邻木数取4的传统算法结果进行对比分析,结果表明:两者在计算混交度、大小比数时结果有较高的相关性和一致性,但两者在计算角尺度时结果差异较大,构建Voronoi图确定最近邻木时各个方向都有选取,角尺度的取值均小于传统计算方法,但是Delaunay三角网结构本身较好反映个体在水平地面的分布格局,且基于Voronoi图和Delaunay三角网林分空间结构研究不需要对象木与邻木距离量算和角度测量。

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

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

基于Voronoi图的侧柏游憩林空间结构分析

为了探究侧柏游憩林的林分结构调控途径,采用聚集指数、混交度、大小比数及开敞度4个指数,基于Voronoi图空间结构单元分析了北京西山国家森林公园典型侧柏林的林分空间结构特征。结果表明:1)林分平均聚集指数为1.31,林木总体上呈均匀分布格局;2)林分平均混交度为0.427,树种空间隔离程度较低,且空间配置较为简单;3)林分平均胸径和树高大小比数分别为0.512和0.497,林木胸径及树高分化均不太明显,说明林分处于中等竞争状态;4)林分平均开敞度为0.320,林内空间较为开阔,林木生长空间基本充足。侧柏游憩林的林分空间结构基本合理,建议通过少量间伐或补植乡土阔叶树种等措施优化林分空间结构,进一步提升该地区侧柏林的游憩价值。

基于Voronoi图和Delaunay三角网的杉木游憩林空间结构

基于Voronoi图和Delaunay三角网建立空间结构单元的方法,采用聚集指数、混交度、大小比数、竞争指数和开敞度5个指数分析福建将乐国有林场典型游憩林的林分空间结构特征。结果表明:杉木游憩林以1株对象木周围6株最近邻木的构成形式最为常见,林分平均聚集指数R为1.05;林木空间分布格局呈均匀分布;林分平均混交度M-为0.48,树种空间相互隔离程度不高,处于中等混交状态;林分平均胸径和树高大小比数分别为0.49和0.51,林木胸径、树高分化不太明显,林分处于中等竞争状态;优势树种中,杉木竞争指数CI为346.27,具有较强竞争力;林分平均开敞度K-为0.21,林分内林木生长空间不足。在维持现有林分条件的基础上,应增大林内开敞度以便进一步优化林分空间结构,提升游憩林的游憩价值。

基于投影加权Voronoi图的GIS空间竞争分析模型研究

提出加权Voronoi图的一种新形式———投影加权Voronoi图,由此形成平面剖分中的空隙(竞争三角形)可用于GIS空间竞争分析模型。进而分析不同的剖分模型以及竞争三角形的特性和分布。最后提出这种空间分析方法的应用领域。

基于线性四叉树结构的Voronoi图反向膨胀生成方法

提出一种基于线性四叉树结构并顾及矢量与栅格计算性质的Voronoi图生成方法,其核心思想是利用线性四叉树结构以减小空间剖分所产生的空间复杂度,改变膨胀模拟操作的计算方向以减小时间复杂度。讨论了基于数学形态学的反向膨胀计算模型及推理出基于该计算模型的几个优化计算性质。实验验证,这种方法能够有效地平衡时空复杂度,并且易于求取邻元,其时间复杂度小于均匀格网结构与常规四叉树结构。一般情况下,空间复杂度小于均匀格网结构。