问题标签 [kdtree]

我正在寻找 Java 中的 KDTree 实现。
我做了一个谷歌搜索，结果似乎很随意。实际上有很多结果，但它们大多只是一次性的实现，我宁愿找到更多“生产价值”的东西。诸如 apache 集合或 .NET 的优秀 C5 集合库之类的东西。我可以看到公共错误跟踪器并检查最后一次 SVN 提交发生的时间。此外，在理想情况下，我会为空间数据结构找到一个精心设计的 API，而 KDTree 只是该库中的一个类。

对于这个项目，我只会在 2 维或 3 维中工作，而且我主要只是对一个好的最近邻实现感兴趣。

当只需要功能时，我正在尝试决定使用哪种数据结构来存储键值对

• 插入
• 抬头

具体来说，我不需要能够删除对或遍历键/值/对。

键是整数元组，值是指针（引用等）。我只存储了几百万对，分布在（许多）对象上。

目前我正在考虑使用

• 哈希表
• kd树
• b树

我倾向于哈希表（对于O(1)插入/查找时间），但我想确认我的倾向。

您会推荐哪种结构（上述结构或其他结构），为什么？如果您推荐一个哈希表，我应该为每个对象创建一个单独的表，还是只创建一个表并将对象的 id 作为键元组的一部分？

在 kd 树的wikipedia 条目中，提出了一种算法，用于在 kd 树上进行最近邻搜索。我不明白的是步骤3.2的解释。仅仅因为搜索点的分裂坐标与当前节点的差值大于搜索点的分裂坐标与当前最佳点的差值，你怎么知道没有更近的点呢？

最近邻搜索 使用二维 KD 树进行 NN 搜索的动画

最近邻（NN）算法旨在找到树中最接近给定输入点的点。这种搜索可以通过使用树属性快速消除大部分搜索空间来有效地完成。在 kd-tree 中搜索最近邻的过程如下：

1. 从根节点开始，算法递归地向下移动树，与插入搜索点的方式相同（即它向右或向左移动取决于该点是否大于或小于当前节点。分割维度）。
2. 一旦算法到达叶节点，它将该节点点保存为“当前最佳”
3. 该算法展开树的递归，在每个节点执行以下步骤： 1. 如果当前节点比当前最佳节点更接近，则它成为当前最佳节点。2. 算法检查分割平面的另一侧是否有任何点比当前最佳点更靠近搜索点。从概念上讲，这是通过将分割超平面与搜索点周围的超球面相交来完成的，该超球面的半径等于当前最近的距离。由于超平面都是轴对齐的，因此这是一个简单的比较，以查看搜索点和当前节点的分割坐标之间的差异是否小于搜索点到当前最佳点的距离（整体坐标）。1. 如果超球面穿过平面，则平面的另一侧可能有更近的点，因此算法必须从当前节点向下移动树的另一个分支以寻找更近的点，遵循与整个搜索相同的递归过程. 2. 如果超球面不与分裂平面相交，则算法继续向上走，并且该节点另一侧的整个分支被消除。
4. 当算法完成对根节点的这个过程时，搜索就完成了。

通常，该算法使用平方距离进行比较以避免计算平方根。此外，它可以通过将平方当前最佳距离保存在变量中进行比较来节省计算量。

我必须在 kd-tree 中实现 k 个最近邻搜索 10 维数据。

但问题是我的算法对于 k=1 非常快，但对于 k>1 (k=2,5,10,20,100) 慢 2000 倍

这对 kd 树来说是正常的，还是我在做一些磨损的事情？

我想扩展一个 kd-tree (2D) 类，以便能够删除节点（点）。这种移除应该在不必重建树的大部分部分的情况下进行。这些幻灯片中描述的算法，在幻灯片 13 上似乎是我所追求的。但是，按照幻灯片 7 中的“findmin()”描述，我遇到了麻烦，该描述用于节点删除算法。

问题

1. 倒数第二行的“i”是什么意思？（也许这是作者的一个错误，因为它没有在其他地方引用？）

2. “whichAxis”到底是什么？它是我们想要最接近的分裂超平面的深度吗？

3. 什么是“最小（）”，最小化？我虽然这将是到轴的距离，但在我看来，作者正在最小化这些点，这对我来说没有意义。

I'm currently attempting to find K Nearest Neighbor of all nodes of a balanced KD-Tree (with K=2).

My implementation is a variation of the code from the Wikipedia article and it's decently fast to find KNN of any node O(log N).

The problem lies with the fact that I need to find KNN of each node. Coming up with about O(N log N) if I iterate over each node and perform the search.

Is there a more efficient way to do this?

尝试使用 KD 树创建 KNN 搜索。我可以很好地形成 KD 树（或者至少，我相信我可以！）。我的问题是我正在寻找与点列表中每个点最近的 2 个邻居。

那么，有没有一种方法可以使用 KD 树找到一个点的 K 最近邻居，即使该点实际上在树中，还是我需要为每个点构建一个单独的 KD 树，而忽略我希望的点寻找？

我的实现语言是 C++，但我更多的是寻找算法或一般帮助，谢谢！

谢谢，斯蒂芬

在共享内存机器上是否有 KD-Tree 的一些实现？

谢谢阿曼
。

我试图建立一个 kd-tree 来搜索一组点，但我对维基百科文章中“中位数”的使用感到困惑。为了便于使用，维基百科文章将 kd-tree 构造的伪代码声明为：

我对“选择中位数...”行感到困惑，仅仅是因为我不太确定在这里应用中位数的“正确”方法是什么。

据我所知，奇数（排序）数字列表的中位数是中间元素（又名，对于 5 个事物的列表，元素编号 3 或标准从零开始的数组中的索引 2），并且偶数大小数组的中位数是两个“中间”元素的总和除以 2（也就是，对于 6 个事物的列表，中位数是元素 3 和 4 - 或 2 和 3，如果为零 -索引 - 除以 2。）。

但是，当我们使用一组不同的点时，这个定义肯定在这里不起作用吗？那么如何为偶数大小的数字列表选择正确的中位数，尤其是长度为 2 的列表？

我感谢任何和所有的帮助，谢谢！

-斯蒂芬

我正在进行光线追踪，并希望通过一些加速结构（kd-tree、BVH 等）来加速它。我不想自己编码。到目前为止我已经尝试过：

• 将 kd-tree 从 pbrt 中拉出。有太多的内部依赖关系，如果不将所有 pbrt 都拉到我的代码中，我就无法成功。

• CGAL 的 AABB 树。令人沮丧的是，这似乎只返回了交点。在不知道该点来自哪个三角形的情况下，我无法在三角形上有效地插入颜色。我很想用颜色来扩展“点”的概念，但是如果不从头开始编写大量模板代码，这似乎是不可能的。

• 自己写。好的，所以我编写了自己的网格加速类，它可以工作，但它很讨厌而且效率低下。

因此，如果有人可以建议一个我可以用于此目的的简单库，我将不胜感激！我只需要一个三角形汤和射线，找到最近的交点并返回该三角形的索引。