使用KD-Tree树查找最近邻点 - 二维

简介: 使用KD-Tree树查找最近邻点 - 二维

KD-Tree


介绍


kd-tree,是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。 主要应用于多维空间关键数据的搜索(如:范围搜索和最近邻搜索)。K-D树是二进制空间分割树的特殊的情况。

用法


QT图形视图框架绘制曲线图和Smith图_qtcreator画smith图-CSDN博客 在这篇博客中绘图的mark点支持,最初我是使用set的自排序功能来查找最近的点,虽然效率能跟得上使用,但是这种方式弊端非常明显。每次移动的时候就需要重写计算距离,然后重新生成这个set。这个方式浪费不仅浪费空间也浪费时间。


所以在后续更新的时候使用了KD-Tree做了最邻近点的计算,比上述暴力的的排序方式快了不止30倍(这里是只测试了4W个点,使用排序打印的ms为0,使用上面的方式打印的在30左右)。


接下来展示我的代码:


kdtree.h

#ifndef TURBOPLOT_KDTREE_H
#define TURBOPLOT_KDTREE_H

/******************************************************************
 * @brief     求最邻近点算法
 * @author    turbo
 * @class     KDTree
 * @date      2023年11月2日10:59:27
 * @version   0.0.1
 * @property  root_            kdtree跟节点
 ******************************************************************/

#include <QPointF>
#include <QVector>

namespace turbo
{
    class KDTree
    {
    public:
        struct KDTreeNode
        {
            QPointF      point;
            KDTreeNode*  left;
            KDTreeNode*  right;
        };
        KDTree();
        ~KDTree();
        /**
         * @brief 设置点,根据点生成对应的KDTree
         * @param points
         */
        void setPoints(QVector<QPointF> &points);
        /**
         * @brief 获取离入参点最近的点
         * @param point
         * @return
         */
        QPointF getNearestPoint(const QPointF &point);

    protected:
        /**
         * @brief 计算两个点之间的欧氏距离
         * @param point1
         * @param point2
         * @return
         */
        static double euclideanDistance(const QPointF& point1, const QPointF& point2);
        /**
         * @brief 根据两个点的x比较大小
         * @param point1
         * @param point2
         * @return
         */
        static bool compareX(const QPointF& point1, const QPointF& point2);
        /**
         * @brief 根据两个点的y比较大小
         * @param point1
         * @param point2
         * @return
         */
        static bool compareY(const QPointF& point1, const QPointF& point2);
        /**
         * @brief 构建KD树
         * @param points
         * @param compareX
         * @return
         */
        KDTreeNode* buildKdTree(QVector<QPointF>& points, int depth);
        /**
         * @brief 计算最邻近点
         * @param root
         * @param target
         * @param nearest
         * @param minDist
         * @param depth
         */
        void findNearestNeighbor(KDTreeNode* root, QPointF target, QPointF& nearest, double& minDist, int depth);
        /**
         * @brief 清理kdtree 释放空间
         * @param root
         */
        void clearKdTree(KDTreeNode* root);

    private:
        KDTreeNode *root_;
    };
}

#endif //TURBOPLOT_KDTREE_H


kdtree.cpp

#include "kdtree.h"
#include <algorithm>
#include <cmath>

namespace turbo
{
    KDTree::KDTree() : root_(nullptr)
    {

    }

    KDTree::~KDTree()
    {
        clearKdTree(root_);
    }

    // 清理KD树
    void KDTree::clearKdTree(KDTreeNode* root)
    {
        if (root == nullptr)
        {
            return;
        }
        clearKdTree(root->left);
        clearKdTree(root->right);
        delete root;
        root = nullptr;
    }

    double KDTree::euclideanDistance(const QPointF &point1, const QPointF &point2)
    {
        double dx = point1.x() - point2.x();
        double dy = point1.y() - point2.y();
        return std::sqrt(dx*dx + dy*dy);
    }

    bool KDTree::compareX(const QPointF &point1, const QPointF &point2)
    {
        return point1.x() < point2.x();
    }

    bool KDTree::compareY(const QPointF &point1, const QPointF &point2)
    {
        return point1.y() < point2.y();
    }

    KDTree::KDTreeNode *KDTree::buildKdTree(QVector<QPointF> &points, int depth)
    {
        if (points.isEmpty())
        {
            return nullptr;
        }
        // 根据分割轴对点进行排序
        if (depth % 2 == 0)
        {
            std::sort(points.begin(), points.end(), compareX);
        }
        else
        {
            std::sort(points.begin(), points.end(), compareY);
        }

        // 选择中间点作为根节点
        int mid = points.size() / 2;
        auto* root = new KDTreeNode();
        root->point = points[mid];
        QVector<QPointF> points1 = QVector<QPointF>(points.begin(), points.begin() + mid);
        QVector<QPointF> points2 = QVector<QPointF>(points.begin() + mid + 1, points.end());
        root->left = buildKdTree(points1, depth + 1);
        root->right = buildKdTree(points2, depth + 1);
        return root;
    }

    // 在KD树中查找最近邻点
    void KDTree::findNearestNeighbor(KDTree::KDTreeNode* root, QPointF target, QPointF& nearest, double& minDist, int depth)
    {
        if (root == nullptr)
        {
            return;
        }
        // 计算当前节点到目标点的欧氏距离
        double dist = euclideanDistance(root->point, target);
        // 如果当前节点更近,则更新最近邻点和最小距离
        if (dist < minDist)
        {
            nearest = root->point;
            minDist = dist;
        }
        // 根据深度选择分割轴
        int axis = depth % 2;
        // 根据分割轴比较目标点和当前节点,并决定遍历顺序
        if ((axis == 0 && target.x() < root->point.x()) || (axis == 1 && target.y() < root->point.y()))
        {
            findNearestNeighbor(root->left, target, nearest, minDist, depth + 1);
            if ((axis == 0 && target.x() + minDist >= root->point.x()) || (axis == 1 && target.y() + minDist >= root->point.y()))
            {
                findNearestNeighbor(root->right, target, nearest, minDist, depth + 1);
            }
        }
        else
        {
            findNearestNeighbor(root->right, target, nearest, minDist, depth + 1);
            if ((axis == 0 && target.x() - minDist <= root->point.x()) || axis == 1 && target.y() - minDist <= root->point.y())
            {
                findNearestNeighbor(root->left, target, nearest, minDist, depth + 1);
            }
        }
    }

    void KDTree::setPoints(QVector<QPointF> &points)
    {
        clearKdTree(root_);
        root_ = buildKdTree(points, 0);
    }

    QPointF KDTree::getNearestPoint(const QPointF &point)
    {
        QPointF nearest;
        double minDist = std::numeric_limits<double>::max();
        // 在KD树中查找最近邻点
        findNearestNeighbor(root_, point, nearest, minDist, 0);
        return nearest;
    }
}


这里面就说一下构建时候的思路和查找时候的思路


KD-Tree的构建

KDTree::KDTreeNode *KDTree::buildKdTree(QVector<QPointF> &points, int depth)
{
    if (points.isEmpty())
    {
        return nullptr;
    }
    // 根据分割轴对点进行排序
    if (depth % 2 == 0)
    {
        std::sort(points.begin(), points.end(), compareX);
    }
    else
    {
        std::sort(points.begin(), points.end(), compareY);
    }

    // 选择中间点作为根节点
    int mid = points.size() / 2;
    auto* root = new KDTreeNode();
    root->point = points[mid];
    QVector<QPointF> points1 = QVector<QPointF>(points.begin(), points.begin() + mid);
    QVector<QPointF> points2 = QVector<QPointF>(points.begin() + mid + 1, points.end());
    root->left = buildKdTree(points1, depth + 1);
    root->right = buildKdTree(points2, depth + 1);
    return root;
}


  1. 检查点集是否为空,如果是则返回空指针。
  2. 根据当前深度选择分割轴,偶数深度使用compareX函数排序,奇数深度使用compareY函数排序。
  3. 选择中间点作为根节点,并创建一个新的KDTreeNode对象来存储该点。
  4. 将点集分为两部分,分别是从起始位置到中间位置的点集points1和从中间位置+1到结束位置的点集points2。
  5. 递归地调用buildKdTree函数来构建左子树,并将其赋值给根节点的left指针。
  6. 递归地调用buildKdTree函数来构建右子树,并将其赋值给根节点的right指针。


这么做的主要目的就是将一整个区域分成不同的区域


最邻近点的查找

// 在KD树中查找最近邻点
void KDTree::findNearestNeighbor(KDTree::KDTreeNode* root, QPointF target, QPointF& nearest, double& minDist, int depth)
{
    if (root == nullptr)
    {
        return;
    }
    // 计算当前节点到目标点的欧氏距离
    double dist = euclideanDistance(root->point, target);
    // 如果当前节点更近,则更新最近邻点和最小距离
    if (dist < minDist)
    {
        nearest = root->point;
        minDist = dist;
    }
    // 根据深度选择分割轴
    int axis = depth % 2;
    // 根据分割轴比较目标点和当前节点,并决定遍历顺序
    if ((axis == 0 && target.x() < root->point.x()) || (axis == 1 && target.y() < root->point.y()))
    {
        findNearestNeighbor(root->left, target, nearest, minDist, depth + 1);
        if ((axis == 0 && target.x() + minDist >= root->point.x()) || (axis == 1 && target.y() + minDist >= root->point.y()))
        {
            findNearestNeighbor(root->right, target, nearest, minDist, depth + 1);
        }
    }
    else
    {
        findNearestNeighbor(root->right, target, nearest, minDist, depth + 1);
        if ((axis == 0 && target.x() - minDist <= root->point.x()) || axis == 1 && target.y() - minDist <= root->point.y())
        {
            findNearestNeighbor(root->left, target, nearest, minDist, depth + 1);
        }
    }
}

这里注释都写的很清楚了,本质上就是递归查找。这边要说明白得绘图了,单纯用文字描述的话,确实有点不太清楚。但是我绘图技术太菜,直接看代码理解吧。

判断的地方,因为之前划分的时候就是按照深度划分的,这里根据深度来决定是使用x还是y来找最近点。

目录
相关文章
|
机器学习/深度学习 算法 PyTorch
RPN(Region Proposal Networks)候选区域网络算法解析(附PyTorch代码)
RPN(Region Proposal Networks)候选区域网络算法解析(附PyTorch代码)
2444 1
|
8月前
|
机器学习/深度学习
过程奖励模型PRM成版本答案!谷歌DeepMind全自动标注逐步骤奖励PAV,准确率提升8%
研究团队提出了一种新的过程奖励模型(PRM),通过衡量每一步骤的进展来改进大型语言模型(LLM)的推理能力。与仅在最后提供反馈的结果奖励模型(ORM)不同,PRM能在多步骤推理中逐步提供反馈,从而改善信用分配。研究引入了过程优势验证者(PAV),用于预测证明策略下的进展,显著提升了测试时间搜索和在线强化学习(RL)的效率与准确性。实验表明,PAV相比ORM提高了8%以上的准确性和5至6倍的样本效率。该方法在Gemma2模型上得到了验证,并展示了在解决复杂问题上的潜力。尽管成果显著,但仍需进一步研究以优化证明策略的设计和减少拟合误差。
306 97
|
数据可视化 jenkins vr&ar
python3用ARIMA模型进行时间序列预测
python3用ARIMA模型进行时间序列预测
|
Linux Shell API
在Linux中,如何判断一个进程是否存活,如果不存活,如何告实现警?
在Linux中,如何判断一个进程是否存活,如果不存活,如何告实现警?
|
Ubuntu 安全 测试技术
Ubuntu 22.04 Samba 安装和配置
SMB(Server Message Block)是一种跨平台的文件共享协议,它允许不同操作系统之间的文件和打印机共享。在本文中,我们将详细介绍如何在 Ubuntu 服务器上部署和配置一个 SMB 服务器,并涵盖多通道配置、性能测试、安全最佳实践以及一些常见问题。【8月更文挑战第1天】
1965 1
|
存储 SQL 测试技术
Entity Framework Core 中的存储过程超厉害!从定义到调用全攻略,提升性能与安全性!
【8月更文挑战第31天】在现代软件开发中,数据库操作效率至关重要。Entity Framework Core(EF Core)作为强大的对象关系映射(ORM)框架,支持存储过程,可提升数据库操作的性能、安全性和可维护性。本文详细介绍如何在 EF Core 中定义、配置及调用存储过程,并提供最佳实践建议,包括性能优化、安全性增强、代码可维护性提升以及参数化查询等。通过遵循这些指导原则,开发者能够充分利用存储过程的优势,显著提高应用程序质量和性能。附带完整示例代码,展示从定义实体类到调用存储过程的全过程。
706 0
|
缓存 搜索推荐 应用服务中间件
|
前端开发 JavaScript 程序员
你真的会用三元运算符吗?
你真的会用三元运算符吗?
215 0