不同交通网络速度的Voronoi图的结晶生成

针对以欧氏距离为度量的Voronoi图所分割必须是均质空间的局限性,为了体现实际分析中的交通网络所导致的空间不均质性,在现有Voronoi图理论成果的基础上,提出了以交通时间距离为度量的基于交通网络的Voronoi图的概念,运用结晶生成法通过C#软件编程实现了不同交通网络速度的基于交通网络的Voronoi图的生成程序。该方法进一步完善和丰富了Voronoi图理论,拓展了Voronoi图的应用范围,体现了实践应用价值。     

一般城市Voronoi图的结晶生成

城市Voronoi图是以L1平面上任意两点之间花费的最短时间为距离的一种新型Voronoi图,它要求交通网络路线仅为水平或垂直方向。然而,客观世界中存在大量曲线交通路线。为了使城市Voronoi图理论研究进一步贴近现实,进而应用于实际,将交通路线扩展为曲线,提出了一种新的城市Voronoi图——一般城市Voronoi图,给出了一般城市Voronoi图的定义、性质和结晶生成算法。     

带线段障碍的城市Voronoi图生成算法研究

带线段障碍的城市Voronoi图是城市Voronoi图的扩展.在步行或使用一般交通工具的情况下,客观世界中存在着许多不能逾越的障碍,甚至连交通网络也时常被一些障碍隔开.许多障碍可简化为线段障碍来处理.给出带线段障碍的城市Voronoi图的定义、性质,结晶生长算法和实例.算法简单,可扩展性好,具有较高的理论价值和应用价值.     

线段障碍Voronoi图的离散生成

Voronoi图是以两点间线段的长度作为距离，对平面的一种分割。然而，在地理环境中，存在着许多自然的或人为的障碍，使得从一点到另一点不能直线到达。为了扩大Voronoi图的应用领域，本文对传统的Voronoi图进行扩充，给出了障碍Voronoi图的定义、性质，以及离散生成线段障碍Voronoi图的方法。     

障碍空间中基于Voronoi图的k最近邻查询

为了提升障碍空间中k最近邻查询的效率,研究了障碍空间中基于Voronoi图的k最近邻查询方法,提出了在障碍空间基于Voronoi图的kNN-Obs算法。该算法采用了两个过程:过滤过程和精炼过程。过滤过程主要是利用Voronoi图的过滤功能,较大程度地减少了被查询点的个数。精炼过程主要根据障碍距离和邻接生成点对候选集内对象进行第二次筛选。进一步给出了处理新增加点的ADDkNN-Obs算法和处理删除点的DENkNN-Obs算法。实验表明该算法在处理障碍空间中的k最近邻问题时具有优势。     

Power图的离散生成

Power图是一种特殊的加权Voronoi图，该图中每个生成元点pi都带有权值wi．给出了一种直接构造Power图的算法．以每个生成元点Pi为圆心，Power距离,√wi为半径画圆；然后将这些圆以不同颜色填充，并以相同速率向外扩展这些圆的边界，直到屏幕上所有像素点都涂上颜色为止，环绕Pi的新边界构成Power图．该算法改进了在Voronoi图基础上构造Power图的传统方法，具有较高的效率．     

基于Voronoi图的有障碍物空间聚类

Voronoi图具有侧向临近特性，可以方便表达空间临近关系。根据这一性质，解决在空间数据聚类分析中的有实体障碍物所面临的问题。通过生成考虑实体障碍物的Voronoi图，建立Voronol图的距离度量方法，提出采用循障碍物求距离法，可以方便地完成有障碍物的空间聚类分析。该方法使得有实体障碍物情况下空间聚类更加准确，并通过实验进行验证。     

关于一般图形Voronoi图的离散构造法的研究

生成元为任意图形的一般图形Vomnoi图，由于其生成元的任意性，使得构造一般图形Voronoi图的算法均比较复杂。本文给出了在生成元边界上选取母点，利用点为生成元的Voronoi图的离散画法进行构造，从而得到一般图形Voronoi图的离散构造法。与其它算法相比，该算法的实现与生成元的形状无关，无需复杂计算，无需考虑误差控制，因而更加实用，效率也更高。实验结果表明，该算法简单，具有较高的理论价值和应用价值。     

特征保持的马赛克图像生成方法

马赛克图像是一种非真实感的渲染效果,主要通过组合不同形状、颜色的嵌片合成目标图像.基于测地距离度量下的Voronoi图结构,提出一种保特征的自适应马赛克图像生成方法.首先利用特征算子自动提取出源图像中的特征线,并根据这些特征线定义测地度量,从而保证在测地度量下生成的Voronoi图的边和图像特征边重合;然后通过距离变换计算每个像素到图像特征线的最近距离,并利用该距离场定义马赛克图像的密度函数;最后结合重心Voronoi图理论,采用Lloyd迭代算法优化嵌片的形状,得到最终的马赛克图像.实验结果表明,该方法得到的马赛克效果图有效地保持了源图像特征,疏密程度自适应、连续过渡,嵌片形状规则、排列整齐.     

基于MapReduce的加权Voronoi图并行算法设计及应用

针对大规模数据的加权Voronoi图实现的复杂性和计算精度低问题, 采用欧氏距离法, 设计和实现了一种基于MapReduce编程模型的并行栅格加权Voronoi图的生成算法, 并将其成功应用于石家庄桥东区超市的推荐服务。该算法计算精度高, 同时可适用于任意点、线、面及复合发生元的加权Voronoi图的计算。实验结果表明, 算法在处理大规模栅格数据时能明显提高栅格Voronoi图的生成速度, 并能为用户推荐综合因素优选的超市。     

A parallel algorithm for constructing Voronoi diagrams based on point‐set adaptive grouping

This paper presents a parallel algorithm for constructing Voronoi diagrams based on point‐set adaptive grouping. The binary tree splitting method is used to adaptively group the point set in the plane and construct sub‐Voronoi diagrams for each group. Given that the construction of Voronoi diagrams in each group consumes the majority of time and that construction within one group does not affect that in other groups, the use of a parallel algorithm is suitable. After constructing the sub‐Voronoi diagrams, we extracted the boundary points of the four sides of each sub‐group and used to construct boundary site Voronoi diagrams. Finally, the sub‐Voronoi diagrams containing each boundary point are merged with the corresponding boundary site Voronoi diagrams. This produces the desired Voronoi diagram. Experiments demonstrate the efficiency of this parallel algorithm, and its time complexity is calculated as a function of the size of the point set, the number of processors, the average number of points in each block, and the number of boundary points. Copyright © 2013 John Wiley & Sons, Ltd.     

On 2-Site Voronoi Diagrams Under Geometric Distance Functions

We revisit a new type of Voronoi diagram, in which distance is measured from a point to a pair of points. We consider a few more such distance functions, based on geometric primitives, namely, circles and triangles, and analyze the structure and complexity of the nearest- and furthest-neighbor 2-site Voronoi diagrams of a point set in the plane with respect to these distance functions. In addition, we bring to notice that 2-point site Voronoi diagrams can be alternatively interpreted as 1-site Voronoi diagrams of segments, and thus, our results also enhance the knowledge on the latter.     

基于动态创建局部Voronoi图的连续近邻查询

在充分认识到k阶Voronoi图在解决连续k个近邻查询优越性和现实不可行性的基础上,用分支限界的思想去界定预创建Voronoi图生成点范围的上界,提出了一种动态地创建局部Voronoi图的办法解决连续近邻查询问题。该方法只是在给定查询段上所有点的k个近邻范围上界内创建一个局部的k阶Voronoi图,这样大大降低了基于Voronoi图的连续k近邻查询的代价。     

移动点Voronoi图拓扑维护策略的研究

移动环境下基于Voronoi图的最近邻查询必须要解决随时间不断改变的移动点Voronoi图的拓扑结构的维护问题。通过一组离散的,有限的事件序列对其对偶图Delaunay图拓扑改变过程的模拟来实现对移动点Voronoi图拓扑结构的维护。把带有事件驱动机制的移动数据结构(Kinetic Data Structure,KDS)模型作为移动点的运动模型,给出了KDS模型对其对偶图Delaunay图拓扑结构改变维护的具体策略,并对移动环境下动态插入或删除移动点时Voronoi图的拓扑维护问题进行了研究。最后给出了移动环境下基于Voronoi图的近邻查询的数据库实现模型。     

Fast Voronoi modeling

The common way to construct Voronoi tessellations is to compare the distances between given reference points using a given distance function. To generalize this distance-function concept we expand an existing approach which defines distance functions by their ``unit circles'. Our new approach allows modeling the ``unit circles' by a closed Spline curve. Changing the control polygon directly affects the tessellation's appearance. Typically generalized Voronoi diagrams are represented by Voronoi vertices and curves separating the individual tiles. To obtain interactive modeling we extended an existing hardware accelerated rendering approach computing a bitmap-representation using different colors for individual tiles. With our extension, we are able to use our Spline distance representations as input for a growing process. This growing process easily takes into account weighting approaches like multiplicative, additive, and even free functional weighting.     

连续近邻查询方法的研究

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