概述
图例
- 可以看到，4叉树把2D空间中的三角形进行了分组
4叉树简介
- 定义
- 把2D空间均等划分，管理空间中物体的树状数据结构
- 功能
- 定位空间中一点所在区域
- 定位空间中某个多边形所在区域
- 获取某个区域下的物体
- 应用
- 物理引擎中，用于碰撞检测系统中的粗略物理碰撞判断过程使用4叉树减少不必要的碰撞检测
- 渲染系统中，扩展4叉树为8叉树，用于剔除空间中不需要渲染的物体
4叉树基本操作
- 插入
- 插入一个物体，插入时分割空间直到能容纳改物体的最小空间，插入该物体到结点
- if 这个节点是能容纳该物体的最小节点，放入这个节点
- else 分割这个节点，找到合适的子节点执行插入操作
- 插入一个物体，插入时分割空间直到能容纳改物体的最小空间，插入该物体到结点
- 删除
- 找到该物体的所属的结点，删除该物体，如果结点不再包含物体并且不含有叶子节点，删除该节点
- 获取给定物体在节点中的空间划分
- 获取给定物体在当前节点的空间信息，即4象限信息
- 查询是否包含给定物体
4叉树扩展
- 更新
- 当物体的位置、大小发生变化，更新4叉树中该物体的信息
- 一般是删除该物体后重新插入
- 获取某节点下所有物体
白话四叉树
- 均等划分空间，用树状结构代表这些被分割的空间节点。把空间中的物体放到对应所属的空间中。
- 查询时只需要知道要查询哪个空间下的节点，遍历这个节点下的物体即可，减少了查询数，提升了性能
下一篇是四叉树的应用和实现
- 四叉树应用、实现
最后
以上就是笨笨小虾米为你收集整理的四叉树(QuadTree)原理的全部内容，希望文章能够帮你解决四叉树(QuadTree)原理所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
![同余最短路(总结)同余最短路(总结)P3403 跳楼机P2371 [国家集训队]墨墨的等式GYM100753 M-Sums](/uploads/reation/bcimg3.png)
发表评论 取消回复