问题标签 [kdtree]

我想得到一个kdtree二维（x，y）的最小元素。最小元素是kdtree的每个元素（x'，y'），x

作为可以重复的元素 x，返回其中之一。

我在 wiki 中阅读了 kd 树描述，wiki 说 kd 树保留点。我有三角形网格，需要一些结构来有效计算与圆柱体的交点和点到点的距离查询。据我了解，如果我按平面分割网格 - 许多三角形可以与该平面相交。那我该怎么办？将三角形的副本放在左右子框中，还是分割相交的三角形？

所以 NetworkX 很清楚，他们在 n^2 时间内使用算法来生成随机几何图。他们说使用 KD 树可以实现更快的算法。我的问题是如何尝试实现该算法的 KD 树版本？我不熟悉这种数据结构，也不会称自己为 python 专家。只是想弄清楚这一点。感谢所有帮助，谢谢！

我已经阅读了有关四叉树或 kd-tree 拆分和 mandelbrot 集的信息，但是当第一次拆分之前的矩形和框架位于 mandelbrot 集中或具有相同的迭代深度并且算法从平铺返回时怎么办？当矩形太大时，如何强制跳过填充矩形？

因此，在平衡 KD 树时，您应该找到中位数，然后将所有较小的元素放在左子树上，将较大的元素放在右边。但是，如果您有多个元素的值与中位数相同，会发生什么？它们进入左子树，右子树还是丢弃它们？

我问是因为我尝试过做多件事，它会影响我最近邻搜索算法的结果，并且在某些情况下，树的给定部分的所有元素都将具有完全相同的值，所以我不知道在这种情况下如何将它们分开。

上个月我一直在制作一个照片马赛克网站。我用 PHP 构建了所有东西，我让它工作得很好。我唯一不喜欢的是执行时间。由于线性比较搜索，我认为这太长了。所以我一直在询问如何改善我的搜索时间，大多数人都将我指向 KD-tree 的方向，这将使 k-最近邻变得更快。

所以我一直在研究 KD-tree 并且我了解如何手动构建这样的树。现在我当然想编写这个代码，我只能找到 C++ 和 java 的库。因为我只熟悉 PHP，所以我一直在尝试自己制作，但这并不像我想象的那么容易。

• 我面临的一个问题是如何存储所有内容。当我得到第一个包含所有点的数组时，我会将它分成 3 块。左分支、节点和右分支。当然我会对左分支做同样的事情，直到我不能再分裂，当然我循环穿过轴（XYZ）。但是我如何存储所有正确的分支，我将它们留在数组中吗？还是在我准备好使用它们时再次计算它们？

• 我想知道的另一件事是为什么没有 PHP KD-tree 脚本是因为 PHP 不是适合这项工作的语言？

这就是我到目前为止所得到的。

这个函数计算我用来测试其余部分的随机颜色 (RGB)。

此函数对特定键上的多维数组进行排序（默认为 R）

此类将数组拆分为左分支、节点和右分支。

我有一个 kdtree，其节点包含以下字段： public static class Node implements Serializable {

其中数据点定义：

公共静态类 DataPoint 实现 Serializable { public Comparable X; 公共可比 Y；公共可比 Z；

我想序列化树，存储在文件中并在回答范围查询时反序列化。我对这个概念 od 序列化的理解并不好。从我收集的任何内容中，我编写了以下函数，但这些函数不起作用。有人可以帮忙吗？

Google 有一个用 C 语言编写的 KD 树库：这里

据我所知，您使用其中一个函数将注释插入树中，然后查询树中最近的邻居。它返回一个指向新数组的指针（据我所知）。

这是我的目标：

我有一个 3D 数组，我希望找到一种方法来返回给定点最近邻居的索引。我想说：这是一个点：（12,23,14），现在告诉我最接近的点的索引，例如：“它是数组中的第 5 项”。但是，我不知道该怎么做。

我的问题，有没有人：

A）知道一个有据可查的关于 c 的 k 维最近邻搜索库，或者：

B) 知道如何获取 Google 的代码以返回数组中最近邻居的位置。

Scipy有一个出色的空间分析包，其中包括一个 K 维树。我正在尝试使用查询功能，它返回此错误：

ValueError: x 必须由长度为 6 但形状为 (2,) 的向量组成

有谁知道这个错误指的是什么？

通过一些谷歌搜索，我发现它具有以下通用格式：

我相信这是源代码。

我正在尝试实现 Kd 树以在 C++ 中执行最近邻和近似最近邻搜索。到目前为止，我遇到了最基本的 Kd 树的 2 个版本。

1. 一种，数据存储在节点和叶子中，例如这里
2. 一种，数据仅存储在叶子中，例如这里

它们似乎基本相同，具有相同的渐近特性。

我的问题是：有什么理由选择一个而不是另一个？

到目前为止，我想出了两个原因：

1. 在节点中存储数据的树也浅了 1 级。
2. 只在叶子中存储数据的树更容易实现delete data功能

在决定制作哪一个之前，我还应该考虑其他一些原因吗？