四叉树基本原理与简单实现

一.什么是四叉树

	四叉树（Quad Tree）是一种树形的数据结构，每个节点有且只有四个子节点。
1

二.应用场景

1.图像处理
2.空间数据索引
3.2D碰撞检测
4.稀疏数据
1
2
3
4

三.基本结构

结点基本构成

class QuadTree {
    /**当前节点包含的物体集合 */
    private _objs:Circle[] = [];
    /**单个节点最大容量 */
    private readonly _maxCapacity:number = 10;
    /**四叉树最大深度 */
    private readonly _maxDepth:number = 7;
    /**当前深度 */
    private _curDepth:number = 0;
    /**节点的矩形范围 */
    private _boundary:Rect;
	/**子节点集合**/
    private _areas:QuadTree[] = [];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

插入函数

	/** 
     * 插入
    */
    public insert(target:Circle){
        //判断当前节点范围是否包含目标点
        if(!this._boundary.contains(target.center)) return false;
        //如果当前容量维达上限 或者 当前节点已经是最大深度 则直接加入
         if(this._objs.length<this._maxCapacity || this._curDepth>=this._maxDepth){
               this._objs.push(target);
               return true;
          }
           //如果当前节点没有子节点 则划分四个子节点
           if(this._areas.length <= 0){
                this.genQTNode();
           }
           //给子节点插入该物体
           for(let i=0; i<this._areas.length;++i){
                if(this._areas[i].insert(target)) return true;
           }
           return false;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

查找函数

	/**
     * 查找
     * @param target 查找范围
     * @param result 查找结果
     */
    search(target:Circle, results?:Circle[]):Circle[]{
        if(!results) results = [];
        // 检测目标圆形是否与当前节点相交
        if (!this._boundary.contains(target.center)) return results;
        //检查当前节点内对象是否与目标对象相交
        this._objs.forEach(obj=>{
            //相交则加入列表
            if(obj.contains(target)){
                results.push(obj);
            }
        })
        // 检查子节点中是否有相交的物体
        for (let area of this._areas) {
            area.search(target, results);
        }
        return results;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

四.效果演示

应用

 update(deltaTime: number) {
        if(this.type == 1){
            this.node.getChildByName("Label").getComponent(Label).string =`圆球数量：${this.circles.length}-四叉树`;
            this.root.clear()
            this.circles.forEach(c=>{
                this.root.insert(c);
                c.color = Color.RED;
                c.move(750,520);
            })
            this.circles.forEach(c=>{
                let results =   this.root.search(c);
                //此处返回的结果已经是有碰撞的集合了 因此不必再次检测碰撞
                results.forEach(e=>{
                    if(c.uniqueId!=e.uniqueId){
                        c.color = Color.GREEN
                    }
                })
             })
        }else if(this.type == 0){
            this.node.getChildByName("Label").getComponent(Label).string =`圆球数量：${this.circles.length}-非四叉树`;
            this.circles.forEach(c=>{
               c.color = Color.RED;
               c.move(750,520);
           })

            this.circles.forEach(c=>{
                this.circles.forEach(e=>{
                    if(c.uniqueId!=e.uniqueId && c.contains(e)){
                        c.color = Color.GREEN
                    }
                })
            })
        }}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

可以看出四叉树在碰撞检测的性能上有明显的提升

1