• 最近研究了一下四叉树的实现。 基本原理就不说了。 在线演示链接：https://timohausmann.de/quadtree.js/dynamic.html 个人觉得这个每一帧都要去清空并重建四叉树，效率不高。 源码：...
最近研究了一下四叉树的实现。
基本原理就不说了。
个人觉得这个每一帧都要去清空并重建四叉树，效率不高。
 //remove duplicates
returnObjects = returnObjects.filter(function(item, index) {
return returnObjects.indexOf(item) >= index;
});
源码里面重复添加节点以及返回结果的过滤，性能不好。
看了知乎上的另外一篇文章：https://zhuanlan.zhihu.com/p/180560098
觉得思路挺好的。
按照思路用ts实现了一遍，大概300行代码。初步测试结果看起来正常，1000个物体相互碰撞在5ms以内。
export class QPoint {
public x:number;
public y:number;
public get w():number {return this.x;}
public get h():number {return this.y;}
constructor(x:number,y:number){
this.x = x;
this.y = y;
}
}

export class QRect {
public origin:QPoint;
public size:QPoint;

public get centerX():number{ return this.origin.x + this.size.w * 0.5;}
public get centerY():number{ return this.origin.y + this.size.h * 0.5;}
public get xMin():number{return this.origin.x };
public get yMin():number{return this.origin.y };
public get xMax():number{return this.origin.x + this.size.w};
public get yMax():number{return this.origin.y + this.size.h};

public static intersects( rect:QRect, target:QRect):boolean{
if( rect.yMin > target.yMax ){
return false;
}
if( rect.yMax < target.yMin ){
return false;
}
if( rect.xMax < target.xMin ){
return false;
}
if( rect.xMin > target.xMax ) {
return false;
}
return true;
}

constructor(origin:QPoint,size:QPoint){
this.origin = origin;
this.size = size;
}

}

this.treeNode = treeNode;
}

this.next = other.next;
this.treeNode = other.treeNode;
}
}

class DataNode<T> {
public data:T;
public rect:QRect;
public depth:number;

constructor(data:T,depth:number,rect:QRect){
this.data = data;
this.depth = depth;
this.rect = rect;
}

let t1 = this.lastLinkTreeInfo.next;
let t2 = this.curLinkTreeInfo.next;
while(t2){
if(t1 != t2){
return true;
}
t1 = t1.next;
t2 = t2.next;
}
return false;
}
}

protected curDepth:number;
protected nodesConut:number;
protected originX:number;
protected originY:number;
protected treeNodes:QuadTreeNode<T>[] = [];
protected children:DataNode<T>[] = [];
private static looseRectTmp:QRect = new QRect(new QPoint(0,0),new QPoint(0,0));

/**
* 仅用来读
*/
public get looseRect():QRect{
let size = this.rootTree.getSizeByDepth(this.curDepth);
QuadTreeNode.looseRectTmp.origin.x = this.originX - size.w/2;
QuadTreeNode.looseRectTmp.origin.y = this.originY - size.h/2;
QuadTreeNode.looseRectTmp.size.x = size.x * 2;
QuadTreeNode.looseRectTmp.size.y = size.y * 2;
}

public get isLeaf():boolean{ return this.rootTree.isMaxDepth(this.curDepth);}

this.originX = originX;
this.originY = originY;
this.curDepth = curDepth;
this.rootTree = rootTree;
this.nodesConut = 0;
}

/**
* 四叉树节点
*/
let depth = this.curDepth+1;
let size = this.rootTree.getSizeByDepth(depth);
//left bottom
let treeNode = new QuadTreeNode<T>(this.originX,this.originY,depth,this.rootTree);
this.treeNodes.push(treeNode);
//right bottom
treeNode = new QuadTreeNode<T>(this.originX+size.w,this.originY,depth,this.rootTree);
this.treeNodes.push(treeNode);
//left up
treeNode = new QuadTreeNode<T>(this.originX,this.originY+size.h,depth,this.rootTree);
this.treeNodes.push(treeNode);
//right up
treeNode = new QuadTreeNode<T>(this.originX+size.w,this.originY+size.h,depth,this.rootTree);
this.treeNodes.push(treeNode);
}

/**
* 更新链接索引路径
* @param centerX
* @param centerY
* @param maxDepth
*/
if(this.curDepth+1 > maxDepth){
return;
}
let size = this.rootTree.getSizeByDepth(this.curDepth+1);
let row = Math.min(1,Math.floor((centerY - this.originY) / size.h));
row = Math.max(0,row);
let col = Math.min(1,Math.floor((centerX - this.originX) / size.w));
col = Math.max(0,col);
let idx = row * 2 + col;
let treeNode = this.treeNodes[idx];
treeNode.updatePosInfo(centerX,centerY,maxDepth,nextInfo);
}

/**
* 查询碰撞节点
* @param rect
* @param outItms 接收数组
* @param outVisItms 访问过的节点
*/
quary(rect:QRect,outItms:T[],outVisItms:T[]){
let queue:QuadTreeNode<T>[] = [];
if(this.checkNeedVisit(rect)){
queue.push(this);
}

let index = 0;
while(index < queue.length){
let treeNode = queue[index]
for(let i=0 , n=treeNode.children.length ; i<n;i++){
let dataNode = treeNode.children[i];
outVisItms.push(dataNode.data);
if(QRect.intersects(dataNode.rect,rect)){
outItms.push(dataNode.data);
}
}

if(!treeNode.isLeaf){
for(let i=0, n = treeNode.treeNodes.length; i<n ; i++){
if(treeNode.treeNodes[i].checkNeedVisit(rect)){
queue.push(treeNode.treeNodes[i]);
}
}
}
index++;
}
}

/**
* 更新四叉树
* @param item
* @param rect
*/
update(item:T,rect:QRect){
let dataNode:DataNode<T> = item["$dataNode"]; //插入 if(!dataNode){ let tmpDepth = this.rootTree.getDepthBySize(rect.size.w,rect.size.h); dataNode = new DataNode<T>(item,tmpDepth,rect); item["$dataNode"] = dataNode;
}else{
dataNode.rect = rect;
}
this.remove(dataNode);
this.insert(dataNode);
}
}

/**
* 插入节点
* @param dataNode
*/
insert(dataNode:DataNode<T>){
}
}
}

/**
* 移除节点
* @param dataNode
*/
remove(dataNode:DataNode<T>){
let index = linkInfo.treeNode.children.indexOf(dataNode);
}
}
}

private checkNeedVisit(rect:QRect){
return this.nodesConut > 0 &&  QRect.intersects(this.looseRect,rect);
}
}

/**
* 松散网格型四叉树
*/
export default class QuadTree<T>{
public maxDepth:number;
public gridMinWidth:number;
public gridMinHeight:number;
public depthSize:QPoint[] = [];

public getSizeByDepth(dep:number):QPoint{
return this.depthSize[dep];
}

public isMaxDepth(depth:number):boolean{
return depth >= this.maxDepth -1;
}

private disDepth(width:number,height:number):number{
let dw = Math.max(0,Math.floor(Math.log2(width / this.gridMinWidth + 1)));
let dh = Math.max(0,Math.floor(Math.log2(height/ this.gridMinHeight + 1)));
return Math.max(dw,dh);
}

public getDepthBySize(width:number,height:number):number{
let disDepth = this.disDepth(width,height);
return this.maxDepth - disDepth - 1;
}

/**
*
* @param originX 左下角x
* @param originY 左下角y
* @param conWidth 宽度
* @param conHeight 高度
* @param checkMinWidth 检测的物体的最小宽度
*/
constructor(originX:number,originY:number,conWidth:number,conHeight:number,checkMinWidth:number){
this.gridMinWidth = checkMinWidth;
this.gridMinHeight = checkMinWidth;
this.maxDepth = this.disDepth(conWidth,conHeight);
let tmp = Math.pow(2,this.maxDepth-1);
this.gridMinWidth = conWidth / tmp;
this.gridMinHeight = conHeight / tmp;
//初始化层级size
for(let i=0; i < this.maxDepth; i++){
this.depthSize.push(new QPoint(conWidth/Math.pow(2,i),conHeight/Math.pow(2,i)));
}
}

/**
* 更新四叉树
* @param item
* @param rect
*/
update(item:T,rect:QRect){
}

/**
* 查询碰撞节点
* @param rect
* @param outItms 接收数组
* @param outVisItms 访问过的节点
*/
quary(rect:QRect,outItms:T[],outVisItms:T[]){
}
}

效果:
CocosCreator工程源码:https://gitee.com/fuatnow/quad-tree.git
展开全文
• 最近想要研究研究webgl地形的渲染，然后就想起了四叉树，在网上看了一篇相关的文章，准备拿javascript实现一下备用。四叉树原理(这部分就直接抄了，见参考)四叉树(Q-Tree)是一种树形数据结构。四叉树的定义是：它的...

最近想要研究研究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();
/**
* @param {[number]} depth [输的深度]
* @param {[QuadRect]} rect [数表示的矩形区域]
*/
g_tree.depth = depth;
}
/**
* @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;
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;
console.log('ok.');
用四叉树查找某一对象
未完待续......

展开全文
• #coding=utf-8"""@des:多叉树--这里定义的4叉树"""class node:def __init__(self, data):self._data = dataself._children = []def getdata(self):return self._datadef getchildren(self):return self._childrendef...

#coding=utf-8
"""
@des:多叉树--这里定义的4叉树
"""
class node:
def __init__(self, data):
self._data = data
self._children = []
def getdata(self):
return self._data
def getchildren(self):
return self._children
##if full
if len(self._children) == 4:
return False
else:
self._children.append(node)
def go(self, data):
for child in self._children:
if child.getdata() == data:
return child
return None
class tree:
def __init__(self):
def insert(self, path, data):
for step in path:
if cur.go(step) == None:
return False
else:
cur = cur.go(step)
return True
def search(self, path):
for step in path:
if cur.go(step) == None:
return None
else:
cur = cur.go(step)
return cur
if __name__=="__main__":
'''
define node
'''
a = node('A')
b = node('B')
c = node('C')
d = node('D')
e = node('E')
f = node('F')
g = node('G')
h = node('H')
i = node('I')
j = node('J')
k = node('K')
l = node('L')
m = node('M')
n = node('N')
o = node('O')
'''
adding node to build true
'''
tree = tree()
#testcase
print 'Node',tree.search("ABE").getdata()
print 'Node',tree.search("ABC").getdata()
print 'Node',tree.search("AHM").getdata()
tree.insert("ABCD", 1)
for i in d.getchildren():
print 'value after', d.getdata(),' is ', i.getdata()

展开全文
• 题目难度：★★★☆☆类型：二叉树我们想要使用一棵四叉树来储存一个 N x N 的布尔值网络。网络中每一格的值只会是真或假。树的根结点代表整个网络。对于每个结点, 它将被分等成个孩子结点直到这个区域内的值都是...

题目
难度：★★★☆☆
类型：二叉树
我们想要使用一棵四叉树来储存一个 N x N 的布尔值网络。网络中每一格的值只会是真或假。树的根结点代表整个网络。对于每个结点, 它将被分等成四个孩子结点直到这个区域内的值都是相同的.
每个结点还有另外两个布尔变量: isLeaf 和 val。isLeaf 当这个节点是一个叶子结点时为真。val 变量储存叶子结点所代表的区域的值。
你的任务是使用一个四叉树表示给定的网络。下面的例子将有助于你理解这个问题：
给定下面这个8 x 8 网络，我们将这样建立一个对应的四叉树：

我们要用四叉树表示这样一个棋盘
由上文的定义，它能被这样分割：

上述棋盘的分割方式
对应的四叉树应该像下面这样，每个结点由一对 (isLeaf, val) 所代表.
对于非叶子结点，val 可以是任意的，所以使用 * 代替。

可以表示上述棋盘的四叉树
提示
N 将小于 1000 且确保是 2 的整次幂。
如果你想了解更多关于四叉树的知识，你可以参考这个 wiki 页面。
解答
题目中四叉树的构建是为了表示一个布尔方阵，我们的构建遵循构建法则，我们定义一个构建函数，实现构建指定区域四叉树的功能，通过递归调用本函数实现所有四叉树结点的构建。这里重点介绍使用函数递归调用实现四叉树构建的思路：
1. 函数的功能
实现指定范围的四叉树构建。
2. 函数的输入和输出
我们设计的四叉树，需要只需要输入要构建网格中四叉树的网格即可。不过我们这里为了便于递归，把整个网格作为每次递归函数的输入，并且指定要构建四叉树的范围，这里的范围用左上角坐标和区域边长来表示。
函数的输出是根据指定网格构建而成的四叉树，换句话说，这个四叉树是输入网格的唯一表示。
3. 函数的实现
计算所考察正方形区域中元素的纯度，这里通过计数方式实现，如果区域内所有数字均为零或一，表明该区域满足构建叶子结点的条件，直接返回对应的叶子结点即可。
如果所考察的正方形区域中既有零又有1，我们就需要把它当做普通结点进行对待，实例化一个结点，并且把四个子树挂在这个结点上，设当前区域左上角坐标为(h, w)，当前区域边长为N，边长的一半为n，那么四个子树所表示的区域分别为：
(1)左上子树表示的区域，左上角为(h, w)，边长为n；
(2)右上子树表示的区域，左上角为(h, w+n)，边长为n；
(3)左下子树表示的区域，左上角为(h+n, w)，边长为n；
(4)右下子树表示的区域，左上角为(h+n, w+n)，边长为n。
有了区域，通过调用本函数可以实现四个子树的构建，通过递归可以实现整个四叉树的构建。
# Definition for a QuadTree node.
class Node:
def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):
self.val = val
self.isLeaf = isLeaf
self.topLeft = topLeft
self.topRight = topRight
self.bottomLeft = bottomLeft
self.bottomRight = bottomRight
class Solution:
def construct(self, grid):
def dfs(grid, h, w, N):
"""
用于构建方格([h, w], [h+N, w+N])的四叉树
:param grid: 输入网格
:param h: 方格左上角纵坐标
:param w: 方格左上角横坐标
:param N: 方格边长
:return: 返回一棵构建好的四叉树
"""
total = sum([grid[h+i][w+j] for i in range(N) for j in range(N)]) # 求取当前方格内的和
if total == 0: # 如果方格内所有元素都是0
return Node(False, True, None, None, None, None) # 构造一个值为False的叶子节点
elif total == N * N: # 如果方格内所有元素都是1
return Node(True, True, None, None, None, None) # 构造一个值为True的叶子节点
else: # 说明方格内有0有1
root = Node('*', False, None, None, None, None) # 构造一个值为"*"的中间结点
n = N // 2 # 求方格的一半
root.topLeft = dfs(grid, h, w, n) # 构建左上子树
root.topRight = dfs(grid, h, w+n, n) # 构建右上子树
root.bottomLeft = dfs(grid, h+n, w, n) # 构建左下子树
root.bottomRight = dfs(grid, h+n, w+n, n) # 构建右下子树
return root # 返回构建完成的树
return dfs(grid, 0, 0, len(grid))
if __name__ == "__main__":
s = Solution()
print(s.construct([[1, 1, 1, 1, 0, 0, 0, 0],
[1, 1, 1, 1, 0, 0, 0, 0],
[1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 0, 0, 0, 0],
[1, 1, 1, 1, 0, 0, 0, 0],
[1, 1, 1, 1, 0, 0, 0, 0],
[1, 1, 1, 1, 0, 0, 0, 0],
]))
如有疑问或建议，欢迎评论区留言~

展开全文
• 问题描述 区域型物体的四叉树（Quad-tree）表示方法最早出现在加拿大地理信息系统CGIS中，将四...（2）对该矩阵进行自上而下的四叉树分割，构建四叉树结构； （3）对得到的所有叶子节点进行线性四叉树编码，将编码作为
• *在UE4里实现四叉树查找最近点 如果问如何计算1个点与10个点中最近的点，可能只需要计算10次，比较9次便能得到答案。但若要以这样的方式计算1万，10万，甚至1千万个点中相邻的点，可能就需要计算几万次。这样计算的...
• 接下来我们讲解一下本篇文章最重要的部分，就是关于游戏AOI中的四叉树算法，四叉树其实在游戏AOI中不太常用（网上相关信息太少），经过查找一般都适用于地图的地形数据或者碰撞检测之类的地方，首先说一下什么是四叉...
• 请你用四叉树表示该矩阵 grid 。 你需要返回能表示矩阵的 四叉树 的根结点。 注意，当 isLeaf 为 False 时，你可以把 True 或者 False 赋值给节点，两种值都会被判题机制接受 。四叉树数据结构中，每个内部节点只有...
• 红色实心矩形 就是在四叉树 + 视锥cascaded 内的 cube 集合 更加精准 Code QuadTree.cs #define __ENABLE_COMPLETE_CONTAINS_BRANCH_HANDLE__ // 启用完全包含 枝干 优化的处理 #define __ENABLE
• 题目难度：★★☆☆☆类型：二叉树给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。例如，给定一个 3叉树 :某个三叉树返回其层序遍历:[[1],[3,2,4],[5,6]]说明：树的深度不会超过 1000。树的...
• 四叉树索引的基本思想是将地理空间递归划分为不同层次的树结构。它将已知范围的空间等分成个相等的子空间，如此递归下去，直至树的层次达到一定深度或者满足某种要求后停止分割。四叉树的结构比较简单，并且当空间...
• 问题：给定n个权值，作为n个叶结点，构造一棵二叉树，而这棵的特点是，有n个叶节点，叶节点的值为给定的权值。而内部节点的值为子树的权值和 带权路径： 哈夫曼是这种二叉树中带权路径最小的 构造方法 设有n...
• 四叉树的结构比较简单，并且当空间数据对象分布比较均匀时，具有比较高的空间数据插入和查询效率，因此四叉树是GIS中常用的空间索引之一。常规四叉树的结构如图所示，地理空间对象都存储在叶子..
• 《用四叉树和希尔伯特曲线做空间索引》由会员分享，可在线阅读，更多相关《用四叉树和希尔伯特曲线做空间索引(11页珍藏版)》请在人人文库网上搜索。1、超酷算法：用四叉树和希尔伯特曲线做空间索引阅读四叉树,...
• 对一组输入数据构建相应的二叉排序，并利用其中序遍历对数据进行升序排序。（此题人工批改，必须使用二叉树进行排序，其它算法不得分） 【输入形式】 数据个数，数据。(以空格分割) 【输出形式】 排序之后的数据。...
• 建立空间索引在点云数据处理中已被广泛应用，常见空间索引一般是自顶向下逐级划分空间的各种空间索引结构，比较有代表性的包括BSP Tree、K-D Tree、KDB Tree、R Tree、R+ Tree、Cell Tree、四叉树和八叉树等索引结构...
• 基于西瓜书西瓜数据集2.0生成决策，画出决策，并输入样本进行预测类别。 然后根据现有代码对breast_cancer数据集进行训练和预测。 因为实验要求，不能够使用sklearn库，所以就只能上网借鉴一下大佬的代码，再...
• Overview内容——3（四叉树规划） Teacher Zhang mentioned quadtree in last class, which is used to divide space and then connecting blank block can get a path. RRT算法——1（流程图） RRT means Rapidly-...
• kd树构建的代码如下 class Node: def __init__(self, x0): self.left = None self.right = None self.x0 = x0 self.split = None def create_node(data, depth=0): n, f = data.shape if n == 0: return if n == 1:...
• 来看一个具体的习题实践：题目根据二叉树前序遍历序列例如：7,-7,8,#,#,-3,6,#,9,#,#,#,-5,#,#，构建二叉树，并且用前序、中序、后序进行遍历代码import java.util.Scanner;public class BinaryTree {public static ...
• 遍历序列构造唯一二叉树 一、一种遍历确定二叉树？ 二、两种遍历确定二叉树？ 2.1 先序 + 中序遍历序列 2.2 后序 + 中序遍历序列 2.3 层序 + 中序遍历序列 一、一种遍历确定二叉树？ 通过先、中、后序遍历的序列，...
• 一、CART决策模型概述(Classification And Regression Trees)决策是使用类似于一棵的结构来表示类的划分，构建可以看成是变量(属性)选择的过程，内部节点表示选择那几个变量(属性)作为划分，每棵的叶...
• 构建三叉的算法，求救高手！！！！！关注:109答案:2信息版本：手机版 电脑版解决时间 2021-01-24 17:11提问者嗿恋仯囡2021-01-24 00:24有道题目需要写一函数来构造一个三叉，已知：标准链式存储结构，指向跟的...
• R语言构建xgboost模型：xgb.cv函数交叉验证确定模型的最优子个数（可视化交叉验证对数损失函数与xgboost模型子树个数的关系）、交叉验证获取最优子之后构建最优xgboost模型
• 文章目录简介一、构建决策-DecisionTree.py1. 思路基本算法信息熵信息增益决策存储结构2. 代码二、决策可视化-PlotTree.py1. 思路2. 代码3. 可视化结果总结 简介 GitHub地址：...
• 构造哈夫曼 每个节点的存储结构设计如下图： 哈夫曼的存储表示代码： // 哈夫曼的存储表示 ...//构建select函数 void Select(HuffmanTree HT, int m, int* s1, int* s2) { //从这m个数
• N 叉树的层序遍历（中等） 思路：广度优先搜索，思路同上，但第二次写我做了些优化——由于子节点不只两个，一开始将子节点存入队列时想的是循环遍历，后来意识到可以用扩展运算符，避免了三层循环嵌套，减少时间...
• 在这其中，八叉是一种非常有效的储存数据的方法，尤其是对于像流形物体、点云图（point cloud）、体素（voxel）这样的稀疏化（sparse）数据来说，八叉可以更好地展示数据的结构特性。 图1 八叉结构的数据...

...