问题标签 [kdtree]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
c++ - Kdtree 查找：PBRT 源代码
我正在尝试使用 pbrt 源代码来实现 kdtree 以查找n最近的点。我有一个分布在 3d 空间上的点数组，我需要计算距参考点给定距离内的点数。那么有人可以指导我如何进行吗？基本上，我使用的是与 integrators/photonmap.cpp 中提到的相同的查找过程 (PhotonProcess)。但不知何故，我最终得到了奇怪的结果。这是我正在使用的代码的一小部分。
我没有得到 searchdist 的预期值。欢迎任何提示想法或建议。
performance - 具有可变密度的欧几里得数据的简单k最近邻算法？
关于这个问题的详细说明，但有更多限制。
这个想法是相同的，为 2 维欧几里得的 k 最近邻找到一个简单、快速的算法。如果您能找到合适的网格大小来对数据进行分区，则分桶网格似乎工作得很好。但是，如果数据不是均匀分布的，而是具有非常高和非常低密度的区域（例如，美国人口），那么没有固定的网格大小可以保证足够的邻居和效率怎么办？这种方法还能挽回吗？
如果没有，其他建议会有所帮助，但我希望答案比转移到 kd-trees 等复杂。
kdtree - 使用 vlfeat 的慢速 kd 树查询，更快的替代方案？
我正在使用 vlfeat 的 kdtree，它实现了 FLANN 的 kd-tree，据说它可以处理高维数据。但是，现在我有一个从 128x15000 数据集构建的 kdtree，并且对任何内容的 kd 树查询都已减慢到 8 秒。这是kd-trees的极限吗？FLANN 也应该是一个更快优化的 kdtree...
我现在还有什么其他选择？
python - 从树递归中返回值列表
我正在尝试自学数据结构，并且我正在用 Python 实现一个 kd 树。我有一种方法可以在我的 kd 树类中一个点的某个半径内搜索树中的点：
它可以工作，但它返回的列表非常时髦，带有来自递归调用的重复值result。将树递归返回的值“累积”到列表中的好方法是什么？我已经考虑了一段时间，但我真的不知道怎么做。
python - kd树构建排序优化
用 Python 编程语言实现的 kd-tree 的算法构建如下（来自http://en.wikipedia.org/wiki/K-d_tree）：
每一步都进行排序。如何减少分拣量？
sorting - 我怎样才能制作这个KD树？
我有一个很长的、半排序的纬度、经度和时区三元组列表。我希望能够快速搜索此列表以找到与任何给定纬度和经度最近的时区，因此我想将此列表制作成 KD 树。
我在想我应该首先将整个文件读入某种数据结构（什么数据结构？可能ArrayList<Triplet<Double, Double, String>>？）。然后取该结构中的中间元素并将其作为根，给我留下一个左右列表。然后继续获取每个列表的中间元素并将其添加为左子或右子。
第一次尝试似乎很慢而且效率低下......但我觉得我做错了。你能为我提供一个算法或伪代码吗？
ios - 我应该使用什么空间索引算法？
我想为我的MKAnnotations. 目前，当我尝试根据距离标准过滤它们时，速度非常慢（3-4k 个位置，目前使用简单的双精度非常慢for......）。
我想创建MKAnnotations, 的集群来决定它是否靠近另一个。此外，这些位置在某种程度上是（创建）顺序，并且需要“上一个”/“下一个”功能来“跳转”（这不是必须的）。我已经阅读了kd-tree和r-tree结构，它们似乎都满足过滤/聚类的快速距离/邻居获取选项，但我不确定哪个最适合我，或者是否还有其他选项。我应该使用什么算法/数据结构？
更新：我将这些位置存储在核心数据数据库中，它们代表一条路径。当地图打开时，它们被提取到一个数组中，然后我只使用该数组进行距离计算和注释创建。当用户移动/缩放地图时，我会遍历它们并决定需要在地图上更改哪些内容，因此整个内容都是静态的。据我了解，如果我使用一棵树，我可以将位置存储在那里，当发生缩放/移动时，我只需搜索它并获取新区域中的位置。这是真的 ？
即使在动态情况下，当我可以向该数组添加新位置时，它也将是一次插入，并且很少发生。
opencv - SIFT描述符匹配的有效方法
有 2 个图像 A 和 B。我从中提取关键点（a[i] 和 b[i]）。
我想知道如何有效地确定 a[i] 和 b[j] 之间的匹配？
对我来说，显而易见的方法是将 A 中的每个点与 B 中的每个点进行比较。但是对于大型图像数据库来说，它非常耗时。我怎样才能将点 a[i] 与 k 范围较小的 b[k] 进行比较？
我听说kd-tree可能是一个不错的选择，不是吗？有没有关于kd-tree 的好例子？
还有其他建议吗？
python - 最近邻搜索：Python
我有一个二维数组：
前两个元素MyArray[0]和MyArray[1]是点的X和Y坐标。
对于数组中的每个元素，我想找到以X单位为半径返回其单个最近邻居的最快方法。我们假设这是在二维空间中。
让我们说这个例子X = 6。
我通过将每个元素与其他元素进行比较来解决了这个问题，但是当您的列表长度为 22k 点时，这需要 15 分钟左右。我们希望最终在大约 3000 万个点的列表上运行它。
我已经阅读了 Kd 树并理解了基本概念，但在理解如何编写它们时遇到了麻烦。
javascript - 有效地确定一个点在二维空间中的哪个矩形
我有一大组在 html5 画布上绘制的矩形。
我希望能够使用鼠标跟踪与此图像进行交互（我不能使用 SVG，因为它不能缩放到 10-100k 矩形）。是否有任何数据结构/算法，假设鼠标 x,y 坐标能够告诉您鼠标在哪个框上（使用矩形的计算位置）？我在想像 kd 树之类的东西，但不确定。