在维基百科条目KD树 ，一种算法，做一个kd树最近邻搜索。 我不明白的是3.2步的解释。 你怎么知道那里是不是仅仅因为搜索点的分裂之间的差异协调和比搜索点的分裂之间的差异协调和目前最好的当前节点是更大的一个更近的点？
NN的最近邻搜索动画的KD树在2D搜索
最近邻（NN）算法旨在找到树是最近的给定输入点的点。 这种搜索可以有效地利用树性质快速消除搜索空间的大部分来完成。 搜索在kd树的过程如下最近邻居：
- 根节点开始，算法递归地向下移动的树，以同样的方式，它会如果正在插入的搜索点（即，它直或视点是否是比当前节点或大或小左分割尺寸）。
- 一旦算法到达叶节点，这样可以节省节点点作为“当前最好”
- 该算法解开树的递归，执行在每个节点处的以下步骤：1.如果当前节点是比当前最佳越近，则它变为当前最好的。 2.算法检查是否有可能是比目前最好的接近搜索点上的分裂平面的另一侧上的任何点。 在概念上，这是由分裂超平面周围有等于当前的最近距离的半径搜索点超球面交叉进行。 由于超平面都是轴对齐这被实现为简单的比较以查看所述搜索点的分束之间的差是否坐标和当前节点是小于距离（总体坐标）从搜索点到当前最好的。 1.如果超球越过平面，有可能是在飞机上的另一侧靠近点，因此算法必须与树的另一分支从当前节点寻找更接近点下移，以下同递归过程为整个搜索过程。 2.如果超球面不相交分割平面，则算法继续步行了树，并在该节点的另一侧的整个分支被消除。
- 当算法结束本过程对于根节点，则搜索完成。
一般来说，算法采用平方距离进行比较，以避免计算平方根。 此外，它还可以通过按住一个变量的平方当前最佳距离比较节省计算。
在第6帧仔细看该网页上的动画 。
由于算法是回到了递归，有可能存在于它的上超平面的另一边仔细点。 我们已经检查了一半，但也有可能是对另一半的更近点。
那么，事实证明，我们有时可以简化。 如果它是不可能有是对另一半比我们目前最好的（最近）点更靠近一点，那么我们就可以完全跳过这个超平面的一半。 这种简化是第六帧上显示的一个。
搞清楚这种简化是可能被来自超平面的距离比较我们的搜索位置完成。 因为超平面与轴对齐，从它直线最短任何其他点将沿一维的线，所以我们可以比较维度超平面分割的只是坐标。
如果是从搜索点比从搜索点到当前的最近点更远的超平面，那么就没有理由寻找过去那种分裂的坐标。
即使我的解释也无济于事，图形会。 祝你的项目！
是的，NN（近邻），在KD树在维基百科上搜索的描述是有点难以跟随。 它没有帮助， 很多的NN KD树搜索上谷歌搜索结果中的是完全错误的！
下面是一些C ++代码来告诉你如何得到它的权利：
template <class T, std::size_t N>
void KDTree<T,N>::nearest (
const const KDNode<T,N> &node,
const std::array<T, N> &point, // looking for closest node to this point
const KDPoint<T,N> &closest, // closest node (so far)
double &minDist,
const uint depth) const
{
if (node->isLeaf()) {
const double dist = distance(point, node->leaf->point);
if (dist < minDist) {
minDist = dist;
closest = node->leaf;
}
} else {
const T dim = depth % N;
if (point[dim] < node->splitVal) {
// search left first
nearest(node->left, point, closest, minDist, depth + 1);
if (point[dim] + minDist >= node->splitVal)
nearest(node->right, point, closest, minDist, depth + 1);
} else {
// search right first
nearest(node->right, point, closest, minDist, depth + 1);
if (point[dim] - minDist <= node->splitVal)
nearest(node->left, point, closest, minDist, depth + 1);
}
}
}
对于NN在KD树搜索API：
// Nearest neighbour
template <class T, std::size_t N>
const KDPoint<T,N> KDTree<T,N>::nearest (const std::array<T, N> &point) const {
const KDPoint<T,N> closest;
double minDist = std::numeric_limits<double>::max();
nearest(root, point, closest, minDist);
return closest;
}
默认距离函数：
template <class T, std::size_t N>
double distance (const std::array<T, N> &p1, const std::array<T, N> &p2) {
double d = 0.0;
for (uint i = 0; i < N; ++i) {
d += pow(p1[i] - p2[i], 2.0);
}
return sqrt(d);
}
编辑：一些人都在问与数据结构的帮助太大（不只是NN算法），所以这里是我用过的东西。 根据你的目的，你不妨稍微修改的数据结构。 （注：但你几乎肯定不希望修改NN算法）。
KDPoint类：
template <class T, std::size_t N>
class KDPoint {
public:
KDPoint<T,N> (std::array<T,N> &&t) : point(std::move(t)) { };
virtual ~KDPoint<T,N> () = default;
std::array<T, N> point;
};
KDNode类：
template <class T, std::size_t N>
class KDNode
{
public:
KDNode () = delete;
KDNode (const KDNode &) = delete;
KDNode & operator = (const KDNode &) = delete;
~KDNode () = default;
// branch node
KDNode (const T split,
std::unique_ptr<const KDNode> &lhs,
std::unique_ptr<const KDNode> &rhs) : splitVal(split), left(std::move(lhs)), right(std::move(rhs)) { };
// leaf node
KDNode (std::shared_ptr<const KDPoint<T,N>> p) : splitVal(0), leaf(p) { };
bool isLeaf (void) const { return static_cast<bool>(leaf); }
// data members
const T splitVal;
const std::unique_ptr<const KDNode<T,N>> left, right;
const std::shared_ptr<const KDPoint<T,N>> leaf;
};
KDTree类：（注意：你需要添加一个成员函数建立/填充你的树）
template <class T, std::size_t N>
class KDTree {
public:
KDTree () = delete;
KDTree (const KDTree &) = delete;
KDTree (KDTree &&t) : root(std::move(const_cast<std::unique_ptr<const KDNode<T,N>>&>(t.root))) { };
KDTree & operator = (const KDTree &) = delete;
~KDTree () = default;
const KDPoint<T,N> nearest (const std::array<T, N> &point) const;
// Nearest neighbour search - runs in O(log n)
void nearest (const std::unique_ptr<const KDNode<T,N>> &node,
const std::array<T, N> &point,
std::shared_ptr<const KDPoint<T,N>> &closest,
double &minDist,
const uint depth = 0) const;
// data members
const std::unique_ptr<const KDNode<T,N>> root;
};
