共查询到19条相似文献,搜索用时 93 毫秒
1.
通过对空间点群的自适应聚类方法构建层次Voronoi图,以此层次Voronoi图为切入点,计算点群的拓扑、密度和范围的相似度,结合有关标准差的数理统计方法,计算角度、距离的相似度。在各维度的相似度基础上,使用其几何平均值作为点群整体相似度的度量标准,优化点群相似度的计算方法,并通过实验证明算法的可行性 相似文献
2.
3.
4.
5.
对现有三维点集Voronoi图的生成算法进行深入研究,提出并实现由Delaunay三角剖分构建Voronoi图的算法.首先采用随机增量局部转换计算Delaunay三角剖分,然后再根据对偶特性构建Voronoi图.该算法健壮性很高,适用于处理各种非完全共面三维点集. 相似文献
6.
基于C++的Voronoi图数据结构的设计与构造算法研究 总被引:3,自引:0,他引:3
通过对Voronoi图的定义和组成的分析,对其主要构成几何元封装成相应的C 类,用逐点插入算法实现其构造. 针对算法中若干具体细节提出了许多新颖的处理方法,如循环查找待处理单元算法和插入剔除算法等,并给出退化情况的处理. 相似文献
7.
8.
本文叙述作者新近发现的平面点集二阶Voronoi图的一些性质,并依据这些性质设计了构造二阶Voronoi图的一种算法,算法的时间复杂性为O(nlogn),优于J-D Boissonna t和M Yvinec所著Algorithmic Geometry一书中提出的算法。 相似文献
9.
10.
近似线性平均复杂性的平面点集Voronoi图增量算法的设计与实现 总被引:1,自引:0,他引:1
1 引言 Voronoi图是计算几何学科的一个重要结构,在模式识别、计算机图形、计算机辅助设计等领域有广泛的应用。平面点集Voronoi图的常用构造算法有三类:分治法、平面扫描法和增量算法。由于增量算法不仅适用于静态点集,而且还适用于动态点集,因而受到重视。 Voronoi图增量算法中的关键工作是最近邻的选择和搜索。已有算法大都采用随机穷举法,因而效率较低。本文首先介绍了Voronoi图的翼边数据结构表示方法,在增量算法时间复杂性分析的基础上,提出了应用桶技术选择生成子并提 相似文献
11.
基于Voronoi图的组最近邻查询 总被引:1,自引:0,他引:1
组最近邻查询由于涉及多个查询点,因此比传统的最近邻查询更为复杂.充分考虑查询点的分布特征以及它们构成的几何图形的性质和特点,给出组最近邻所应满足的条件及判断组最近邻的理论方法.提出基于Voronoi图的组最近邻查询的VGNN算法,可以精确求解查询点集的最近邻.对于查询点不共线的情况,该算法的查询方式是以一点为中心、向外扩张式的;对于查询点共线的情况,该算法给出搜索范围,限定了参与计算的数据点的个数.给出基于Voronoi图的VTree索引.实验结果表明,基于VTree索引的VGNN算法具有较好的性能,并且当查询点不共线时,其性能具有较高的稳定性. 相似文献
12.
采用改进的逐点插入算法生成Voronoi图。该算法在逐点插入的过程中生成凸壳,进而生成Delaunay三角剖分。在生成Voronoi图的实现过程中,通过遍历三角形的边顶点快速识别相关的三角形组,进而生成Voronoi图。试验结果表明,该算法能实现,成功生成Voronoi图。 相似文献
13.
论文提出一种基于点集自适应分组构建Voronoi 图的并行算法,其基本思
路是采用二叉树分裂的方法将平面点集进行自适应分组,将各分组内的点集独立生成
Voronoi 图,称为Voronoi 子图;提取所有分组内位于四边的边界点,对边界点集构建Voronoi
图,称为边界点Voronoi 图;最后,针对每个边界点,提取其位于Voronoi 子图和边界点Voronoi
图内所对应的两个多边形,进行Voronoi 多边形的合并,最终实现子网的合并。考虑到算法
耗时主要在分组点集的Voronoi 图生成,而各分组的算法实现不受其他分组影响,采用并行
计算技术加速分组点集的Voronoi 图生成。理论分析和测试表明,该算法是一个效率较高的
Voronoi 图生成并行算法。 相似文献
14.
15.
16.
结合 3种点群目标选取的一般原则和遗传算法的基本原理与特点 ,设计了基于遗传算法的点群目标选取模型 .考虑到要最大限度地保持点群的分布范围、排列规律、内部各地段的分布密度等因素 ,基于遗传算法的点群选取模型的基本原理是 :首先采用自适应分类方法 ,将点群 M依照密度分成若干类子点群 ,然后根据每个子点群的点数和最后要保留的总的点数 ,计算每个子点群中要保留的点数 ,最后结合凸壳化简方法和遗传算法对点进行选择 .在对关键性步骤进行讨论的基础上 ,本文针对某一地区的点群目标分别采用基于遗传算法的点目标选取方法与凸壳选取方法进行了选取对比实验 .从实验结果和遗传算法的特点分析可以看出 ,基于遗传算法的点目标选取方法的特点是非常明显的 ,其适用于分散式居民地记号房、可看作点状目标的小湖泊群等点状要素的选取 ;能够保持密度分布特征及其排列规律 ;外围轮廓特点没有大的改变 相似文献
17.
基于边界点偏置的VORONOI骨架算法的研究 总被引:2,自引:0,他引:2
利用Voronoi图求解中轴骨架的方法往往首先将边界用多边形来表示,文中提出将边界点进行偏置,在偏置过程中得到Voronoi图,并得到中轴骨架的算法。这种算法无须对边界进行直线拟合,简单明了,易于实现,适用于任意和任意连通性的二值图像。 相似文献
18.
Abstract. We present an optimal parallel randomized algorithm for the Voronoi diagram of a set of n nonintersecting (except possibly at endpoints) line segments in the plane. Our algorithm runs in O(log n) time with high probability using O(n) processors on a CRCW PRAM. This algorithm is optimal in terms of work done since the sequential time bound for this problem
is Ω(n log n) . Our algorithm improves by an O(log n) factor the previously best known deterministic parallel algorithm, given by Goodrich, ó'Dúnlaing, and Yap, which runs in
O( log
2
n) time using O(n) processors. We obtain this result by using a new ``two-stage' random sampling technique. By choosing large samples in the
first stage of the algorithm, we avoid the hurdle of problem-size ``blow-up' that is typical in recursive parallel geometric
algorithms. We combine the two-stage sampling technique with efficient search and merge procedures to obtain an optimal algorithm.
This technique gives an alternative optimal algorithm for the Voronoi diagram of points as well (all other optimal parallel
algorithms for this problem use the transformation to three-dimensional half-space intersection). 相似文献
19.
We present a randomized algorithm for computing the Voronoi diagram of line segments using coarse-grained parallel machines.
Operating on P processors, for any input of n line segments, this algorithm performs O((n log n)/P) local operations per processor, O(n/P) messages per processor, and O(1) communication phases, with high probability for n=Ω(P
3+ε
) .
Received June 1, 1997; revised March 10, 1998. 相似文献