c - 连续使用返回值作为函数的输入

Question

我有一个代码，它使用用C编写的KD-tree来搜索最近的邻居，然后使用返回的值从该点搜索下一个最近的邻居。我想这样做大约5次迭代，即第一次迭代的结果被用作第二次迭代的输入，第二次迭代的结果被用作第三次迭代的输入，等等。我是一个初学者，我认为while循环可能会工作，但在两次迭代后失败，即我再次得到相同的输入。
如何更改此变量的值以反映更改，从而使第一次迭代的输出是上次执行的操作的输入。此外，如果有一种方法来创建一个功能，这将是高度赞赏。代码与gcc编译器一起工作。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define MAX_DIM 4

struct kd_node_t{
    double x[MAX_DIM];
    struct kd_node_t *left, *right;
};

    inline double
dist(struct kd_node_t *a, struct kd_node_t *b, int dim)
{
    double t, d = 0;
    while (dim--) {
        t = a->x[dim] - b->x[dim];
        d += t * t;
    }
    return d;
}
inline void swap(struct kd_node_t *x, struct kd_node_t *y) {
    double tmp[MAX_DIM];
    memcpy(tmp,  x->x, sizeof(tmp));
    memcpy(x->x, y->x, sizeof(tmp));
    memcpy(y->x, tmp,  sizeof(tmp));
}


/* quickselect method */
    struct kd_node_t*
find_median(struct kd_node_t *start, struct kd_node_t *end, int idx)
{
    if (end <= start) return NULL;
    if (end == start + 1)
        return start;

    struct kd_node_t *p, *store, *md = start + (end - start) / 2;
    double pivot;
    while (1) {
        pivot = md->x[idx];

        swap(md, end - 1);
        for (store = p = start; p < end; p++) {
            if (p->x[idx] < pivot) {
                if (p != store)
                    swap(p, store);
                store++;
            }
        }
        swap(store, end - 1);

        /* median has duplicate values */
        if (store->x[idx] == md->x[idx])
            return md;

        if (store > md) end = store;
        else        start = store;
    }
}

    struct kd_node_t*
make_tree(struct kd_node_t *t, int len, int i, int dim)
{
    struct kd_node_t *n;

    if (!len) return 0;

    if ((n = find_median(t, t + len, i))) {
        i = (i + 1) % dim;
        n->left  = make_tree(t, n - t, i, dim);
        n->right = make_tree(n + 1, t + len - (n + 1), i, dim);
    }
    return n;
}


int visited;

void nearest(struct kd_node_t *root, struct kd_node_t *nd, int i, int dim,
        struct kd_node_t **best, double *best_dist)
{
    double d, dx, dx2;

    if (!root) return;
    d = dist(root, nd, dim);
    dx = root->x[i] - nd->x[i];
    dx2 = dx * dx;

    visited ++;

    if (!*best || d < *best_dist) {
        *best_dist = d;
        *best = root;
    }


    nearest(dx > 0 ? root->left : root->right, nd, i, dim, best, best_dist);
    if (dx2 >= *best_dist) return;
    nearest(dx > 0 ? root->right : root->left, nd, i, dim, best, best_dist);
}

int main(void)
{
    int i;

  struct kd_node_t wp[] = {
        {{7, 9, 5, 56}},{{2, 4, 8, 10}},  {{81, 2, 31, 80}}, {{31, 4, 900, 1}},{{4, 7, 1, 9}}, {{9, 6, 2,0}}, {{4, 3, 11, 2}},{{7, 7, 9, 1}}, {{6, 9, 0,2}}
    };

    struct kd_node_t testNode = {{0, 2}}; //This is the input

    struct kd_node_t *root, *found, *million;
    double best_dist;
    double length =sizeof(wp) / sizeof(wp[1]);
    root = make_tree(wp, sizeof(wp) / sizeof(wp[1]), 0, 2);

    visited = 0;
    found = 0;
    nearest(root, &testNode, 0, 2, &found, &best_dist);

    printf(">> WP tree\nsearching for (%g, %g)\n"
            "found (%g, %g %g, %g) dist %g\nseen %d nodes\n\n",
            testNode.x[0], testNode.x[1],
            found->x[0], found->x[1],found->x[2], found->x[3], sqrt(best_dist), visited);
//It produces an output found->x[0], found->x[1], found->x[2], found->x[3]

for(int i=0; i<5; i++) //Where the problem is and where i will like to continuously use the returned value as input
{


    testNode = {{found->x[2], found->x[3]}}; // This is the new input i.e the output of the previous run
printf(" (%g, %g) ",
                found->x[2], found->x[3]);
     root = make_tree(wp, sizeof(wp) / sizeof(wp[1]), 0, 2);
     nearest(root, &testNode, 0, 2, &found, &best_dist);
  printf(">> WP tree\nsearching for (%g, %g)\n"
            "found (%g, %g %g, %g) dist %g\nseen %d nodes\n\n",
            testNode.x[0], testNode.x[1],
            found->x[0], found->x[1],found->x[2], found->x[3], sqrt(best_dist), visited);



}



    return 0;
}

这是运行代码的示例输出

>> WP tree
searching for (0, 2)
found (2, 4 8, 10) dist 2.82843
seen 4 nodes

8 10>> WP tree
searching for (8, 10)
found (7, 9 5, 56) dist 1.41421
seen 11 nodes

5 56>> WP tree
searching for (5, 56)
found (7, 9 5, 56) dist 1.41421
seen 16 nodes

5 56>> WP tree
searching for (5, 56)
found (7, 9 5, 56) dist 1.41421
seen 21 nodes

5 56>> WP tree
searching for (5, 56)
found (7, 9 5, 56) dist 1.41421
seen 26 nodes

5 56>> WP tree
searching for (5, 56)
found (7, 9 5, 56) dist 1.41421
seen 31 nodes

实际上，5，56应该返回6，9，0，2，下一个要选择的点应该是0，2等等。
另外，我如何从wp中临时删除返回值的值，以便在搜索时，它在搜索空间中不包括其坐标，但在下一次迭代时，应恢复其值。例如，假设我正在搜索5,56；当前搜索的整个{7、9、5、56、30}将从wp中删除，但稍后将在返回最近的数据后还原。
任何帮助都将不胜感激。谢谢

Answer 1

在一条注释中，我声明OP需要修改代码以忽略已经知道的点。
然而，事实证明这是不正确的。Ak-d tree非常适用于将最近的“映射”已知点定位到任何提供的点。然而，试图忽略映射点会导致严重的并发症。一个典型的结果是，你的搜索只是错过了一些最近的点。这是可以纠正的，但它会减慢搜索速度，并需要更复杂的代码。
当k-d树搜索试图将树中的点排除在考虑范围之外时，我花了很多心思，甚至还用了一个示例程序来找出究竟发生了什么。那些知道k-d树这种性质的人可能会嘲笑我没有更早地意识到这一点；当你意识到发生了什么时，这是非常简单的。然而，大多数作者都发现了这一点，并简单地说，K-D树是近似最近邻数据结构（至少当您希望忽略树中的特定点）时。
所以，希望这能对其他人有所帮助，以下是我对此事的看法。
首先，让我们回顾一下“普通”k-d树近邻搜索的工作原理：
所有点都存储在叶节点中
通常，一组点存储在每个叶节点中；大小取决于使用的维度数。对于3D，我将从每个叶节点至少10个向量开始。最佳数量取决于太多的因素，任何真正的指南都不只是手工操作。
每个内部节点沿着一个轴将搜索卷分成两半
为了找到一个测试点的近似最近邻，一个函数下降到树中，总是选择包含测试点的搜索卷，直到它到达一个叶节点；在那里，它找到最靠近测试点的点。
为了确保在叶节点中找到的邻居是真正的最近邻居，或者为了找到实际的邻居，精确的最近邻居搜索必须返回到根节点。对于每个内部节点，如果分割平面（分割坐标）比到目前为止找到的最近邻的距离更近，则还必须验证另一个子体积（而不是我们刚刚从中上升）。
有几种方法可以将搜索扩展到k近邻。
我最初的建议是，一个人可以忽略树中已经知道的点，但偶尔会失败，因为如果在排除其他节点之后，在叶节点中发现了邻居，那么我们就不能下降到兄弟节点，因为分割平面太远了。通常，我们偶然发现一个离根部更高、更近的分裂平面，然后下降到子卷中，但没有效果：我们已经跳过了真正的近邻所在的子卷。
一个更好的选择是记录所有k个最近的邻居，并使用最远的一个决定何时不下降到兄弟子卷在我们返回到根的路上。我们只需要为k个最近的邻居留出空间，根据与测试点的距离进行排序。当从叶返回到根时，将按照几个步骤修改此列表。
当然，这不会返回第k个最近的邻居，而是返回所有k个最近的邻居到测试点。通常，这样比较好。我不知道效率图（为了满足典型的搜索，必须访问多少个叶节点），但是如果k通常是按存储在每个叶节点中的点数的顺序排列的，那么性能应该是可以接受的。
直接从考虑中排除树中的特定点是可能的，但很复杂。当到达初始叶节点时，我们必须决定是否在返回根的路上下降到兄弟子卷中，但将其排除在最近邻的考虑之外。特别是，如果我们的初始叶节点中的所有点都不在考虑范围内，那么我们必须在向上的过程中下降到所有兄弟子卷中，直到我们有一个最近的邻居候选。
其中，检索k个最近邻居的变体在我看来具有最高的潜力。（这与普通的精确邻域搜索非常相似，对于合理的k值（与每个叶节点的点数相比），它至少应该执行可接受的——当然比在同一个数据集上执行k个单独的搜索要快。）
我很想写一些示例代码，但鉴于我已经在这个问题上做了一番努力，我很犹豫。