标签: kdtree

我有一组多边形区域(地理围栏).这组数据是固定的; 所以不需要插入和删除数据.哪个数据结构可用于搜索查询点(经度,纬度)所在的区域？

注意:我已经成功地为一组点实现了KD-Tree(实际上是一个2D树).但它不适用于这个问题.我已经实现了一个R-Tree; 它解决了问题,但它很慢(或我的实施很糟糕).

谢谢

注意:我从事过R-Tree实现,现在工作正常.

前几天,我正在读关于kd-trees的事.我一直在寻找一个具体而简单的情况,这种数据结构可能很有用.有没有人有这样的例子？

Scipy(http://www.scipy.org/)提供两个KD Tree类; KDTree和cKDTree.

cKDTree要快得多,但是比KDTree更少可定制和查询(据我从文档中可以看出).

这是我的问题: 我有一个3百万二维(X,Y)点的列表.我需要从每个点返回X单位距离内的所有点.

使用KDtree,有一个选项可以做到这一点:KDtree.query_ball_tree()它生成一个列表,其中包含每个其他点的X个单位内的所有点.但是:这个列表很庞大,很快就会填满我的虚拟内存(大约7.44亿个项目).

潜在的解决方案#1:有没有办法在写入时将此列表解析为文本文件？

潜在的解决方案#2:我尝试使用for循环(对于列表中的每个点),然后通过使用:找到X单位内的单点邻居KDtree.query_ball_point().但是:这需要永远,因为它需要运行数百万次查询.是否有与此KDTree工具相当的cKDTree？

潜在的解决方案#3:打败我,其他人有什么想法？

这是我对它的理解:1.向下递取树,根据ELEMENT是否位于左侧或右侧子树(如果存在)中取左或右子树.2.将CURRENT_BEST设置为您到达的第一个叶节点.3.当您重新计算时,检查ELEMENT是否靠近分裂超平面而不是CURRENT_BEST.如果是这样,请将CURRENT_BEST设置为当前节点.

这是我从维基百科和我的班级得到的部分,以及我不理解的部分:4.检查3中分裂点的另一个子树中的任何节点是否比分裂点更接近ELEMENT .

我不明白为什么我们需要做4.因为任何可能位于分裂节点的一个子树中的点必须更接近分裂节点而不是其他子树中的任何点.

很明显,我对算法的理解是有缺陷的,所以非常感谢帮助.

我有大型2D阵列,带有未分类(X,Y)点,我需要知道哪些点彼此非常接近(最近邻查找).我已经使用cKDTree和query_ball_tree成功获得了大约500,000(X,Y)点的数组.但是,当我为超过1,000,000个点的数据集尝试相同的算法时,query_ball_tree会导致MemoryError.

我使用64位Windows和16Gb内部存储器,并尝试了32位和64位版本的Python和扩展模块(scipy和numpy).

def Construct_SearchTree(AllXyPoints):
    KDsearch = cKDTree(AllXyPoints)  
    return KDsearch.query_ball_tree(KDsearch, Maxdist)

我的问题:

1)有没有人知道cKDTree/query_ball_tree的替代品消耗更少的内存？在这种情况下,内存使用速度不太重要.

2)我希望从32位切换到64位python和扩展可以解决MemoryError问题.可能是什么原因呢？

感谢您的帮助和建议.

在MATLAB中,有没有办法更新KDTreeSearcher中的数据点？

我从一个带有所有N个数据点(也就是观察点)的树开始,并且在选择一个点之后迭代地从树中搜索一个点,我需要使该点无效直到后一阶段.

使用所有数据(如createns)构建树的能力以及将标记点标记为有效/无效或启用/禁用的能力就足够了.

当所有点无效时,过程结束时,将有大量删除(失效)和更少的添加(重新验证).

我见过关于scikit-learn kd-tree的类似问题,但它没有答案.

这个问题涉及KDTrees的KNN搜索的实现。遍历KDTree来找到单个最佳匹配（最近邻居）很简单，类似于修改后的二进制搜索。

如何修改遍历以详尽有效地找到k个最佳匹配（KNN）？

编辑以澄清问题：找到最接近输入查询I的节点M之后，遍历算法如何继续查找剩余的K-1最接近查询的匹配项？是否有一个遍历模式可以确保以与查询最佳或最差的顺序访问节点？

我已经研究了很长一段时间,并坚持这个错误.

我们在F#中为学校项目建立了一个光线跟踪器.(链接解释Ray tracer:https://blog.frogslayer.com/kd-trees-for-faster-ray-tracing-with-triangles/)

我们为三角形,边界框创建了一个命中函数,一个KD树来处理具有数千个三角形的图形,例如Stanford Bunny和KD树的遍历算法.

我们已经调试了KD树的创建,确保为浮点添加epsilon值,并检查边界框之间的重复项是否被删除.我们确信我们正确地分割了场景中的形状列表,但是我们在尝试渲染的图中得到了"洞".

这是我们的KD树实现,我附上了这些洞的图片:

斯坦福兔子

螺旋

module TmKdtree

open Point
open Shapes

type BoundingBox = BasicShape.BoundingBox 
type Shape = BasicShape.Shape

type TmKdtree =
    | Leaf of BasicShape.Triangle list * BoundingBox 
    | Node of BasicShape.Triangle list * TmKdtree * TmKdtree * BoundingBox  * (string*Point)

let epsilon = 0.001

//Making a boundingbox for the KD-tree, by finding max H point in the boundingboxlist and min l point in the boundingbox list. 
let mkKdBbox (shapes : …

我已经基于“ 关于建立用于射线跟踪的快速kd树”的论文，以及 Wald和Havran 在O（N log N）中进行的研究，实现了SAH kd树。请注意，最后我还没有完成他们的拼接和合并建议，只是为了加快树的构建速度，只是SAH部分。

我正在使用轴对齐的多维数据集测试该算法，其中每个面都分成两个三角形，所以我N = 12总共有三角形。左下角的顶点（即最靠近轴的顶点）实际上位于原点。

Face    Triangle
----------------
Front:  0, 1
Left:   6, 7
Right:  2, 3
Top:    4, 5
Bottom: 10, 11
Back:   8, 9

假设节点遍历成本Ct = 1.0和交叉成本Ci = 10.0。我们首先发现不分裂的成本为Cns = N * Ci = 12 * 10.0 = 120.0。

现在，我们依次遍历每个轴，并逐步遍历候选拆分平面，以查看拆分成本是否更便宜。第一个分割平面是p = <x,0>。我们有Nl = 0，Np = 2而且Nr = 10（也就是三角形的上左边的数字，在飞机上，并以平面的右侧）。平面中的两个三角形分别是数字6和7（左侧）。其他所有人都在右边。

SAH(p,V,Nl,Nr,Np)现在执行该功能。这需要分割平面，V要分割的体素以及左/右/平面三角形的数量。它计算出命中左（平坦）体素Pl = …

我正在使用基于点云库（PCL）的kd-树最近邻居（NN）搜索的C ++实现。该数据集包含约220万个点。我正在为每一个其他点搜索NN点。搜索半径设置为2.0。要完全计算，大约需要12个小时！我正在使用具有4GB RAM的Windows 64位计算机。kd树搜索是否很常见？我想知道是否还有用于3D点云数据的其他c ++库，它更快。我听说过ANN C ++库和CGAL，但不确定这些速度有多快。