Tag: 最近邻

2D KD树和最近邻搜索: 我正在按照此处描述的算法实现KD树和最近邻搜索： http ： //ldots.org/kdtree/ 我遇到了几种不同的方法来实现KD树，其中一个点存储在内部节点中，另一个只存储在叶节点中。因为我有一个非常简单的用例（我需要做的只是构造一次树，它不需要修改），我采用了仅叶子的方法，它实现起来似乎更简单。我已成功实现了所有内容，树总是成功构建，并且在大多数情况下，最近邻搜索返回正确的值。但是，我有一些问题，对于某些数据集和搜索点，算法返回不正确的值。考虑一下要点： [[6, 1], [5, 5], [9, 6], [3, 81], [4, 9], [4, 0], [7, 9], [2, 9], [6, 74]] 构建一个看起来像这样的树（借口我糟糕的图表）：方形叶节点是包含点的节点，并且圆形节点包含用于在该深度处分割列表的中值。当在这个数据集上调用我的最近邻居搜索，并寻找[6, 74]的最近邻居时，算法返回[7, 9] 。虽然这正确地遵循算法，但它实际上并不是[6, 74]的最接近点。最近的点实际上是[3, 81] ，其距离为7.6， [7, 9]距离为65。以下是绘制的点，对于可视化，红点是我试图找到最近邻居的点：如果有帮助，我的搜索方法如下： private LeafNode search(int depth, Point point, KDNode node) { if(node instanceof LeafNode) return […]