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

xbynet 发布于2019-08-21 12:17 / 1822人阅读

摘要：最近想要研究研究地形的渲染，然后就想起了四叉树，在网上看了一篇相关的文章，准备拿实现一下备用。四叉树的定义是它的每个节点下至多可以有四个子节点，通常把一部分二维空间细分为四个象限或区域并把该区域里的相关信息存入到四叉树节点中。

   最近想要研究研究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云服务器四叉树二叉树算法实现二叉树最优二叉树算法图

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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