基于四叉树，实现最近邻检测。用C语言实现

以下是一个基于四叉树实现最近邻检测的 C 语言代码示例。

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

#define MAX_POINTS 10000
#define MAX_DEPTH 10
#define THRESHOLD 10

typedef struct point_t {
    double x;
    double y;
} point_t;

typedef struct quadtree_node_t {
    point_t points[MAX_POINTS];
    int count;
    double x1, x2, y1, y2;
    struct quadtree_node_t *nw, *ne, *sw, *se;
} quadtree_node_t;

double distance(point_t p1, point_t p2) {
    double dx = p1.x - p2.x;
    double dy = p1.y - p2.y;
    return sqrt(dx * dx + dy * dy);
}

void quadtree_insert(quadtree_node_t **node, point_t point, double x1, double x2, double y1, double y2, int depth) {
    if (*node == NULL) {
        *node = (quadtree_node_t *) malloc(sizeof(quadtree_node_t));
        (*node)->count = 0;
        (*node)->nw = (*node)->ne = (*node)->sw = (*node)->se = NULL;
        (*node)->x1 = x1;
        (*node)->x2 = x2;
        (*node)->y1 = y1;
        (*node)->y2 = y2;
    }
    if ((*node)->count < MAX_POINTS) {
        (*node)->points[(*node)->count++] = point;
    } else {
        if (depth < MAX_DEPTH) {
            double xmid = (x1 + x2) / 2;
            double ymid = (y1 + y2) / 2;
            if (point.x < xmid && point.y < ymid) {
                quadtree_insert(&((*node)->nw), point, x1, xmid, y1, ymid, depth + 1);
            } else if (point.x >= xmid && point.y < ymid) {
                quadtree_insert(&((*node)->ne), point, xmid, x2, y1, ymid, depth + 1);
            } else if (point.x < xmid && point.y >= ymid) {
                quadtree_insert(&((*node)->sw), point, x1, xmid, ymid, y2, depth + 1);
            } else {
                quadtree_insert(&((*node)->se), point, xmid, x2, ymid, y2, depth + 1);
            }
        } else {
            (*node)->points[(*node)->count++] = point;
        }
    }
}

void quadtree_search(quadtree_node_t *node, point_t query, point_t *nearest, double *mindist) {
    if (node == NULL) {
        return;
    }
    for (int i = 0; i < node->count; i++) {
        double dist = distance(node->points[i], query);
        if (dist < *mindist) {
            *mindist = dist;
            *nearest = node->points[i];
        }
    }
    double x = query.x, y = query.y;
    if (x < node->x1 - *mindist || x > node->x2 + *mindist || y < node->y1 - *mindist || y > node->y2 + *mindist) {
        return;
    }
    if (node->nw == NULL && node->ne == NULL && node->sw == NULL && node->se == NULL) {
        return;
    }
    if (node->nw != NULL) {
        quadtree_search(node->nw, query, nearest, mindist);
    }
    if (node->ne != NULL) {
        quadtree_search(node->ne, query, nearest, mindist);
    }
    if (node->sw != NULL) {
        quadtree_search(node->sw, query, nearest, mindist);
    }
    if (node->se != NULL) {
        quadtree_search(node->se, query, nearest, mindist);
    }
}

int main() {
    quadtree_node_t *root = NULL;
    point_t points[] = {{1, 2}, {3, 4}, {5, 6}, {7, 8}, {9, 10}};
    int n = sizeof(points) / sizeof(points[0]);
    for (int i = 0; i < n; i++) {
        quadtree_insert(&root, points[i], 0, 10, 0, 10, 0);
    }
    point_t query = {4, 5};
    point_t nearest = {0, 0};
    double mindist = INFINITY;
    quadtree_search(root, query, &nearest, &mindist);
    printf("Nearest point: (%.2lf, %.2lf), distance: %.2lf\n", nearest.x, nearest.y, mindist);
    return 0;
}

在上面的代码中，`quadtree_insert()` 函数用于在四叉树中插入新的点，`quadtree_search()` 函数用于查找离查询点最近的点。其中，`distance()` 函数用于计算两个点之间的距离。

在 `main()` 函数中，首先创建了一些测试用的点，并插入到四叉树中。然后，定义一个查询点，并调用 `quadtree_search()` 函数查找离查询点最近的点，并输出结果。

这个代码示例可以在本地编译运行，需要注意的是，本示例中的四叉树实现并不是最优的，仅用于演示。在实际应用中，可能需要对四叉树的插入和查询算法进行优化。