算法5-6：Kd树

时间：2022-06-08 23:15:42

问题

给定一系列的点。和一个矩形。求矩形中包括的点的数量。

解答

这个问题能够通过建立矩阵来进行求解。首先将一个空间切割成矩阵，将点放置在相应的格子中。再计算矩形覆盖的格子。再推断格子中的点是否包括在矩形中

算法5-6：Kd树

这样的方法的问题是，可能这些点全都集中在一个格子中。

这样的情况下算法的效率比較低。

算法5-6：Kd树

watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvY2FpcGVpY2hhbzI=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="">

这样的问题在地图的应用中很常见。

算法5-6：Kd树

watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvY2FpcGVpY2hhbzI=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="">

因此须要引入2D树的概念，使得矩阵的分解会依据点的密度自己主动适应。

2D树

下图展示了2D树的样子。

算法5-6：Kd树

watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvY2FpcGVpY2hhbzI=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="">

2D树的构建

每次增加一个点时，将平面分成两半。

算法5-6：Kd树

增加第二个点时。因为第二个点在第一个点的右側，因此在第一个点的右子节点创建一个新的节点。因为父节点是竖直的，所以子节点须要水平切割。

算法5-6：Kd树

添加很多其它的点之后。就会形成例如以下的二叉树。

算法5-6：Kd树

搜索操作

搜索矩形中包括的点。

算法5-6：Kd树

搜索的时候须要从根节点開始。

从根节点知道，矩形在节点的左側。因此仅仅须要搜索左側就可以。到了点3。因为矩形覆盖了两边的区域。因此须要搜索两边。

一直迭代循环，直到节点搜索完成为止。

这样的算法的平均复杂度是logN。最坏复杂度是sqrtN。

问题

给定一系列点。和一个待測点。求与待測点近期的点。

用2D树的数据结构时，有时能够将搜索范围缩小到一半。

Kd树就是2D树的推广形式。处理二维以上的数据时很高效。

N体模拟算法

关键思想就是对于单个质点来说，将距离较远的那些点看成一个质点。

详细实现能够參考论文

http://www.cs.montana.edu/courses/spring2005/580/papers/0906008.pdf


算法5-6：Kd树的更多相关文章

  1. 从K近邻算法谈到KD树、SIFT+BBF算法

    转自 http://blog.csdn.net/v_july_v/article/details/8203674 ,感谢july的辛勤劳动 前言 前两日,在微博上说:“到今天为止,我至少亏欠了3篇文章 ...

  2. 一看就懂的K近邻算法(KNN)，K-D树，并实现手写数字识别！

    1. 什么是KNN 1.1 KNN的通俗解释 何谓K近邻算法,即K-Nearest Neighbor algorithm,简称KNN算法,单从名字来猜想,可以简单粗暴的认为是:K个最近的邻居,当K=1 ...

  3. 李航统计学习方法(第二版)（六）：k 近邻算法实现（kd树(kd tree)方法）

    1. kd树简介 构造kd树的方法如下:构造根结点,使根结点对应于k维空间中包含所有实例点的超矩形区域;通过下面的递归方法,不断地对k维空间进行切分,生成子结点.在超矩形区域(结点)上选择一个坐标轴和 ...

  4. KNN算法与Kd树

    最近邻法和k-近邻法 下面图片中只有三种豆,有三个豆是未知的种类,如何判定他们的种类? 提供一种思路,即:未知的豆离哪种豆最近就认为未知豆和该豆是同一种类.由此,我们引出最近邻算法的定义:为了判定未知 ...

  5. <转>从K近邻算法、距离度量谈到KD树、SIFT+BBF算法

    转自 http://blog.csdn.net/likika2012/article/details/39619687 前两日,在微博上说:“到今天为止,我至少亏欠了3篇文章待写:1.KD树:2.神经 ...

  6. 从K近邻算法、距离度量谈到KD树、SIFT+BBF算法

    转载自:http://blog.csdn.net/v_july_v/article/details/8203674/ 从K近邻算法.距离度量谈到KD树.SIFT+BBF算法 前言 前两日,在微博上说: ...

  7. kd树的构建以及搜索

    构建算法 k-d树是一个二叉树,每个节点表示一个空间范围.表1给出的是k-d树每个节点中主要包含的数据结构. 表1 k-d树中每个节点的数据类型 域名 数据类型 描述 Node-data 数据矢量 数 ...

  8. KD树

    k-d树 在计算机科学里,k-d树( k-维树的缩写)是在k维欧几里德空间组织点的数据结构.k-d树可以使用在多种应用场合,如多维键值搜索(例:范围搜寻及最邻近搜索).k-d树是空间二分树(Binar ...

  9. 【特征匹配】SIFT原理之KD树+BBF算法解析

    转载请注明出处:http://blog.csdn.net/luoshixian099/article/details/47606159 继上一篇中已经介绍了SIFT原理与C源代码剖析,最后得到了一系列 ...

随机推荐

  1. 利用keepalived和haproxy配置mysql的高可用负载均衡

    实验系统:CentOS 6.6_x86_64(2.6.32-504.30.3.el6.x86_64) 实验前提:防火墙和selinux都关闭 实验说明:本实验共有4台主机,IP分配如拓扑 实验软件:k ...

  2. Log4j具体使用实例

    首先,下载log4j.jar架包(网上很多,随便下载一个就可以了), 第一步:新建java项目,Testlog4j,再在src中建立com.Testlog4j包,再建一个testlog4j.java文 ...

  3. shiro权限控制方式

    1.基于配置文件(*.ini)[常用jdbcRealm.ini] 2.基于注解的配置 3.基于jsp标签的配置(需要导入对应的标签jar包) 权限包含: 是否为特定用户 是否为特定角色 是否拥有特定操 ...

  4. shell变量的替换，命令的替换，转义字符

    1,shell变量的替换 变量可以根据变量是否为空或者被删除,而被替换为特定的值 ${var}  变量本来的值 $(var:-word)   如果变量为空,或者已被删除那么返回word,但是不改变va ...

  5. headfirst设计模式（8）—适配器模式与外观模式

    前言 这一章主要讲2个模式,一个是,适配器模式(负责将一个类的接口适配成用户所期待的),另外一个是外观模式(为子系统提供一个共同的对外接口),看完的第一反应是,为什么要把它们两放在同一章,难道它们有什 ...

  6. HDU6333 Harvest of Apples （杭电多校4B）

    这莫队太强啦 先推公式S(n,m)表示从C(n, 0) 到 C(n, m)的总和 1.S(n, m)   = S(n, m-1) + C(n, m) 这个直接可以转移得到 2.S(n, m)   = ...

  7. poj 3273"Monthly Expense"(二分搜索+最小化最大值)

    传送门 https://www.cnblogs.com/violet-acmer/p/9793209.html 题意: 有 N 天,第 i 天会有 a[ i ] 的花费: 将这 N 天分成 M 份,每 ...

  8. Qt中关于QMouseEventbuttons()和QMouseEventbutton()的使用注意

    在进行QT程序开发中经常需要响应鼠标事件,在QWidget或QMainWindow的子类中可以重载如下鼠标事件实现自己需要的效果. virtual void mouseDoubleClickEvent ...

  9. Python2.7-functools

    functools 模块,是一个高阶函数模块,很有用,尤其是 partial 函数(类似函数定义了默认参数)和装饰器属性更新函数.装饰器在实现的时候,被修饰后的函数其实已经是另外一个函数了(函数名等函 ...

  10. android中ImageView的ScaleType属性

    android中ImageView的ScaleType属性 ScaleType的值分别代表的意义: ImageView是Android中的基础图片显示控件,该控件有个重要的属性是ScaleType,该 ...

相关文章