问题标签 [kdtree]

我有一个图像（appx 1000 x 1000）和一组每个 10 x 10 的小图像。

我创建了一个（3 维树）来存储每个图块的 HSL 值。我得到了一个图块 RGB 值的数组列表，它最接近目标图像中特定网格的 HSL。

问题是我不知道数组列表中的特定 HSL 属于哪个较小的图像。我有一个小图像类，它存储小图像被重用的次数。我需要访问这些字段以确定我可以使用哪个图块。

有没有一种方法可以获取我得到的小图像 HSL 的数组列表并获取小图像信息。

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

cKDTree 比 KDTree 快得多，但可定制性和可查询性较差（据我从文档中得知）。

这是我的问题： 我有一个包含 300 万个二维 (X,Y) 点的列表。我需要从每个点返回 X 个单位距离内的所有点。

使用 KDtree，有一个选项可以做到这一点：KDtree.query_ball_tree()它生成一个列表，其中包含 X 单位内的所有点与其他点的列表。但是：这个列表很大，很快就填满了我的虚拟内存（大约 7.44 亿条）。

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

潜在解决方案#2：我尝试使用 for 循环（对于列表中的每个点），然后通过使用：KDtree.query_ball_point(). 但是：这需要很长时间，因为它需要运行数百万次查询。是否有与此 KDTree 工具等效的 cKDTree？

潜在的解决方案＃3：击败我，其他人有什么想法吗？

我是一名学生，试图在 linux 86*64 上将 kdtree 与 libkdtree++ 一起使用。./configure 顺利，虽然 sudo make install 失败

我已经实现了一个使用给定点的 kd 树。例如，我可以向树中添加点，然后找到与给定 x、y 坐标最近的点，这很棒。

我想扩展它以使用矩形，例如用户给出一个 x 和 ay 坐标、一个宽度和一个高度，然后我希望能够在这个结构上进行范围查询和最近邻搜索。我将如何扩展我必须处理矩形数据的当前树？

每次我尝试做任何涉及 kd-tree 的事情时，似乎都会出现以下错误。奇怪的是，就在几天前，这段代码运行良好，并且在我同事的机器上仍然运行良好（我们使用的是相同的存储库）。

无论我输入什么，它似乎都会发生。

任何人都可以提供任何见解吗？

如果您查看kd trees的 Wikipedia 条目，您将看到将 2D 空间划分为矩形的点和平面的图示。

我的问题是如何获得结果矩形集？我认为到叶节点的每条“路径”都可能给我一个界限。对于任意深度的 N 个点，是否有一种通用的方法可以做到这一点？

请注意，我不要求的是超矩形结构的 kd 树，其中给定的输入是一组矩形，然后可以查询这些矩形进行范围搜索等。我的输入是一组随机点，我想输出完全“镶嵌”或细分笛卡尔空间的一组矩形。

四叉树和kd树的主要区别是什么？我知道他们在多个维度上分割点，但我不明白为什么我们会使用一个而不是另一个。我需要一个允许我计算给定区域中有多少点（2D 点）的结构。基本上，我正在尝试检测点簇。

这是我对它的理解： 1. 向下递归，根据 ELEMENT 是否存在于左子树或右子树中取左子树或右子树。2. 将 CURRENT_BEST 设置为您到达的第一个叶节点。3. 当你递归备份时，检查 ELEMENT 是否离分裂超平面比离 CURRENT_BEST 更近。如果是这样，请将 CURRENT_BEST 设置为当前节点。

这是我从Wikipedia和我的班级得到的部分，也是我不明白的部分： 4.检查3.中挑出的分裂点的另一个子树中的任何节点是否比分裂点更接近ELEMENT .

我不明白为什么我们需要做 4.，因为可能位于分裂节点的一个子树中的任何点都必须比另一个子树中的任何点更靠近分裂节点。

显然，我对算法的理解存在缺陷，因此将不胜感激。

我使用“列表中位数”算法在 Java 中编写了一个 KD-Tree，以构建一个更平衡的树。使用 wiki 提供的数据时似乎工作正常，请注意 wikipedia 示例仅使用 X、Y 值，因此它不评估 Z 深度。

来自维基百科：

从我的java程序：

但是，当我对这些数据使用“列表中位数”方法时，它似乎无法正常工作。

我得到一棵这样的树：

这看起来不正确，因为 (1.0, 0.0, 2.0) 在 (1.0, 0.0, 1.0) 的右侧，但它们本质上是相等的，因为它们的 Y 值相等。此外， (1.0, 0.0, -1.0) 在 (1.0, 0.0, -2.0) 的左侧，它应该在右侧，因为它的 Z 值更大。

我认为问题源于具有相等的 X 和 Y 值并且只有可变的 Z 值，因此列表的中位数并没有真正准确地拆分列表。

...遵循wiki的python代码的原始代码...

...基于我的评论的新代码...

我在实现一个给定 kdtree 的方法时遇到了一点问题，该方法将所有预先订购的项目存储在堆栈中。

我迭代地实现了这个方法，我有这个代码：

问题是，这种方法通过树的元素，不再具有恒定顺序，线性顺序，而是在最坏的情况下。

您能想出任何方法以恒定顺序将项目保存在堆栈中吗？

对不起，如果我解释得不好，我是西班牙人，我正在使用谷歌翻译 xD