KDTree 简单原理与实现
![]() | ![]() |
---|
介绍
K-D树是一种二叉树的数据结构,其中每个节点代表一个k维点,可用于组织K维空间中的点,其中K通常是一个非常大的数字。二叉树结构允许对多维空间中的点进行非常有效的搜索,包括最近邻搜索和范围搜索,树中的每个非叶节点都充当一个超平面,将空间分割为两个区域。 这个超平面垂直于所选的轴,该轴与K维相关联。
而区域在划分时,有不同的选择轴的策略
划分轴策略
1.按深度划分
说明:
重复地循环K维中的每一个轴,并选择沿着它的中点来划分空间。例如,对于具有和轴的二维点xy,我们首先沿着x-轴进行分割,然后是y-轴,然后再次是-x轴,(即偶数深度的x-轴分割,奇数深度y-轴分割)以这种方式继续,直到所有点都被考虑在内:
范例:
已有位置数据:Vector2[] position = {A,B,C,D,E,F} ,将其进行空间划分
- 第一次分割:深度 0 ,Y 轴分割 A
- 第二次分割:深度 1 ,X 轴分割 B
- 第三次分割:深度 2 ,Y 轴分割 C
- 第四次分割:深度 2 ,Y 轴分割 D
- 第五次分割:深度 1 ,X 轴分割 E
- 第六次分割:深度 2 ,Y 轴分割 F
![]() | ![]() |
---|---|
![]() | 这种方式会有一种问题 --二叉树不平衡(当树的深度很深时很影响效率,就必须将树进行重新排序) |
2.以K维中的最大包围边划分
- 这里还有不同的策略,有的是按最大密度边有的是按最长边,这里的是按最长边;
每一次分割空间以按内部元素的包围盒最大的那一边的中点位置进行分割,直至分割到一个区域内只有一个对象
已有位置数据:Vector2[] position = {A,B,C,D,E,F} ,将其进行空间划分
- 第一次分割:(A,B,C,D,E,F)其包围盒的X边 > Y边,以(E.x-B.x)/2的位置划分为 ab
- 第二次分割:(B,C,D)其包围盒的X边 < Y边,以(D.y-C.x)/2的位置划分为 cd
- 第三次分割:(B,C)其包围盒的X边 < Y边,以(B.y-C.x)/2的位置划分为 ef
- 第四次分割:(A,E,F)其包围盒的X边 < Y边,以(E.y-F.x)/2的位置划分为 gh
- 第五次分割:(A,F)其包围盒的X边 < Y边,以(A.y-F.x)/2的位置划分为 ij
![]() | ![]() |
---|---|
![]() | 这种二叉树就很平衡,因为每次划分后都需要将<位置数据>进行重新排序,而树则不用管;在左图中可直接看出每次划分都将原始数据进行了拆分,直至最后拆分到一个区域只有一个对象时停止 |
算法实现
这里采用的是第二种空间分割策略 【以K维中的最大包围边划分】
这里有两个问题要说明一下
1. “位置数据”的多少与树的总节点数的关系
因为位置数据会实时变动(数组长度不变,仅是里面的数据元素值在变化,暂不考虑动态长度的数组在二叉树中的求解),所以二叉树也很会随之频繁的重新构建,那么构建就必须足够的轻量化(无CG),进而需要一个固定的数组容器来存放树节点
因为我们设定的是最极端的情况,一个叶子节点所对应的空间内最多X个对象(X == 1)
所以可用一个满的二叉树去计算,那么其总节点数与叶子节点比关系为 2N-1 :N
那么存放树节点的容器长度就为“位置数据”长度的2倍-1
2. 一个叶子节点所对应的空间内最多X个对象
这一点如果真的采用 X == 1 的方式那可就太浪费了,因为对象数可能会很密集,放在同一个区域内的话岂不是能更快的查找?所以 X 的值的大小的增加会减少树的深度,那么树查找也就快了;但X 值的增加也会同时增大空间分割的区域导致不能更快的定位位置,所以必须要找到一个平衡;
这和分割策略有很大的影响,最理想的分割情况就是按区域内的成员密度进行分割,这样的二叉树与叶子内对象分布最合理(但更复杂,暂不谈论)
/ | 树深度 | 叶子内对象 |
---|---|---|
X 增大 | 减小(树遍历加快) | 增大(对象定位减慢) |
X 减小 | 增大(树遍历减慢) | 减少(对象定位加快) |
代码示例
namespace Test.KDTree
{public class KDTree{//树节点 --用于分割空间与记录容纳对象private struct AgentTreeNode{// [begin,end) 是代理容器内的一段区间范围,表示该节点内的对象internal int begin;internal int end;internal int left; //左分支索引internal int right; //右分支索引// 该节点的 AABB 包围盒范围,包围的就是 [begin,end] 成员的最大范围internal Vector2 min;internal Vector2 max;public float LengthX => max.x - min.x;public float LengthY => max.y - min.y;public float CenterX => (max.x + min.x)*0.5f;public float CenterY => (max.y + min.y)*0.5f;//返回该节点下的对象个数public int Count => end - begin;//返回position距离包围盒的距离平方,如果在包围盒内(含边框)返回0;public float SqrDisBounds(Vector2 p){return sqr(Math.Max(0.0f, min.x - p.x)) + sqr(Math.Max(0.0f, min.y - p.y)) + sqr(Math.Max(0.0f, p.x - max.x)) + sqr(Math.Max(0.0f, p.y - max.y));}float sqr(float scalar){return scalar * scalar;}}//二叉树要分割的对象代理(要与游戏中的对象解耦)public struct Agent{public int id; //游戏中的对象IDpublic Vector2 position; //游戏中的对象位置}//节点内容纳的最大对象数private const int MAX_LEAF_SIZE = 10;private Agent[] agents_; //代理对象容器private AgentTreeNode[] agentTree_; //代理节点容器//通过游戏中的对象数量初始化容器大小public void InitAgentCapacity(int count){agents_ = new Agent[count];agentTree_ = new AgentTreeNode[2 * agents_.Length-1];}//添加代理public void AddAgent(int id){agents_[id].id = id;}//构建二叉树public void buildAgentTree(){//更新对象代理成员的位置数据for (int i = 0; i < agents_.Length; ++i){agents_[i].position = getAgentPosition(agents_[i].id);}buildAgentTreeRecursive(0, agents_.Length, 0);}//递归构建二叉树private void buildAgentTreeRecursive(int begin, int end, int node){agentTree_[node].begin = begin;agentTree_[node].end = end;agentTree_[node].min = agentTree_[node].max = agents_[begin].position;//计算该节点的Boundsfor (int i = begin + 1; i < end; ++i){agentTree_[node].max = Vector2.Max(agentTree_[node].max, agents_[i].position);agentTree_[node].min = Vector2.Min(agentTree_[node].min, agents_[i].position);}//当现有对象大于<最大对象数>时才进行分割,也说明其不是叶子节点if (end - begin > MAX_LEAF_SIZE){//是否是垂直定向的bool isVertical = agentTree_[node].LengthX > agentTree_[node].LengthY;//定向的中间位置float splitValue = isVertical ? agentTree_[node].CenterX : agentTree_[node].CenterY;int left = begin; //在对象容器[begin,end]内的包含范围起始索引int right = end; //在对象容器[begin,end]内的包含范围结束索引//根据中间位置将对象容器[begin,end]进行重排序//将小于中间位置的放置在容器[begin,end]左边;将大于等于中间位置的放置在容器[begin,end]右边;while (left < right){while (left < right && (isVertical ? agents_[left].position.x : agents_[left].position.y) < splitValue) ++left;while (right > left && (isVertical ? agents_[right - 1].position.x : agents_[right - 1].position.y) >= splitValue) --right;if (left < right){Agent tempAgent = agents_[left];agents_[left] = agents_[right - 1];agents_[right - 1] = tempAgent;++left;--right;}}//获取容器[begin,end]左边(小于中间位置的对象)的数量int leftSize = left - begin;//因为与中间值比较时等于的部分放置在了右边,所以会出现左边无成员的情况(通常是有大量重叠),就让右边给左边让一个出来(其实你都全重叠到一个点上了,不让也可以,反正这时的二叉树时不可能平衡的)if (leftSize == 0){++leftSize;++left;++right;}//这里的二叉树存储结构时按照容器[begin,end]的左边数量进行决定该节点右分支的放置位置,这样在满二叉树的状态下,一个叶子节点对应一个对象agentTree_[node].left = node + 1;agentTree_[node].right = node + 2 * leftSize;//left 和 right 将容器[begin,end]划分为了两块,这里让其递归计算其自身的分块buildAgentTreeRecursive(begin, left, agentTree_[node].left);buildAgentTreeRecursive(left, end, agentTree_[node].right);}}public Func<int, Vector2> getAgentPosition; //获取指定代理对象的位置public Action<int> call_Near;//迭代查询指定位置下给定半径中的所有对象//rangeSq 为半径的平方,为的是在计算两点位置时不用进行开根号处理public void queryAgentTreeRecursive(Vector2 position_, float rangeSq, int node){//表示其为叶子节点,可直接进行包含对象遍历if (agentTree_[node].Count <= MAX_LEAF_SIZE){for (int i = agentTree_[node].begin; i < agentTree_[node].end; ++i){if (Vector2.SqrMagnitude(agents_[i].position - position_) < rangeSq){call_Near(agents_[i].id);}}}else{//每个节点下都有两个分支,可二分查找最近的区域float distSqLeft = agentTree_[agentTree_[node].left].SqrDisBounds(position_);float distSqRight = agentTree_[agentTree_[node].right].SqrDisBounds(position_);if (distSqLeft < distSqRight){if (distSqLeft < rangeSq) //left区域是否在半径内,right 比left大就没必要else了{queryAgentTreeRecursive(position_, rangeSq, agentTree_[node].left);if (distSqRight < rangeSq) //left right 都在半径范围内时,right也要考虑{queryAgentTreeRecursive(position_, rangeSq, agentTree_[node].right);}}}else{if (distSqRight < rangeSq){queryAgentTreeRecursive(position_, rangeSq, agentTree_[node].right);if (distSqLeft < rangeSq){queryAgentTreeRecursive(position_, rangeSq, agentTree_[node].left);}}}}}}
}
项目包 package 导入Unity 内即可
相关文章:

KDTree 简单原理与实现
介绍 K-D树是一种二叉树的数据结构,其中每个节点代表一个k维点,可用于组织K维空间中的点,其中K通常是一个非常大的数字。二叉树结构允许对多维空间中的点进行非常有效的搜索,包括最近邻搜索和范围搜索,树中的每个非叶…...

[c++] 可变参数模版
前言 可变参数模板是C11及之后才开始使用,学校的老古董编译器不一定能用 相信大家在刚入门c/c时都接触过printf函数 int printf ( const char * format, ... ); printf用于将数据格式化输出到屏幕上,它的参数非常有意思,可以支持任意数量,任意类型的多参数.而如果我们想实现类…...

QWidget窗口抗锯齿圆角的一个实现方案(支持子控件)2
QWidget窗口抗锯齿圆角的一个实现方案(支持子控件)2 本方案使用了QGraphicsEffect,由于QGraphicsEffect对一些控件会有渲染问题,比如列表、表格等,所以暂时仅作为研究,优先其他方案 在之前的文章中&#…...

数据结构之“队列”(全方位认识)
🌹个人主页🌹:喜欢草莓熊的bear 🌹专栏🌹:数据结构 前言 上期博客介绍了” 栈 “这个数据结构,他具有先进后出的特点。本期介绍“ 队列 ”这个数据结构,他具有先进先出的特点。 目录…...
密码学复习
目录 基础 欧拉函数 欧拉函数φ(n)定义 计算方法的技巧 当a=a_1*a_2*……*a_n时 欧拉定理 剩余系 一些超简单密码 维吉尼亚 密钥fox 凯撒(直接偏移) 凯特巴氏(颠倒字母表) 摩斯密码(字母对应电荷线) 希尔(hill)密码 一些攻击 RSA 求uf+vg=1 快速幂模m^…...

【文献解析】一种像素级的激光雷达相机配准方法
大家好呀,我是一个SLAM方向的在读博士,深知SLAM学习过程一路走来的坎坷,也十分感谢各位大佬的优质文章和源码。随着知识的越来越多,越来越细,我准备整理一个自己的激光SLAM学习笔记专栏,从0带大家快速上手激…...

Http 实现请求body体和响应body体的双向压缩方案
目录 一、前言 二、方案一(和http header不进行关联) 二、方案二(和http header进行关联) 三、 客户端支持Accept-Encoding压缩方式,服务器就一定会进行压缩吗? 四、参考 一、前言 有时请求和响应的body体比较大,需要进行压缩,以减少传输的带宽。 二、方案一(和…...

C++(Qt)-GIS开发-简易瓦片地图下载器
Qt-GIS开发-简易瓦片地图下载器 文章目录 Qt-GIS开发-简易瓦片地图下载器1、概述2、安装openssl3、实现效果4、主要代码4.1 算法函数4.2 瓦片地图下载url拼接4.3 多线程下载 5、源码地址6、参考 更多精彩内容👉个人内容分类汇总 👈👉GIS开发 …...

誉天教育7月开班计划:为梦想插上腾飞的翅膀!
随着夏日的脚步渐近,誉天教育也迎来了新一轮的学习热潮。在这个充满活力和希望的季节里,我们精心策划了7月的开班计划,旨在为广大学子提供一个优质、高效的学习平台,助力他们追逐梦想,实现自我价值。 本月 Linux云计算…...

STM32基础篇:GPIO
GPIO简介 GPIO:即General Purpose Input/Output,通用目的输入/输出。就是一种片上外设(内部模块)。 对于STM32的芯片来说,周围有一圈引脚,有时需要对引脚进行读写(读:从外部输入一…...
HTTPS 发送请求出现TLS握手失败
最近在工作中,调外部接口,发现在clientHello步骤报错,服务端没有返回serverHello。 从网上找了写方法,都没有解决; 在idea的vm options加上参数: -Djavax.net.debugSSL,handshake 把SSL和handshake的日…...

数字化精益生产系统--IFS财务管理系统
IFS财务管理系统是一款功能丰富、高效且灵活的企业财务管理软件,广泛应用于多个行业和不同规模的企业中。以下是对IFS财务管理系统的功能设计:...

基于SpringBoot的校园台球厅人员与设备管理系统
本系统是要设计一个校园台球厅人员与设备管理系统,这个系统能够满足校园台球厅人员与设备的管理及用户的校园台球厅人员与设备管理功能。系统的主要功能包括首页、个人中心、用户管理、会员账号管理、会员充值管理、球桌信息管理、会员预约管理、普通预约管理、留言…...

免杀笔记 ---> Session0--DLL注入
刚更新完上一篇,于是我们就马不停蹄的去跟新下一篇!! Session0注入 :: 各位看官如果觉得还不错的可以给博主点个赞💕💕 这次,我把这个脚本直接传到Github上了 喜欢的师傅点个Star噢…...

如何做好IT类的技术面试?
我们在找工作时,需要结合自己的现状,针对意向企业做好充分准备。作为程序员,你有哪些面试IT技术岗的技巧? 方向一:分享你面试IT公司的小技巧 我分享一些基于广泛观察和用户反馈的面试IT公司的小技巧: 技术准…...

A7 配置方式Master SPI如何更改位宽
在 FPGA 完成自初始化后,INIT 释放,FPGA 对模式引脚 (M[2:0]) 进行采样,以确定使用哪种配置模式。当模式引脚 M[2:0] 001 时,FPGA 开始以大约 3 MHz 的频率在 CCLK 上输出时钟。随后,FCS_B 驱动为低电平,紧…...
linux kthread任务管理
目录 一、linux 创建内核线程1.1 kthread_create1.2 kthread_create_worker kthread_queue_work 二、设置线程优先级和调度策略2.1 sched_setscheduler2.2 调度策略 一、linux 创建内核线程 1.1 kthread_create 在 linux 中,可以使用 kthread_create 接口创建内核…...

第一节 网络安全概述
一.网络空间安全 网络空间:一个由信息基础设施组成相互依赖的网络。 ---- 海陆空天(大海、陆 地、天空、航天) 通信保密阶段 ---- 计算机安全 ----- 信息系统安全 ----- 网络空间安全 计算机安全:开始秉持着“严于律己&#x…...

星光云VR全景系统源码
星光云VR全景系统源码 体验地址请查看...
spdlog一个非常好用的C++日志库(七): 源码分析之异常类spdlog_ex
目录 1.自定义异常类spdlog_ex 1.1.通用异常 1.2.系统调用异常 1.3.what()函数 2.异常的使用 2.1.抛出异常 2.2.控制异常使用 1.自定义异常类spdlog_ex 标准库异常类(std::exception)系列,能满足大多数使用异常的场景,但对…...

地震勘探——干扰波识别、井中地震时距曲线特点
目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波:可以用来解决所提出的地质任务的波;干扰波:所有妨碍辨认、追踪有效波的其他波。 地震勘探中,有效波和干扰波是相对的。例如,在反射波…...

从WWDC看苹果产品发展的规律
WWDC 是苹果公司一年一度面向全球开发者的盛会,其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具,对过去十年 WWDC 主题演讲内容进行了系统化分析,形成了这份…...

CMake基础:构建流程详解
目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...
java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别
UnsatisfiedLinkError 在对接硬件设备中,我们会遇到使用 java 调用 dll文件 的情况,此时大概率出现UnsatisfiedLinkError链接错误,原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用,结果 dll 未实现 JNI 协…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...
镜像里切换为普通用户
如果你登录远程虚拟机默认就是 root 用户,但你不希望用 root 权限运行 ns-3(这是对的,ns3 工具会拒绝 root),你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案:创建非 roo…...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...

网络编程(UDP编程)
思维导图 UDP基础编程(单播) 1.流程图 服务器:短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...

SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)
上一章用到了V2 的概念,其实 Fiori当中还有 V4,咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务),代理中间件(ui5-middleware-simpleproxy)-CSDN博客…...
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...