数据结构与算法–四叉树（javascript实现）

   最近想要研究研究webgl地形的渲染，然后就想起了四叉树，在网上看了一篇相关的文章，准备拿javascript实现一下备用。

四叉树原理
（这部分就直接抄了，见参考）四叉树（Q-Tree）是一种树形数据结构。四叉树的定义是：它的每个节点下至多可以有四个子节点，通常把一部分二维空间细分为四个象限或区域并把该区域里的相关信息存入到四叉树节点中。这个区域可以是正方形、矩形或是任意形状。以下为四叉树的二维空间结构(左)和存储结构(右)示意图（注意节点颜色与网格边框颜色）：

四叉树的每一个节点代表一个矩形区域（如上图黑色的根节点代表最外围黑色边框的矩形区域），每一个矩形区域又可划分为四个小矩形区域，这四个小矩形区域作为四个子节点所代表的矩形区域。

数据结构

var QuadRect = function(left,top,right,bottom){
        this.left = left;
        this.top = top;
        this.right = right;
        this.bottom = bottom;
    };

    var QuadNode = function(){
        this.rect = null;           //所表示的矩形区域
        this.data = null;           //相关数据
        this.childs = null;         //四个子节点，没有就是null
    };

    var QuadTree = function(){
        this.root = new QuadNode();     //根节点
        this.depth = 0;                 //数的深度
    };

树的构建

    var g_tree = new QuadTree();

    /**
     * [quadTreeBuild 构建四叉树]
     * @param  {[number]} depth [输的深度]
     * @param  {[QuadRect]} rect  [数表示的矩形区域]
     */
    function quadTreeBuild(depth, rect){
        g_tree.depth = depth;

        quadCreateBranch(g_tree.root, depth, rect);
    }

    /**
     * [quadCreateBranch 递归方式创建给定节点的子节点]
     * @param  {[QuadNode]} node  [需要创建子节点的节点]
     * @param  {[type]} depth [description]
     * @param  {[type]} rect  [description]
     * @return {[type]}       [description]
     */
    function quadCreateBranch(node, depth, rect){
        if (depth !== 1) {
            node.rect = rect;
            node.childs = [new QuadNode(),new QuadNode(),new QuadNode(),new QuadNode()];

            childsRect = rectSubdivide(rect);

            quadCreateBranch(node.childs[0], depth - 1, childsRect[0]);
            quadCreateBranch(node.childs[1], depth - 1, childsRect[1]);
            quadCreateBranch(node.childs[2], depth - 1, childsRect[2]);
            quadCreateBranch(node.childs[3], depth - 1, childsRect[3]);
        }
    }

    /**
     * [rectSubdivide 给定一个矩形区域将它分为四个象限]
     * @param  {[type]} rect [description]
     * @return {[type]}      [description]
     */
    function rectSubdivide(rect){
        var firstRect = new QuadRect(
            (rect.left + rect.right)/2, rect.top, rect.right, (rect.top+rect.bottom)/2
        );
        var secondRect = new QuadRect(
            rect.left, rect.top, (rect.left + rect.right)/2, (rect.top+rect.bottom)/2
        );
        var thirdRect = new QuadRect(
            rect.left, (rect.top+rect.bottom)/2, (rect.left + rect.right)/2, rect.bottom
        );
        var fourthRect = new QuadRect(
            (rect.left + rect.right)/2, (rect.top+rect.bottom)/2, rect.right, rect.bottom
        );

        return [firstRect,secondRect,thirdRect,fourthRect];
    }



    var rect = new QuadRect(0,10,10,0);
    var depth = 5;

    quadTreeBuild(depth,rect);

    console.log('ok.');

用四叉树查找某一对象
未完待续……

参考
– 四叉树与八叉树

您可能感兴趣的文章：
数据结构与算法–四叉树（javascript实现）
Python中的树你知道吗？
数据结构中树与二叉树基础算法的比较
php 二叉树遍历算法与例子
数据结构-树和二叉树(Golang)
二叉链表表示的二叉树及基本操作
Python中的二叉排序树和平衡二叉树是什么
C 实现二叉查找树过程详解教程【图】
数据结构和算法(Golang实现)(29)查找算法-2-3树和左倾红黑树
jQuery源码分析系列