數(shù)據(jù)結(jié)構(gòu)與算法--四叉樹(shù)（javascript實(shí)現(xiàn)）

xbynet 發(fā)布于2019-08-21 12:17 / 1998人閱讀

摘要：最近想要研究研究地形的渲染，然后就想起了四叉樹(shù)，在網(wǎng)上看了一篇相關(guān)的文章，準(zhǔn)備拿實(shí)現(xiàn)一下備用。四叉樹(shù)的定義是它的每個(gè)節(jié)點(diǎn)下至多可以有四個(gè)子節(jié)點(diǎn)，通常把一部分二維空間細(xì)分為四個(gè)象限或區(qū)域并把該區(qū)域里的相關(guān)信息存入到四叉樹(shù)節(jié)點(diǎn)中。

   最近想要研究研究webgl地形的渲染，然后就想起了四叉樹(shù)，在網(wǎng)上看了一篇相關(guān)的文章，準(zhǔn)備拿javascript實(shí)現(xiàn)一下備用。

四叉樹(shù)原理
（這部分就直接抄了，見(jiàn)參考）四叉樹(shù)（Q-Tree）是一種樹(shù)形數(shù)據(jù)結(jié)構(gòu)。四叉樹(shù)的定義是：它的每個(gè)節(jié)點(diǎn)下至多可以有四個(gè)子節(jié)點(diǎn)，通常把一部分二維空間細(xì)分為四個(gè)象限或區(qū)域并把該區(qū)域里的相關(guān)信息存入到四叉樹(shù)節(jié)點(diǎn)中。這個(gè)區(qū)域可以是正方形、矩形或是任意形狀。以下為四叉樹(shù)的二維空間結(jié)構(gòu)(左)和存儲(chǔ)結(jié)構(gòu)(右)示意圖（注意節(jié)點(diǎn)顏色與網(wǎng)格邊框顏色）：

四叉樹(shù)的每一個(gè)節(jié)點(diǎn)代表一個(gè)矩形區(qū)域（如上圖黑色的根節(jié)點(diǎn)代表最外圍黑色邊框的矩形區(qū)域），每一個(gè)矩形區(qū)域又可劃分為四個(gè)小矩形區(qū)域，這四個(gè)小矩形區(qū)域作為四個(gè)子節(jié)點(diǎn)所代表的矩形區(qū)域。

數(shù)據(jù)結(jié)構(gòu)

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;           //所表示的矩形區(qū)域
        this.data = null;           //相關(guān)數(shù)據(jù)
        this.childs = null;         //四個(gè)子節(jié)點(diǎn)，沒(méi)有就是null
    };

    var QuadTree = function(){
        this.root = new QuadNode();     //根節(jié)點(diǎn)
        this.depth = 0;                 //數(shù)的深度
    };

樹(shù)的構(gòu)建

    var g_tree = new QuadTree();

    /**
     * [quadTreeBuild 構(gòu)建四叉樹(shù)]
     * @param  {[number]} depth [輸?shù)纳疃萞
     * @param  {[QuadRect]} rect  [數(shù)表示的矩形區(qū)域]
     */
    function quadTreeBuild(depth, rect){
        g_tree.depth = depth;

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

    /**
     * [quadCreateBranch 遞歸方式創(chuàng)建給定節(jié)點(diǎn)的子節(jié)點(diǎn)]
     * @param  {[QuadNode]} node  [需要?jiǎng)?chuàng)建子節(jié)點(diǎn)的節(jié)點(diǎn)]
     * @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 給定一個(gè)矩形區(qū)域?qū)⑺譃樗膫€(gè)象限]
     * @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.");

用四叉樹(shù)查找某一對(duì)象
未完待續(xù)......

參考
- 四叉樹(shù)與八叉樹(shù)