西安地区专业做网站公司,查看网站备案号,百科网站推广,深圳网页制作服务商KD树#xff08;K-Dimensional Tree#xff09;是一种用于多维空间的二叉树数据结构#xff0c;旨在提供高效的数据检索。KD树在空间搜索和最近邻搜索等问题中特别有用#xff0c;允许在高维空间中有效地搜索数据点。 重要性质 1.分割K维数据空间的数据结构 2.是一颗二叉树…KD树K-Dimensional Tree是一种用于多维空间的二叉树数据结构旨在提供高效的数据检索。KD树在空间搜索和最近邻搜索等问题中特别有用允许在高维空间中有效地搜索数据点。 重要性质 1.分割K维数据空间的数据结构 2.是一颗二叉树 3.切分维度上左子树值小于右子树值
#include iostream
#include vector
#include algorithm
#include cmath// 定义二维点的结构体
struct Point2D {double x;double y;Point2D(double _x, double _y) : x(_x), y(_y) {}
};// 定义KD树节点
struct KDTreeNode {Point2D point;KDTreeNode* left;KDTreeNode* right;KDTreeNode(Point2D _point) : point(_point), left(nullptr), right(nullptr) {}
};class KDTree {
private:KDTreeNode* root;// 构建KD树的递归函数KDTreeNode* buildKDTree(std::vectorPoint2D points, int depth) {if (points.empty()) {return nullptr;}// 选择轴线交替选择x和y坐标int axis depth % 2;// 按轴线排序点if (axis 0) {std::sort(points.begin(), points.end(), [](const Point2D a, const Point2D b) {return a.x b.x;});} else {std::sort(points.begin(), points.end(), [](const Point2D a, const Point2D b) {return a.y b.y;});}// 选择中间点作为节点int median points.size() / 2;KDTreeNode* node new KDTreeNode(points[median]);// 递归构建左子树和右子树std::vectorPoint2D leftPoints(points.begin(), points.begin() median);std::vectorPoint2D rightPoints(points.begin() median 1, points.end());node-left buildKDTree(leftPoints, depth 1);node-right buildKDTree(rightPoints, depth 1);return node;}// 在KD树中查找最近邻点的递归函数KDTreeNode* findNearestNeighbor(KDTreeNode* node, Point2D target, int depth, KDTreeNode* best, double bestDistance) {if (node nullptr) {return best;}// 计算当前节点到目标点的距离double currentDistance distance(node-point, target);// 更新最近邻点和距离if (currentDistance bestDistance) {best node;bestDistance currentDistance;}// 选择子树int axis depth % 2;KDTreeNode* nearSubtree;KDTreeNode* farSubtree;if (axis 0) {if (target.x node-point.x) {nearSubtree node-left;farSubtree node-right;} else {nearSubtree node-right;farSubtree node-left;}} else {if (target.y node-point.y) {nearSubtree node-left;farSubtree node-right;} else {nearSubtree node-right;farSubtree node-left;}}// 递归搜索更近的子树best findNearestNeighbor(nearSubtree, target, depth 1, best, bestDistance);// 如果可能搜索更远的子树if (shouldSearchFarSubtree(node, target, bestDistance)) {best findNearestNeighbor(farSubtree, target, depth 1, best, bestDistance);}return best;}// 计算两点之间的欧几里得距离double distance(Point2D a, Point2D b) {double dx a.x - b.x;double dy a.y - b.y;return std::sqrt(dx * dx dy * dy);}// 检查是否需要搜索更远的子树bool shouldSearchFarSubtree(KDTreeNode* node, Point2D target, double bestDistance) {int axis node-point.x target.x ? 0 : 1; // 如果轴线是x则比较x坐标如果轴线是y则比较y坐标double nodeDistance axis 0 ? node-point.x - target.x : node-point.y - target.y;return nodeDistance * nodeDistance bestDistance;}public:KDTree(std::vectorPoint2D points) {root buildKDTree(points, 0);}// 查找最近邻点Point2D findNearestNeighbor(Point2D target) {double bestDistance std::numeric_limitsdouble::max();KDTreeNode* bestNode findNearestNeighbor(root, target, 0, nullptr, bestDistance);return bestNode-point;}
};int main() {// 创建一些二维点std::vectorPoint2D points {{2.0, 3.0},{5.0, 4.0},{9.0, 6.0},{4.0, 7.0},{8.0, 1.0},{7.0, 2.0}};// 构建KD树KDTree kdTree(points);// 查找最近邻点Point2D target(9.0, 2.0);Point2D nearestNeighbor kdTree.findNearestNeighbor(target);std::cout The nearest neighbor to ( target.x , target.y ) is ( nearestNeighbor.x , nearestNeighbor.y ) std::endl;return 0;
}
