四叉树(QuadTree)原理
4叉树简介定义把2D空间均等划分,管理空间中物体的树状数据结构功能定位空间中一点所在区域定位空间中某个多边形所在区域获取某个区域下的物体应用物理引擎中,用于碰撞检测系统中的粗略物理碰撞判断过程使用4叉树减少不必要的碰撞检测渲染系统中,扩展4叉树为8叉树,用于剔除空间中不需要渲染的物体4叉树基本操作插入插入一个物体,插入时分割空间直到能容纳改物体的最小空间,插入该物体到结点if 这个节点是能容纳该物体的最小节点,放入这个节点else 分割这个节点,找到合