數據結構與算法--四叉樹（javascript實現）

xbynet 發布于2019-08-21 12:17 / 1859人閱讀

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

   最近想要研究研究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.");

用四叉樹查找某一對象
未完待續......

參考
- 四叉樹與八叉樹

云服務器 GPU云服務器四叉樹二叉樹算法實現二叉樹最優二叉樹算法圖

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/87530.html

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

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

pepperwang 2019-08-20 15:32 評論0 收藏0
高仿 ios 相冊地圖功能

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

pakolagij 2019-08-15 10:56 評論0 收藏0
下一代的 3D Tiles 前瞻

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

魏明 2021-11-24 09:39 評論0 收藏0
JavaScript 數據結構與算法之美 - 非線性表中的樹、堆是干嘛用的？其數據結構是怎樣的？

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

singerye 2019-08-26 10:09 評論0 收藏0