四叉树初步研究

【JS】 四叉树初步研究

• 四叉树 为何要叫四叉树，二叉树与八叉树又是生么东东，看样子理解起来比较困难，实现该如何入手?
• 树 就是树的结构，树根、树干、树枝、树叶、…还有好吃的果实。o(￣▽￣)ブ 其实树这种结构，很常见的，JSON 不就是最普通的树吗？
• 四叉树的说明我就不写了，毕竟别人早就写过了，很多很多，看多了晕，还不如找个权威的动手写。四叉树是 空间位置属性划分 的方式。

普通JSON 平常见到的最多的数据结构，相对四叉树来说就是一叉树，这样好懂不

// 最外面这个就是 Root 节点
// 总是有一个节点装下所有节点，包括他自己（tree.root = this）
 var tree = {
	value:"xxx",
	children:[{
		value:"xxx2",
		children:[...]
	},{
		value:"xxx4",
		children:[{
			value:"xxx5",
			children:[...]
		}]
	}, ...]
}

上面代码写接口的人最常见了，来看下面四叉树的节点定义

注意，这是分支节点，并不是传统的数据节点，他们分别在两个不同的属性上，且分支节点是固定的 （四叉树就是四个，二叉树是两个）
再看看下面的 空间定义，分四个象限区域，每个区域都有自己的空间属性等

四叉树的模型就这些，其实不难，重在设计，下面来看看，代码的设计方面
ES3 ES5 JS 代码在非 ES6 或更高时 代码设计成型后，对于理解和梳理并不是最好的，先看看普通写法实例

// 四叉树的一般结构
var ForkTree = {
	state:true,
	level:1,
	left:0,top:0,right:1360,bottom:660,
	dataList:[ Shape ], // 数据节点 一般存放带有位置属性的 对象
	nodeList:[{...},{...},{...},{
		state:false,
		level:2,
		left:680,top:330,right:1360,bottom:660,
		dataList:[ Shape ],
		nodeList:[{...},{...},{...},{...}],
		//... 四叉树是四个节点 每个节点又可以继续分裂，如此往复
	}]
}
function insert( object , node ){
	// 插入到节点中
	// 这里经行 插入条件判断
}
function create( left , top ,right , bottom , level){
	// 创建一个新的空白 节点
	// 其他属性
	// parent 
	// maxcount 
}

// 其他方法
// function split(){}
// function delete( object ) {}
// function getFullNode( object , node) {}

这样写下来 看的懂，也需要自己多多练习，朝着自己需要的地方优化，简化，如果换成 ES6 的写法 ，可能会更好理解四叉树的创建过程。

class ForkTree {
	constructor(left , top , right , bottom , level){
		// 记录空间位置属性等
		this.level = level;
		this.width = right - left;
		this.height = bottom - top;
		// ...
	}
	insert(){} // 插入判断
	split(){} // 分裂 创建自己的 四个象限节点
	parent(){} 
	addShape(shape){}
	delShape(shape){}
	// ... 还有其他的一些扩展 属性 和 方法
}

嗯，看样子这样写 确实好多了，只是写到后面，方法属性都堆积在一起，工具方法也好，测量方法也好，都会增加维护和排查问题的难度
考虑到 Root 节点只有一个，且大部分插入的时候都是从第一个节点开始遍历整棵树，所以由一个 类 来当 Root 节点 用另一个 类 来表示非 Root 节点 ，更多的还可以继续将功能分类，分到不同的类中。
我的设计是把 容器和控制 尽量分开，继续看

// 控制 和 容器分离
// 普通节点
class Region {
	constructor(left , top , right , bottom , level){
		// 数据存储记录
	}
	
	parent(){}
	split(){} 
	add(shape){} 
	remove(shape){}
	isCline(l,t,r,b){} // 检查不在当前节点的中线上 
}

// Root节点 
class Tree extends Region{
	//拥有普通节点所有的功能
	constructor(width , height , maxlevel){
		super(0 , 0 , width , height , 1);
		// 初始化 Root 节点独有的一些属性
		this.maxLevel = maxlevel?maxlevel:4;
		// ...
		this.initSplit();
	}
	isLower(region){ // 是否到达最大分裂深度
		return region.level >= this.maxLevel ;
	}
	insert( shape ,region){
		if (!region) region = this;
		if (region.isCline(shape.l, shape.t, shape.r, shape.b)) return region;
		if(!region.isSplit){
			...// 如果深度到达上限 就返回 这个节点
			...// 如果当前容器内 数据长度没有突破上限 就返回这个节点
            region.isSplit = true;// 表示当前节点的子节点可要 
            // 移动数据到合适的子节点中 
            let mylist = region.list;
            region.list = [];
            for (let cur of mylist) {
                this.insert(cur).add(cur);
            }
		}
		//根据位置获取 子 域 判断是否在 子 域中线上 否则 插入
		// I II III IV 
        let vcenline = region.left + region.cenWidth;
        let hcenline = region.ttop + region.cenHeight;
        if (vcenline > shape.right) { // node 节点具体存储在那个属性中自己定义
            if (hcenline > shape.bottom) { 	// lt II
                return this.insert(shape, region.node[1]);
            } else { 					// lb III
                return this.insert(shape, region.node[2]);
            }
        } else {
            if (hcenline > shape.bottom) { 	// rt I
                return this.insert(shape, region.node[0]);
            } else { 					// rb IV
                return this.insert(shape, region.node[3]);
            }
        }
	} 
	
	this.initSplit(region){ // 初始化整棵树的节点
		if(this.isLower(region))  return; //停止分裂
		for(let item of region.node) item .split();
	}
}

功能这样分开后，普通节点就主要做好数据存储，一些简单的方法接口等，其他高级的插入，查询，维护等功能都放在 Tree 类中。
像工具方法（位置计算，密度技术等）可以写成新的类，或者写成静态方法，这样语意会更加清晰易懂，便于维护扩展。
上面代码仅供参考，已经有现成的，可供后续深入研究，基本可以跑，会省去很多事情，请看后续的 demo 代码
自定义链表 + 自定义四叉树 初步实现，链表可使用 for of 循环
Chain.JS 自定义链表 此链表设计方向是 多个链表之间的数据移动，而不是数据复制

"use strict";
// 链定义
class Chain {
    constructor() {
        this.lower = new Clasp("end");
        this.top = new Clasp("start");
        this.top.setNext(this.lower);
        this.top.setPacks(this);
        this.lower.setLast(this.top);
        this.lower.setPacks(this);
        this.current = this.lower;
        this.length = 0;

        //遍历链表节点
        this.item = {
            root:this,
            current:this.lower,
            [Symbol.iterator]() {
                this.current = this.root.top.next;
                return this;
            },
            next:function(){
                if (!this.current.done) {
                    let node = this.current;
                    this.current = node.next;
                    return {done: false , value : node};
                } else return {done: true};
            }
        }
    }

    ///Symbol.iterator for of 接口实现

    //遍历链表值
    [Symbol.iterator]() {
        this.current = this.top.next;
        return this;
    }

    next() {
        if (!this.current.done) {
            let node = this.current;
            this.current = node.next;
            return node;
        } else  return {done: true};//循环结束
    }

    return() {
        //循环终止
        return {done: true};
    }

    ///

    add(clasp) {
        if (clasp.packs) {
            if (clasp.packs === this) return;
            clasp.packs.remove(clasp);
        }
        let last = this.lower.last;
        last.setNext(clasp);
        this.lower.setLast(clasp);
        clasp.setNext(this.lower);
        clasp.setLast(last);
        clasp.setPacks(this);
        clasp.done = false;
        this.length++;
    }

    remove(clasp) {
        if (clasp.packs === this) {
            let last = clasp.last;
            let next = clasp.next;
            last.setNext(next);
            next.setLast(last);
            clasp.packs = null;
            this.length--;
        }
    }

    push(val) {
        let node = new Clasp(val);
        this.add(node);
        return node;
    }

    join(chain){
        let totop = this.top.next;
        let tolower =  this.lower.last;

        let intop = chain.top.next;
        let inlower = chain.lower.last;
        let inlength = chain.length;

        this.lower.last = inlower;
        inlower.next = this.lower;
        intop.last = tolower;
        tolower.next = intop;

        chain.top.next = chain.lower;
        chain.lower.last = chain.top;
        chain.length = 0;

        this.length += inlength;

        let cur = intop;
        while(!cur.done){
            cur.packs = this;
            cur = cur.next;
        }
    }

    clear() { // 后续扩展
    }
}

// 节点定义
class Clasp {
    constructor(val) {
        this.done = true;
        this.value = null;
        this.packs = null;
        this.next = null;
        this.last = null;
        if (val) this.value = val;
    }


    delete() {
        if (this.packs) this.packs.remove(this);
    }

    setNext(clasp) {
        this.next = clasp;
    }

    setLast(clasp) {
        this.last = clasp;
    }

    getValue (){
        return this.value;
    }

    setValue (val){
        this.value = val;
    }

    setPacks(chain) { //表示节点在那个链中
        this.packs = chain;
    }
}

Tree.JS 自定义四叉树 此四叉树设计方向是 尽量简单 简化，拥有列表的加持，对数据在各个树节点中移动的速度比平常数组要好

"use strict";
// 树节点
class Region {
    constructor(l, t, r, b, level) {
        let w = r - l,
            h = b - t;
        this.l = l;
        this.t = t;
        this.r = r;
        this.b = b;
        this.w = w;
        this.h = h;
        this.cw = w / 2;
        this.ch = h / 2;
        this.level = level;

        this.splited = false;
        this.edged = false;


        this.nodeRT = null;// Region
        this.nodeLT = null;// Region
        this.nodeLB = null;// Region
        this.nodeRB = null;// Region

        this.tree = null;
        this.parent = null;

        // Chain.js
        this.list = new Chain();
    }

    getLevel() {
        return this.level;
    }


    setParent(parent) {
        this.parent = parent;
        return this;
    }

    getParent() {
        return this.parent;
    }
	// 设置 树的 Root 节点 并初始化一些参数 
    setTree(tree) {
        this.tree = tree;
        this.edge = this.l === 0 || this.t === 0 || this.r === this.tree.r || this.b === this.tree.b;
        this.limit = this.tree.limit * Math.pow(0.667, this.level);
        this.wedge = this.limit / 2;
        // level 深度 插入当前节点引用 // 广度优先 准备的属性
        this.tree.key.get(this.level).push(this); 
        return this;
    }

    getTree() {
        return this.tree;
    }

    topLimit() {
        return this.limit + this.wedge <= this.list.length;
    }

    lowerLimit() {
        return this.limit - this.wedge >= this.list.length;
    }


    /** 中线上
     * @method
     * @param {number} l
     * @param {number} t
     * @param {number} r
     * @param {number} b
     * */
    isCline(l, t, r, b) {
        return ((this.l + this.cw) > l && (this.l + this.cw) < r) || ((this.t + this.ch) > t && (this.t + this.ch) < b);
    }

    /** 可容纳
     * @method
     * @param {number} l
     * @param {number} t
     * @param {number} r
     * @param {number} b
     * */
    isInto(l, t, r, b) {
        return this.l < l && this.t < t && this.r > r && this.b > b;
    }

    /** 是边缘域 > 不考录是否可容纳 但考虑是否在中线 */
    isEdge() {
        return this.edged;
    }

    /** 是否分裂 */
    isSplit() {
        return this.splited;
    }

    setSplit(issplit) {
        this.splited = issplit;
    }

    split() {
        let nlevel = this.level + 1;

        //树节点
        this.nodeRT = new Region(this.l + this.cw, this.t, this.r, this.t + this.ch, nlevel).setTree(this.tree).setParent(this);
        this.nodeLT = new Region(this.l, this.t, this.l + this.cw, this.t + this.ch, nlevel).setTree(this.tree).setParent(this);
        this.nodeLB = new Region(this.l, this.t + this.ch, this.l + this.cw, this.b, nlevel).setTree(this.tree).setParent(this);
        this.nodeRB = new Region(this.l + this.cw, this.t + this.ch, this.r, this.b, nlevel).setTree(this.tree).setParent(this);

    }

	// 插入
    addTo(clasp) {
        //此操作 会转移 节点
        this.list.add(clasp);
    }
	// 移除
    removeTo(clasp) {
        this.list.remove(clasp);
    }
}

// 树 Root 节点 同样是 主要控制器
class Tree extends Region {
    constructor(w, h, level) {
        super(0, 0, w, h, 1);

        this.maxLevel = level ? level : 4;// 默认 4
        this.limit = 108 * 1.5; //值实际为 * 0.667

        this.key = new Map();// get set has delete
        let i=1;
        while(i<=this.maxLevel){
            this.key.set(i,new Chain());
            i++;
        }

        this.setTree(this);
        this.splitTo(this);
        this.setSplit(true);
    }

    isLower(region) {
        return region.level >= this.maxLevel;
    }

    addShape(shape) {
        let item = new Clasp(shape);
        this.key.set(shape, {
            clasp: item,
            region: this
        });
        this.addItem(item);
    }
	// 插入数据 item 为链表的一个节点引用
    addItem(item) {
        let shape = item.value;
        let keyobj = this.key.get(shape);
        keyobj.region = this.inRegion(shape, this); //移动后的新 region
        keyobj.region.addTo(item);
    }

    delShape(shape) {
        let keyobj = this.key.get(shape);
        keyobj.region.removeTo(keyobj.clasp);
        this.key.delete(shape);
    }

	// 删除数据 item 为链表的一个节点引用
    delItem(item) {
        let keyobj = this.key.get(item.value);
        keyobj.region.removeTo(keyobj.clasp);
        this.key.delete(item.value);
    }

	// 获取符合条件的 树节点 
    inRegion(shape, region) {
        // 获取图形可插入的 最深 region
        // 最坏的情况是 tree 节点
        if (!region) region = this;
        if (region.isCline(shape.l, shape.t, shape.r, shape.b)) return region;

        if (!region.isSplit()) {
            if (this.isLower(region)) return region;
            if (!region.topLimit()) return region;
            region.setSplit(true);

            // 复制 // 移动元素
            let mylist = region.list;
            region.list = new Chain();
            for (let cur of mylist.node) {
                this.inRegion(cur.value).addTo(cur);
            }
        }

        //根据位置获取 子 域 判断是否在 子 域中线上 否则 插入 
		// II III || I IV
        let vcenline = region.l + region.cw;
        let hcenline = region.t + region.ch;
        if (vcenline > shape.r) { 		
            if (hcenline > shape.b) { 	// lt II
                return this.inRegion(shape, region.nodeLT);
            } else { 					// lb III
                return this.inRegion(shape, region.nodeLB);
            }
        } else {
            if (hcenline > shape.b) { 	// rt I
                return this.inRegion(shape, region.nodeRT);
            } else { 					// rb IV
                return this.inRegion(shape, region.nodeRB);
            }
        }
    }

	// 当节点中 数量 小于一定值时 将数据存放在父级节点中
    mergeTo(region) {
        if (region.splited) {
            if (region.limit - region.wedge
                > region.nodeRT.list.length
                + region.nodeLT.list.length
                + region.nodeLB.list.length
                + region.nodeRB.list.length
            ) {
                region.setSplit(false);
                region.list.join(region.nodeRT.list);
                region.list.join(region.nodeLT.list);
                region.list.join(region.nodeLB.list);
                region.list.join(region.nodeRB.list);
            }
        }
    }

	// 初始化树节点
    splitTo(region) {
        if (this.isLower(region)) return;
        region.split();
        this.splitTo(region.nodeRT);
        this.splitTo(region.nodeLT);
        this.splitTo(region.nodeLB);
        this.splitTo(region.nodeRB);
    }
}

代码中出现的 shape 是图形的基础类，拥有：x y 属性以及四个边的属性（俗称包围盒 AABB ）：l t r b 。
到此 四叉树的研究已近结束 其他疑问或意见可以通过邮箱发送
如有误导请联系，我会进行修正。
邮箱 hbck_gwx@qq.com