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)系列,能满足大多数使用异常的场景,但对…...
React hook之useRef
React useRef 详解 useRef 是 React 提供的一个 Hook,用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途,下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望
文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例:使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例:使用OpenAI GPT-3进…...
css3笔记 (1) 自用
outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size:0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格ÿ…...

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包
文章目录 现象:mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时,可能是因为以下几个原因:1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...
探索Selenium:自动化测试的神奇钥匙
目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...

【Linux手册】探秘系统世界:从用户交互到硬件底层的全链路工作之旅
目录 前言 操作系统与驱动程序 是什么,为什么 怎么做 system call 用户操作接口 总结 前言 日常生活中,我们在使用电子设备时,我们所输入执行的每一条指令最终大多都会作用到硬件上,比如下载一款软件最终会下载到硬盘上&am…...
Modbus RTU与Modbus TCP详解指南
目录 1. Modbus协议基础 1.1 什么是Modbus? 1.2 Modbus协议历史 1.3 Modbus协议族 1.4 Modbus通信模型 🎭 主从架构 🔄 请求响应模式 2. Modbus RTU详解 2.1 RTU是什么? 2.2 RTU物理层 🔌 连接方式 ⚡ 通信参数 2.3 RTU数据帧格式 📦 帧结构详解 🔍…...

【Linux】Linux安装并配置RabbitMQ
目录 1. 安装 Erlang 2. 安装 RabbitMQ 2.1.添加 RabbitMQ 仓库 2.2.安装 RabbitMQ 3.配置 3.1.启动和管理服务 4. 访问管理界面 5.安装问题 6.修改密码 7.修改端口 7.1.找到文件 7.2.修改文件 1. 安装 Erlang 由于 RabbitMQ 是用 Erlang 编写的,需要先安…...

《信号与系统》第 6 章 信号与系统的时域和频域特性
目录 6.0 引言 6.1 傅里叶变换的模和相位表示 6.2 线性时不变系统频率响应的模和相位表示 6.2.1 线性与非线性相位 6.2.2 群时延 6.2.3 对数模和相位图 6.3 理想频率选择性滤波器的时域特性 6.4 非理想滤波器的时域和频域特性讨论 6.5 一阶与二阶连续时间系统 6.5.1 …...

边缘计算网关提升水产养殖尾水处理的远程运维效率
一、项目背景 随着水产养殖行业的快速发展,养殖尾水的处理成为了一个亟待解决的环保问题。传统的尾水处理方式不仅效率低下,而且难以实现精准监控和管理。为了提升尾水处理的效果和效率,同时降低人力成本,某大型水产养殖企业决定…...