连续近邻查询方法的研究

连续近邻查询(CNN)是时空数据库中一种重要的查询类型。Voronoi图解决连续近邻查询问题,思想简单明晰,但Voronoi图构造代价太高,尤其是高阶的Voronoi图。本文利用分枝限界的思想去界定预创建Voronoi图生成点范围的上限。提出了一种动态地创建局部Voronoi图的办法解决连续近邻查询问题。这种方法只是在给定查询段上所有点的k个近邻范围上限内创建一个局部的k阶Voronoi图,这样会大大降低基于Voronoi图的连续k近邻查询的代价。     

间接法生成Voronoi图的设计与实现

设计出存储有点、线、面、Voronoi多边形等对象拓扑关系的数据结构,通过边扩展算法先构成Delaunay三角网.在此基础上引入凸包生成算法,生成Voronoi图,Voronoi图是GIS空间分析中一个重要的工具.     

左转算法在间接法生成Voronoi图中的应用

就利用左转算法间接法生成Voronoi图进行了初步的探讨,首先用贪心算法进行平面的三角剖分,然后使用左转算法构建Delaunay三角网,再生成Voronoi图.实践证明使用这种方法在编写程序时程序结构更容易理解和稳定.     

空间点集Voronoi图的海量构造算法及可视化技术

设计空间点集Voronoi图的增量式外存算法以及空间点集Voronoi图的任意平面可视化剖分技术,以"点-线-面-体"的空间数据结构为基础,实现在指定空间区域内生成Voronoi图的新方法.提出的算法数据结构清晰合理,数据交互方案简单有效且无内存限制,发展的可视化技术可以对空间点集Voronoi图进行任意的平面剖分,实现了三维Voronoi晶胞集合体内部结构的可视化.     

基于平面多边形Voronoi图的算法与快速成形应用

探讨了平面多边形的Voronoi图的性质,提出了一种新的求解平面多边形的Voronoi图的算法,其核心思想是单独考虑每个Voronoi图对象,分开计算其分治区,然后再构成一个具有拓扑关系的Voronoi图.这种计算方法较其他现有算法(比如二分法)大幅度提高了求解Voronoi图的成功率,在VC 平台上得到了实现,并应用于快速成形的等距线扫描工艺中.该算法求解平面切片的轮廓的Voronoi图和生成等距线速度快,可以实时生成切片轮廓的全部等距线.试验证明:算法可以减少制件特别是类似大平面制件的翘屈变形,提高制件整体质量.     

离散平面Voronoi图的光栅图形算法

1　引言　　Voronoi图及其对偶Delaunay三角剖分,目前广泛应用于计算机图形生成、CAD/CAM和有限元方法等领域,特别是近十年来,随着计算机图形学的发展,三维图形生成技术的需求,受到了学术界的极大关注.此外,Voronoi图的几何特性,在气象、结晶材料,空中交通管制等领域都得到广泛应用.从目前发表的大量文献看,基本上是基于连续域计算几何出发进行的[1,2],其计算方法主要分成两个类型:一个是增量算法,通过每次增加一个点来计算Voronoi图;另一种是分合算法,通过将点划分成两部分,递归计算每一部分点的Voronoi图,然后再将它们合并.光栅图形…     

Voronoi图模拟生长算法的性能研究

对Voronoi图的模拟生长法进行了系统分析和研究,研究了现有模拟生长算法不能正确处理不连续区域、存在斑马纹和生成元覆盖区域边界不精确等问题,分析了引起这些问题的算法终止条件设置不科学、角增量固定和权值过小等原因,提出了相应的解决方案。在此基础之上,给出了一种Voronoi图模拟生长法的改进算法,提高了现有模拟生长法构造Voronoi图的算法效率。通过实验证实,改进后的模拟生长法算法正确且效率高。     

加权Voronoi区域面积的计算方法

加权Voronoi图是Voronoi图定义的扩展.加权Voronoi区域的面积是加权Voronoi图的一个重要的物理属性.给出了加权Voronoi区域面积的计算方法,即对给定的母点坐标和权重,先求出各Voronoi区域边界上相邻两顶点间的Voronoi边的属性数据,并将每个闭合边界上的属性数据存放在一个循环链表中,最后根据各个循环链表中的数据,计算出各加权Voronoi区域的面积.     

基于粗糙集的居民点选取方法研究

考虑到粗糙集能挖掘数据分类信息,生成客观决策规则,提出一种基于粗糙集的居民点选取方法.通过对影响居民点重要性的多项因素进行约简,生成选取规则;基于约简后的指标信息系统,由知识信息量定义指标的权重,综合评价居民点的重要度;依据数量选取模型结合重要度排序完成居民点选取.以居民地的面积、行政等级、Voronoi图面积以及居民点与重要道路的邻近距离作为评价居民点重要性的指标,实验结果验证该方法能有机结合居民点的空间属性与专题属性,选取规则不依赖专家经验,指标权重较为客观,在不同层次有效传递居民点的多项特征.     

Voronoi图在公共服务设施规划中的应用

在公共服务设施的规划中,Voronoi图能很好的满足分析的要求。根据Voronoi图的对应的Delaunay三角形性质提出了一种的可行效率较高的生成的方法。     

基于ArcGIS环境下多类型数据的三角网和Voronoi图的生成

基于渐次插入算法,在ArcGIS环境下,提取居民地中心点和道路中心线上的点作为离散点,实现了对这些离散点的Delaunay三角网的构建和数据的有效组织,利用ArcGIS提供的接口生成了Voronoi图,实现了多类型数据Delaunay三角网和Voronoi图的生成。     

Voronoi图在足球机器人规划中的应用研究

Voronoi图是计算几何的一个重要分支,它在计算几何理论和应用中发挥着重要作用。在Voronoi图已有的理论基础之上,利用Voronoi图的几何特性分析并解决足球机器人的任务规划问题。     

基于空间改进型Voronoi图的路径规划研究

三维空间路径规划在某些特殊情况下必不可少，如无人机为了降低敌雷达的探测概率，利用山谷或其他特殊地形飞行.在原有基于平面Voronoi图的路径规划基础上，将Voronoi图的概念进行了推广，提出了“空间改进型Voronoi图”的概念.研究了不同威胁体下“空间改进型Voronoi图”构图的一些基本原则，包括不同威胁体下“空间改进型Voronoi图”作图法，以及突发威胁体下空间局部路径重规划区域原则和空间局部最优路径选择原则等.仿真结果表明整个模型构架的基本思路可行.     

基于Voronoi图的无线Mesh网络网关部署算法

将Voronoi图应用于无线Mesh网络网关部署问题中,提出了基于Voronoi图的无线Mesh网络网关部署算法.算法首先根据已知AP(access point)位置对网络拓扑图进行Voronoi划分,使得每个终端与其最邻近的AP属于同一区域;然后提取每个Voronoi区域与相邻区域的交点作为备选网关位置,依次计算以每个备选网关作为根节点的网络最小生成树;最后将生成树权值最小、跳数最少的输出作为部署结果.NS2仿真结果表明,在经过Voronoi划分的较小规模网络场景下,所提出算法的丢包率、转发包数量等性能均优于最小权值算法和随机算法.     

传感器网络中基于加权Voronoi图的能量均衡数据采集算法

基于乘法加权Voronoi图在稀疏无线传感器网络中设计了一条优化的数据采集路径.在这个优化路径中,移动采集节点访问一个虚拟Voronoi图的节点子集进行数据收集.这个Voronoi图节点子集是通过精心设计的迭代过程生成的,在给定通信半径内,能够覆盖所有的传感器节点,同时考虑了传感器节点的能量均衡消耗.连接Voronoi节点子集形成的优化路径缩短了数据采集路径的长度,从而缩短了数据采集时延.通过调整虚拟Voronoi图的覆盖系数,可实现满足不同要求的综合考虑时延与能量消耗的折中方案.     

基于断裂点理论和网络加权Voronoi图分析的北京市商业中心辐射域研究

城市断裂点理论作为城市地理学经典理论,与Voronoi图结合将是划分城市商业中心空间势力范围的一种有效工具.尝试对北京市主要商业中心的辐射范围进行了划分,实现了基于道路网络分析的网络Voronoi图和网络加权Voronoi图的构建.对道路系统更新前后构建的网络Voronoi图比较分析,表明构建网络加权Voronoi图是模拟商业中心辐射域的一种有效方法.将断裂点理论与网络加权Voronoi面域图结合,模拟出北京市主城区道路系统更新前后商业中心不同的辐射域空间格局变化,并提取了辐射域覆盖面积、覆盖人口、路网长度、路网密度等信息.实验结果表明:网络加权Voronoi面域图在模拟商业中心辐射域时更加接近地理实际;道路系统更新升级对于商业中心辐射空间格局变化影响明显;商业中心自身规模影响其辐射域的扩张趋势.     

Voronoi图理论与应用新成果

2006年7月2-5日，第3届国际科学与工程中的Voronoi图研讨会（ISVD’2006）在加拿大阿尔伯特省卡尔加里市班夫中心举行。来自加拿大、美国、英国、法国、俄罗斯、日本、韩国、中国等10多个国家的50多位Voronoi图研究专家、学者参加了会议，30多人在大会上作了报告，展示了他们在Voronoi图理论及其应用方面的最新研究成果。     

Voronoi图的扩展、生成及其应用于界定城市空间影响范围

在总结国内外文献的基础上，提出了常规Voronoi图的两种扩展形式，即线的加权Voronoi图和面的加权Voronoi图，并在地理信息系统软件Are/Info的支持下，实现了基于栅格方法的若干类Voronoi图的自动构建，这种方法可以处理任意图形的线状和面状发生元情形。以界定河南省城市空间影响范围为例，尝试了发生元为离散点集的常规Voronoi图和国权Voronoi图应用于界定城市空间影响范围的试验研究。     

基于Voronoi图的复杂对象空间方位关系的推理计算

在分析总结前人研究成果的基础上,研究了复杂对象之间的空间方位关系,提出了基于Voronoi图的空间方位关系的推理模型,并详细论述了该模型的算法实现过程及步骤.实例计算表明该模型是正确和有效的.模型无需区分源目标与参考目标,具有自反性,不受对象的形状、大小、位置和距离等的影响,容易与基于Voronoi图的空间拓扑关系的相关理论结合,形成统一的推理模型.     

基于加权Voronoi图的城市经济区划分方法探讨

在分析目前划分城市经济区的方法的基础上，考虑到加权Voronoi图几何性质的独特性、在空间分割上的合理性以及计算机自动生成的可行性，试图将其应用于城市体系研究．通过深入分析城市断裂点理论的性质，并应用加权Voronoi图对其扩展，发现了包括传统断裂点在内的城市吸引范围的理论上的准确边界，提出了“断裂弧”的概念．通过构建两种不同形式的加权Voronoi图，提出了确定区域中心城市和划分城市经济区的新方法，并以河南省为例进行了实证分析．