国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

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

xbynet / 1797人閱讀

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

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

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

四叉樹的每一個節(jié)點代表一個矩形區(qū)域（如上圖黑色的根節(jié)點代表最外圍黑色邊框的矩形區(qū)域），每一個矩形區(qū)域又可劃分為四個小矩形區(qū)域，這四個小矩形區(qū)域作為四個子節(jié)點所代表的矩形區(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;         //四個子節(jié)點，沒有就是null
    };

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

樹的構(gòu)建

    var g_tree = new QuadTree();

    /**
     * [quadTreeBuild 構(gòu)建四叉樹]
     * @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é)點的子節(jié)點]
     * @param  {[QuadNode]} node  [需要創(chuàng)建子節(jié)點的節(jié)點]
     * @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 給定一個矩形區(qū)域?qū)⑺譃樗膫€象限]
     * @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.");

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

參考
- 四叉樹與八叉樹

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/87530.html

相關(guān)文章

  • d3-force 力導(dǎo)圖 源碼解讀與原理分析【二 ： 四叉樹（一）】

    摘要：我們在上文源碼解析發(fā)現(xiàn)版的節(jié)點碰撞采用四叉樹進行了優(yōu)化。那么版本的力導(dǎo)圖具體和版的有何不同點呢，四叉樹又如何優(yōu)化碰撞校驗的呢原文鏈接被重命名為。性能的提高歸功于的新的四叉樹。 我們在上文源碼解析發(fā)現(xiàn)v4版的節(jié)點碰撞采用四叉樹進行了優(yōu)化。那么V4版本的力導(dǎo)圖具體和v3版的有何不同點呢，四叉樹又如何優(yōu)化碰撞校驗的呢？ v3-force VS v4-force https://github...

    pepperwang 評論0 收藏0

  • 高仿 ios 相冊地圖功能

    摘要：本篇文章已授權(quán)微信公眾號郭霖獨家發(fā)布老規(guī)矩先上圖最近沒有什么時間，后面項目再補上詳細說明百度地圖新增點聚合功能。百度地圖是把整個地球是按照一個平面來展開，并且通過墨卡托投影投射到坐標軸上面。上圖很明顯墨卡托投影把整張世界地圖投影成。 本篇文章已授權(quán)微信公眾號 guolin_blog （郭霖）獨家發(fā)布 老規(guī)矩先上圖最近 沒有什么時間，后面項目再補上詳細說明 showImg(https:/...

    pakolagij 評論0 收藏0

  • 下一代的 3D Tiles 前瞻

    摘要：在中，引入一些元數(shù)據(jù)方面的擴展項。不同層級的元數(shù)據(jù)像素級別樣式化渲染不同層級的元數(shù)據(jù)像素級別樣式化渲染配合使用和兩個擴展項，下一代的可以在各個層級存儲元數(shù)據(jù)。例如，水泥地和草地的摩擦系數(shù)可以作為元數(shù)據(jù)，影響車輛的行駛速度等。下一代的 3D Tiles 前瞻原文：Introducing 3D Tiles Next, Streaming Geospatial to the Metaverse原文...

    魏明 評論0 收藏0

  • JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法之美 - 非線性表中的樹、堆是干嘛用的 ？其數(shù)據(jù)結(jié)構(gòu)是怎樣的 ？

    摘要：筆者寫的數(shù)據(jù)結(jié)構(gòu)與算法之美系列用的語言是，旨在入門數(shù)據(jù)結(jié)構(gòu)與算法和方便以后復(fù)習。非線性表中的樹堆是干嘛用的其數(shù)據(jù)結(jié)構(gòu)是怎樣的希望大家?guī)е@兩個問題閱讀下文。其中，前中后序，表示的是節(jié)點與它的左右子樹節(jié)點遍歷訪問的先后順序。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言 想學好前端，先練好內(nèi)功，內(nèi)功不行，...

    singerye 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<