共查询到18条相似文献,搜索用时 93 毫秒
1.
2.
空间数据库中约束K最接近对查询 总被引:1,自引:0,他引:1
定义了满足空间约束的K最接近对查询,该查询检索两个数据集在给定约束区域中的K最接近对。在空间数据库中,对采用R树类型索引存储的数据集给出了三个查询处理算法。其中两阶段的RJ和JR算法采用了变换范围查询和最接近对查询执行顺序的策略。单阶段基于堆的SPH算法采用了最好优先的策略,并利用给出的裁减规则、更新规则和访问顺序规则来提高查询处理效率。实验表明SPH具有较好的适用性和性能。 相似文献
3.
最近点对问题是空中交通控制系统中的一个重要问题,并且在许多领域都有应用,也是计算几何学研究的基本问题之一.利用分治法解决该问题的线性和平面情况,算法可以在O(n*logn)时间内完成.本文在此基础上,进一步实现空间最接近点的算法,并对算法的复杂性进行分析. 相似文献
4.
平面散乱点三角剖分分治算法的实现 总被引:2,自引:0,他引:2
平面散乱点三角剖分在实践中有广泛应用。文中在分析已有算法的基础上,提出利用分治算法实现平面散乱点三角剖分。给出了算法实现流程并讨论了算法实现过程中几个重要问题。最终给出了实验结果。文中的研究对开展此类工作有借鉴和指导作用。 相似文献
5.
平面散乱点三角剖分分治算法的实现 总被引:2,自引:0,他引:2
平面散乱点三角剖分在实践中有广泛应用。文中在分析已有算法的基础上,提出利用分治算法实现平面散乱点三角剖分。给出了算法实现流程并讨论了算法实现过程中几个重要问题。最终给出了实验结果。文中的研究对开展此类工作有借鉴和指导作用。 相似文献
6.
求平面点集最近点对的一个改进算法 总被引:3,自引:0,他引:3
文中对Preparata和Shamos在1985年提出的求平面点集最近点对的一个分治算法进行了改进,使原来 归并时最多需计处3n对点对的距离,改进的为最多只需计算2n 相似文献
7.
平面域上离散点的三角化实现 总被引:3,自引:0,他引:3
简单回顾了生成Delaunay三角网的分治算法,逐点插入法,三角网生长法等三类主流算法,提出了一种基于逐点插入思想的快速,有效的分区逐点插入三角化算法,实现了平面域上离散数据点的三角化,网络的优化是在网格生成过程中完成的,生成的网格符合Delaunay准。 相似文献
8.
本文为构建离散点的凸包提出了一种改进的分治算法,它在查找每一个凸包顶点的同时,通过去除若干非凸包顶点来迅速减小问题的规模。本文对该算法的正确性给出了严格的证明。 相似文献
9.
10.
本文叙述作者新近发现的平面点集二阶Voronoi图的一些性质,并依据这些性质设计了构造二阶Voronoi图的一种算法,算法的时间复杂性为O(nlogn),优于J-D Boissonna t和M Yvinec所著Algorithmic Geometry一书中提出的算法。 相似文献
11.
As early as in 1975, Shamos and Hoey first gave an O(n lg n)-time divide-and-conquer algorithm (Stt algorithm in short) for the problem of finding the closest pair of points. In one process of combination, the Euclidean distances between 3n pairs of points need to be computed, so the overall complexity of computing distance is then 3n lgn. Since the computation of distance is more costly compared with other basic operation, how to improve SH algorithm from the aspect of complexity of computing distance is considered. In 1998, Zhou, Xiong and Zhu improved SH algorithm by reducing this complexity to 2n lg n. In this paper, we make further improvement. The overall complexity of computing distances is reduced to (3n lg n)/2, which is only half that of SH algorithm. 相似文献
12.
We improve the famous divide-and-conquer algorithm by Bentley and Shamos for the planar closest-pair problem. For n points on the plane, our algorithm keeps the optimal O(n log n) time complexity and, using a circle-packing property, computes at most 7n/2 Euclidean distances, which improves Ge et al.'s bound of (3n log n)/2 Euclidean distances. We present experimental results of our comparative studies on four different versions of the divide-and-conquer closest pair algorithm and propose two effective heuristics. 相似文献
13.
用遗传算法解决点状要素的自动注记问题 总被引:1,自引:0,他引:1
文章针对点状要素的自动注记问题,提出了一种改进的自适应遗传算法,并详细地分析了它的实现方法和步骤。通过实验求解表明,该方法是解决点状要素自动注记问题的有效方法,很好地解决了点注记的冲突、压盖和位置优先级问题。 相似文献
14.
平面线段集三角剖分的算法 总被引:2,自引:0,他引:2
周培德 《计算机工程与科学》2003,25(1):20-22
本文提出了计算平面线段集三角剖分的两种算法,第一个算法是利用平面扫描的思想,当扫描线达到事件点时,处理事件点,即将事件点与已被扫描的某些点连接,这样便将已扫描的区域三角剖分,当扫描线达到最左边的事件点时,处理该事件点,就完成了平面线段集的三角剖分,第二个算法基于逐层计算凸壳,并将凸壳改变为多边形,这样便便形成嵌套的多边形层,这些多边形覆盖线段集凸壳内的区域,然后三角剖分每个多边形,即完成平面线段集的三角剖分,两个算法的时间复杂性分别为O(nlogn),O(mnlogn),其中n为线段集中线估的数目,m为凸壳的层数。 相似文献
15.
16.
17.
18.
为了选择一种更适合数字高程模型匹配的算法,首先回顾了目前广泛使用的两种3维表面匹配算法--最小高差算法和最近点迭代算法的发展,并给出了二者共同的逻辑框架;然后从理论上对二者的差异进行了定性分析;最后通过试验进行了定量比较.试验结果表明:与ICP算法相比,LZD算法的计算效率高于前者约9倍.但其拉入范围略小,迭代速度也比ICP算法慢了约一倍,然而,如果表面姿态差异越小,则LZD算法迭代收敛就越快.因此,对于表面姿态差异较小的DEM匹配而言,LZD算法更加适合. 相似文献