基于Delaunay三角剖分生成Voronoi图算法

针对Delaunay三角网生长算法和间接生成Voronoi图算法构网效率不高的问题,提出了一种Delaunay三角网生长法间接生成Voronoi图的改进算法。该算法以点集凸壳上一边快速生成种子三角形,定义了半封闭边界点的概念,在三角形扩展过程中动态删除封闭点及半封闭边界点,加快Delaunay三角网生成速度。然后又定义了有序目标三角形的概念,该算法能迅速查找点的有序目标三角形,生成无射线的Voronoi图;考虑凸壳上点的特性,借助三个无穷点生成带射线的Voronoi图。通过实验结果分析表明,改进的算法执行效率有了很大提高。     

三维点集Voronoi图的算法实现

对现有三维点集Voronoi图的生成算法进行深入研究,提出并实现由Delaunay三角剖分构建Voronoi图的算法．首先采用随机增量局部转换计算Delaunay三角剖分,然后再根据对偶特性构建Voronoi图．该算法健壮性很高,适用于处理各种非完全共面三维点集．     

一种改进的MC算法

为了对等值面与子等值面进行提取和分组,在MC算法原理的基础上,提出了一种改进的等值面提取与子等值面分组算法。该算法首先将数据场分解为点、棱边、面与体元的拓扑结构;然后在整个数据场范围内求所有棱边与等值面的交点,并在面内连接交点形成面与等值面的交线,交线在体元内连接生成空间多边形;接着通过三角化各个体元内的空间多边形得到由顶点表与三角形表组成的等值面数据;最后根据三角形在顶点处的连接关系,采用种子算法对属于同一子等值面的三角形与顶点进行标记,属于同一子等值面的顶点与三角形将被存放在独立的顶点表与三角形表中。实验结果表明,该算法可以高效地实现等值面提取与子等值面的分组。     

MapReduce模型下Voronoi图栅格生成算法

针对"海量"点组成的平面点集Voronoi图栅格生成算法的效率问题,对其进行易并行性抽象,提出了一种MapReduce模型下基于欧氏距离的Voronoi图栅格生成算法,该算法采用三个MapReduce Job来实现。在第一个MapReduce Job中,将栅格按照隶属代码进行归属分类。在第二个MapReduce Job中,将新数据按照其对应的行号进行归类。在第三个MapReduce Job中,并行生成全局有序的Voronoi图部分文件,并连接各个部分文件,生成最终的Voronoi图。在多个不同大小数据集上的实验结果表明,这种MapReduce模型下的算法部署在Hadoop集群上运行具有较好的加速比和扩展性。     

基于边界点偏置的VORONOI骨架算法的研究

利用Voronoi图求解中轴骨架的方法往往首先将边界用多边形来表示，文中提出将边界点进行偏置，在偏置过程中得到Voronoi图，并得到中轴骨架的算法。这种算法无须对边界进行直线拟合，简单明了，易于实现，适用于任意和任意连通性的二值图像。     

平面上可相交凸多边形的Voronoi图

传统的多边形的Voronoi图存在不能相交的问题,以至于无法将其应用于计算机视觉、生态学等领域中的多边形相交情况.为了解决多边形相交情况下的最邻近空间划分问题,提出了可相交凸多边形的Voronoi图.首先定义可相交凸多边形的Voronoi图;然后阐述相交多边形特有的Voronoi边的区域化现象,证明了其发生的充要条件,进一步揭示了相交多边形与不相交多边形之间的关系;最后提出Voronoi图的生成算法,并用代码实现.实验结果表明,该算法能够有效地解决多边形相交的问题,突破了不能相交的限制,为计算机视觉、生态学等领域的实际应用提供了理论基础.     

基于平面点集的Voroni图的近似构造

现有的平面上点的Voronoi图的构造方法一般很难扩展到一般平面图形的Voronoi图的构造上。以平面点集中的每个点作为生长核,以相同的速率向外扩张,直到彼此相遇为止而在平面上形成的图形即为平面点集的近似的Voronoi图。在VC 6.0的环境下实现了该算法,并将其与分治法所得的结果进行了比较。该算法直观、计算简单,通用性好。对于一般的平面图形,选取有代表性的边界点,再按照平面点集中Voronoi图的近似构造方法,就可以得到一般平面图形的近似的Voronoi图。     

Hadoop下面元加权Voronoi图并行算法及应用

面元加权Voronoi图是生成元为面元的加权Voronoi图。针对大规模数据情况下面元加权Voronoi图存在的计算效率不高问题,结合面元边界点提取方法,提出一种基于Hadoop云平台的面元加权Voronoi图的并行生成算法,进行了单机和集群实验。实验结果表明,算法能有效处理大规模栅格数据,明显提高面元加权Voronoi图的生成速度。还可应用于城市绿地设计规划,为绿地设计提供决策依据。     

近似线性平均复杂性的平面点集Voronoi图增量算法的设计与实现

1 引言 Voronoi图是计算几何学科的一个重要结构,在模式识别、计算机图形、计算机辅助设计等领域有广泛的应用。平面点集Voronoi图的常用构造算法有三类:分治法、平面扫描法和增量算法。由于增量算法不仅适用于静态点集,而且还适用于动态点集,因而受到重视。 Voronoi图增量算法中的关键工作是最近邻的选择和搜索。已有算法大都采用随机穷举法,因而效率较低。本文首先介绍了Voronoi图的翼边数据结构表示方法,在增量算法时间复杂性分析的基础上,提出了应用桶技术选择生成子并提     

Voronoi图的生成及近邻关系查询方法

针对构建Voronoi图的方法的生成效率较低,构建复杂度较高的问题,提出了利用多方法交叉融合进行Voronoi图的构建与更新的方法。为了提高空间数据最近邻查询的效率,提出了基于Voronoi图和Voronoi多边形最小内切圆的最近邻查询方法;针对查询点位置频繁变化的情况,提出了基于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.     

Optimal parallel algorithms for point-set and polygon problems

In this paper we give parallel algorithms for a number of problems defined on point sets and polygons. All our algorithms have optimalT(n) * P(n) products, whereT(n) is the time complexity andP(n) is the number of processors used, and are for the EREW PRAM or CREW PRAM models. Our algorithms provide parallel analogues to well-known phenomena from sequential computational geometry, such as the fact that problems for polygons can oftentimes be solved more efficiently than point-set problems, and that nearest-neighbor problems can be solved without explicitly constructing a Voronoi diagram.     

一种基于逐点插入Delaunay三角剖分生成Voronoi图的算法

采用改进的逐点插入算法生成Voronoi图。该算法在逐点插入的过程中生成凸壳,进而生成Delaunay三角剖分。在生成Voronoi图的实现过程中,通过遍历三角形的边顶点快速识别相关的三角形组,进而生成Voronoi图。试验结果表明,该算法能实现,成功生成Voronoi图。     

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

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

An algorithm for point cluster generalization based on the Voronoi diagram

This paper presents an algorithm for point cluster generalization. Four types of information, i.e. statistical, thematic, topological, and metric information are considered, and measures are selected to describe corresponding types of information quantitatively in the algorithm, i.e. the number of points for statistical information, the importance value for thematic information, the Voronoi neighbors for topological information, and the distribution range and relative local density for metric information. Based on these measures, an algorithm for point cluster generalization is developed. Firstly, point clusters are triangulated and a border polygon of the point clusters is obtained. By the border polygon, some pseudo points are added to the original point clusters to form a new point set and a range polygon that encloses all original points is constructed. Secondly, the Voronoi polygons of the new point set are computed in order to obtain the so-called relative local density of each point. Further, the selection probability of each point is computed using its relative local density and importance value, and then mark those will-be-deleted points as ‘deleted’ according to their selection probabilities and Voronoi neighboring relations. Thirdly, if the number of retained points does not satisfy that computed by the Radical Law, physically delete the points marked as ‘deleted’ forming a new point set, and the second step is repeated; else physically deleted pseudo points and the points marked as ‘deleted’, and the generalized point clusters are achieved. Owing to the use of the Voronoi diagram the algorithm is parameter free and fully automatic. As our experiments show, it can be used in the generalization of point features arranged in clusters such as thematic dot maps and control points on cartographic maps.     

Optimal parallel algorithms for point-set and polygon problems

In this paper we give parallel algorithms for a number of problems defined on point sets and polygons. All our algorithms have optimalT(n) * P(n) products, whereT(n) is the time complexity andP(n) is the number of processors used, and are for the EREW PRAM or CREW PRAM models. Our algorithms provide parallel analogues to well-known phenomena from sequential computational geometry, such as the fact that problems for polygons can oftentimes be solved more efficiently than point-set problems, and that nearest-neighbor problems can be solved without explicitly constructing a Voronoi diagram.The research of R. Cole was supported in part by NSF Grants CCR-8702271, CCR-8902221, and CCR-8906949, by ONR Grant N00014-85-K-0046, and by a John Simon Guggenheim Memorial Foundation fellowship. M. T. Goodrich's research was supported by the National Science Foundation under Grant CCR-8810568 and by the National Science Foundation and DARPA under Grant CCR-8908092.     

Voronoi diagrams with barriers and on polyhedra for minimal path planning

Two generalizations of the Voronoi diagram in two dimensions (E²) are presented in this paper. The first allows impenetrable barriers that the shortest path must go around. The barriers are straight line segments that may be combined into polygons and even mazes. Each region of the diagram delimits a set of points that have not only the same closest existing point, but have the same topology of shortest path. The edges of this diagram, which has linear complexity in the number of input points and barrier lines, may be hyperbolic sections as well as straight lines. The second construction considers the Voronoi diagram on the surface of a convex polyhedron, given a set of fixed source points on it. Each face is partitioned into regions, such that the shortest path to any goal point in a given region from the closest fixed source point travels over the same sequence of faces to the same closest point.     

改进的限定Voronoi图梯形检测带细分算法

针对已有的限定Voronoi图生成算法在一些复杂约束条件下不能收敛的问题,通过引入控制因子,给出一种 改进的限定Voronoi图梯形检测带细分算法。在计算初始Voronoi生长元的过程中,引入外部和内部限定线段端点 保护圆半径控制因子,控制限定线段两端点附近的Voronoi边的尺寸;在细分梯形检测带的过程中,引入外部和内部 限定线段尺寸控制因子,控制位于限定线段上的Voronoi边的尺寸。实验结果表明,本算法对于内部边界约束、线束 约束条件以及不规则区域均可以得到质量较好、满足约束条件的限定Voronoi图。