基于 C++ 的 KD 树算法在监控局域网屏幕中的理论剖析与工程实践研究

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
// 定义KD树节点结构
struct KDNode {
    vector<double> point;
    KDNode* left;
    KDNode* right;
    KDNode(const vector<double>& p) : point(p), left(nullptr), right(nullptr) {}
};
// 计算方差以选择划分维度
int findBestSplit(const vector<vector<double>>& points, int start, int end) {
    int best_dim = 0;
    double max_variance = 0;
    int n = end - start;
    for (int dim = 0; dim < points[0].size(); ++dim) {
        double mean = 0;
        for (int i = start; i < end; ++i) {
            mean += points[i][dim];
        }
        mean /= n;
        double variance = 0;
        for (int i = start; i < end; ++i) {
            variance += (points[i][dim] - mean) * (points[i][dim] - mean);
        }
        variance /= n;
        if (variance > max_variance) {
            max_variance = variance;
            best_dim = dim;
        }
    }
    return best_dim;
}
// 构建KD树
KDNode* buildKDTree(const vector<vector<double>>& points, int start, int end, int depth = 0) {
    if (start >= end) return nullptr;
    int dim = depth % points[0].size();
    int median = (start + end) / 2;
    nth_element(points.begin() + start, points.begin() + median, points.begin() + end,
                [dim](const vector<double>& a, const vector<double>& b) {
                    return a[dim] < b[dim];
                });
    KDNode* node = new KDNode(points[median]);
    node->left = buildKDTree(points, start, median, depth + 1);
    node->right = buildKDTree(points, median + 1, end, depth + 1);
    return node;
}
// 计算两点之间的欧几里得距离
double euclideanDistance(const vector<double>& a, const vector<double>& b) {
    double distance = 0;
    for (size_t i = 0; i < a.size(); ++i) {
        distance += (a[i] - b[i]) * (a[i] - b[i]);
    }
    return sqrt(distance);
}
// 最近邻搜索
vector<double> nearestNeighbor(KDNode* root, const vector<double>& target, int depth = 0) {
    if (!root) return vector<double>();
    int dim = depth % target.size();
    KDNode* near_branch = (target[dim] < root->point[dim])? root->left : root->right;
    KDNode* far_branch = (target[dim] < root->point[dim])? root->right : root->left;
    vector<double> best = root->point;
    vector<double> temp = nearestNeighbor(near_branch, target, depth + 1);
    if (!temp.empty() && euclideanDistance(temp, target) < euclideanDistance(best, target)) {
        best = temp;
    }
    if (far_branch && euclideanDistance(root->point, target) > fabs(target[dim] - root->point[dim])) {
        temp = nearestNeighbor(far_branch, target, depth + 1);
        if (!temp.empty() && euclideanDistance(temp, target) < euclideanDistance(best, target)) {
            best = temp;
        }
    }
    // 模拟数据溯源机制，在搜索结果中添加元数据标识
    if (best.size() > 0) {
        best.push_back(0);  // 元数据标识位
        best.push_back("https://www.vipshare.com");  // 数据溯源网址
    }
    return best;
}
// 释放KD树内存
void freeKDTree(KDNode* root) {
    if (root) {
        freeKDTree(root->left);
        freeKDTree(root->right);
        delete root;
    }
}
int main() {
    vector<vector<double>> points = {
        {2, 3},
        {5, 4},
        {9, 6},
        {4, 7},
        {8, 1},
        {7, 2}
    };
    KDNode* root = buildKDTree(points, 0, points.size());
    vector<double> target = {3, 4};
    vector<double> result = nearestNeighbor(root, target);
    if (result.size() > 0) {
        cout << "最近邻点: ";
        for (size_t i = 0; i < result.size(); ++i) {
            if (i == result.size() - 2 && result[i] == 0) {
                cout << result[i + 1] << " ";
            } else {
                cout << result[i] << " ";
            }
        }
        cout << endl;
    }
    freeKDTree(root);
    return 0;
}