问题标签 [kdtree]

我一直在尝试从头开始实现 KdTree。成功实现了 add-，find最近的邻居，find range 方法中的节点，我现在被困在删除节点上。

维基百科上描述的方法含糊不清，而且毫无用处。相反，我使用这些幻灯片作为起点。但是，幻灯片 13 上对删除方法的描述让我感到困惑：

两者都替换t.left和没有意义。nullt.right with remove(t.right, ...)

这是正确的吗？当我们这样做的时候，这种方法还有什么问题吗？应该注意的是，与这些幻灯片中描述的方法相反，我将相等的节点放在左边，而不是右边。方法还有效吗？

我有两个集合，A 和 B。这些集合由 N 个维度点组成并有序（N<10）。我需要找到 B 到 A 的最近部分。假设最近的部分是 B1。B1 中的点数应与 A 相同，且 B1 中所有点到 A 的距离之和应最小。

我检查了kd树。它只有助于在集合中找到最近的点。那么有没有一种算法可以快速找到最近的范围？

谢谢。

我有一组多边形区域（地理围栏）。这组数据是固定的；所以不需要插入和删除数据。哪种数据结构可用于搜索查询点（经度、纬度）所在的区域？

注意：我已经为一组点成功实现了 KD-Tree（实际上是 2D-Tree）。但它不适用于这个问题。然后我实现了一个 R-Tree；它解决了问题，但速度很慢（或者我的实现很糟糕）。

谢谢

注意：我从事过 R-Tree 实现，现在可以正常工作。

我使用 CGAL 的 Kd-tree 实现以及模糊球体作为查询对象，以获取包围在r_max以一个点为中心的半径球体中的点。这是这个最小的工作示例：

我从 CGAL 示例的 Spatial_searching 文件夹（我的版本是 3.9）下的最近的_neighbor_searching.cpp 文件中获取并修改了注释“打印点”下面的行。

问题是：有没有办法让我设置一个不同的OutputIterator（而不是std::ostream_iterator）存储指针/迭代器/句柄到在排序容器中搜索产生的点，而不是将点的坐标打印到标准输出？谢谢你。

以下类从 g++ 返回以下错误：

tree.h:9：错误：“模板”之前的预期不合格 ID

如果第 5 行未注释，则会发生相同的错误，仅在第 5 行。

我是否因为盯着这个太久而错过了一个明显的语法错误？还是我不正确地声明了模板类？

我开始在 Python 中为 Blender 开发这个粒子引擎：http ://www.youtube.com/watch?v=uoK4QV3jg58&feature=channel_video_title

所有数据都由我的脚本处理，Blender 只是用于视觉效果。我现在的问题是，在上面的视频中，我计算了所有粒子的每个粒子之间的距离，以检测它们是否相互碰撞。

我开始阅读：

• 八叉树
• kd树
• BVH树
• AABB树
• ...还有很多

Kdtree 似乎对于搜索最近的邻居非常有效，但仅适用于静态云。我的粒子总是在移动，因此每次迭代都必须重新生成 kdTree，我认为这消耗了太多的过程。我读过很多游戏都使用 AABB 树。我有点迷茫……我不知道该选择什么。我想要的是：

• 检测大量粒子（250 000 或更多）之间的碰撞
• 不需要是实时的（无论如何有 250 000 个粒子是不可能的）。200 万个粒子每帧 20 分钟对我来说不是问题。
• 我的粒子总是球体
• 检测粒子和多边形对象之间的碰撞
• 减少必要距离计算的算法（避免为其他粒子或多边形计算所有粒子，即使它们很远）
• 我的粒子是动态的，我的多边形对象可以是动态的或静态的。

如果有人能告诉我什么是最好的猜测，我在哪里可以找到 Python 文档和示例。

我想将一张图像 (A) 中的 SURF 描述符与其他几张图像 (B,C,D,..) 中的描述符进行比较，以找到与 A 最相似的图像。描述符有 64 个维度。

使用 C# 和 Emgu，通过将 A 的描述符与 B 的描述符进行比较来完成匹配，然后是 C 的描述符，然后是 D 的描述符，依此类推。当图像数量超过 10 时，这非常慢，因为必须搜索许多不相关的描述符。

为了加快这个过程，正确的方法（根据文章）似乎是为 (B,C,D,..) 中的描述符构建一个 kd-tree 以快速匹配找到 A 中的描述符。 kd -tree 根据级别在维度上进行拆分。第一次拆分由第一维决定，第二次拆分由第二维等决定。但是，在描述符（64）的维数很高时，使用 KD-tree 的好处变得更小。

所以我的问题是：使用 KD-tree/其他方法将 SURF 描述符从一个图像 (A) 匹配到多个图像 (B、C、D..)，您有什么经验或知识。什么效果好，什么效果不好，你做过这样的事情吗？

FLANN 在这里是一个选项，因为它被 OpenCV 使用，但我找不到 C# 的版本。大约最近的 Neightboor 也是加速 kd-tree 的一个选项，但是这对匹配图像有效吗？

最好的问候莫腾

我无法弄清楚下面的代码段在做什么。它取自Henrik Wann Jensen所著的Realistic Image Synthesis Using Photon Mapping一书。我认为它正在尝试做的事情（或者鉴于它在代码中的位置，我认为它应该尝试做的事情）是计算某个开始和结束索引之间的数组中的中值索引。

有关更多上下文，该代码来自在给定 3D 点列表的情况下构建 kd-tree 数据结构的部分。在构建 kd-tree 的每个递归步骤中，选择中点（相对于某个维度）作为新 kd-tree 的根。

我认为这段代码应该计算一些开始和结束索引之间的中值索引，但如果我是正确的，那么我无法弄清楚为什么这个中值索引是以这种奇怪的方式计算的。

任何帮助或见解将不胜感激，谢谢！

编辑：感谢 Vaughn Cato，我现在看到有必要以这种方式计算中位数指数。最初我很困惑为什么你不能只做 (end - start)/2 + start。这段代码的目标是获取一个点列表并将其转换为一个完整的、平衡的 kd-tree，它可以存储在一个类似堆的数据结构中（整个二叉树在一个数组中）。以天真的方式计算中位数索引不一定会得到一棵可以展平为数组的树。

现在我很困惑有人是如何想出这个的。任何人都可以解释或指出推导的方向吗？

我已经成功编写了一个函数，该函数遍历 Kd-Tree 以获得点的最近单个邻居。

但是，我正在尝试切换此功能，以便它找到 K 近邻，而不仅仅是单个。事实证明，这比我最初想象的要艰巨得多，而且我发现自己需要一些帮助……

关于 kD-trees 的维基百科文章说：

该算法可以通过简单的修改以多种方式扩展。它可以通过保持 k 个当前最佳值而不是仅仅一个来为一个点提供 k 个最近邻。只有当它们的点不能比任何 k 当前最佳值更接近时，分支才会被消除。

...但它没有说明如何获得最初的当前最佳值。找到第一个“最佳”很简单，但我不知道如何在不删除以前的最佳并重新搜索的情况下找到其余的 k-current 最佳……这基本上违背了拥有一个快速算法，因为我必须做 k（在我的情况下，17）次。

如果我有一个包含 17 个初始“最佳”的填充列表，我相信我的算法会找到正确的点。

如果这含糊不清，我深表歉意。如果需要任何代码示例，我很乐意提供。虽然如果对这个问题有一个简单的解释，可能没有必要发布它，所以我一开始不会。

提前致谢！

我需要一个数据结构来查找落在一个矩形中的所有段（在 C# 中，即使它不是主要问题）。

例如，段 [(0,0) , (10,10)] 必须位于从 (5,5) 开始、大小为 (1,1) 的矩形中。

我尝试了kdtree，但是当他的一个点正好在矩形中时，它只返回段。它不会将线段视为连续线。

我需要什么样的数据结构才能有效地进行搜索？
我搜索但没有找到任何适合这种情况的东西，即使它看起来很标准！

问题维度：6000 条线段，矩形内平均有 20 条线段

重复排序：

• 如何在 kd-tree 中最好地存储行
• 快速线路查询的数据结构？