我正在尝试构建四叉树，它基于一个位置和一个最大深度来细分一个区域。我想用这个来实现地形的细节级别。换句话说，我有一个位置(x, y)，一个区域(x, y, width)，并将其传递给一些方法build(region, position, maxDepth)，然后应该返回覆盖整个平面的节点数组。
我的实现与此略有不同，因为深度和根区域由Quadtree对象表示。要获得总的细分，需要调用成员方法get(x, y, radius)，它将返回一个覆盖整个根区域的节点数组(请查看下面的代码)。
为了避免出现伪影，对于相邻节点之间最多只能有1个级别是非常重要的。
下面是一个可接受结果的示例。相邻节点之间的最大差异为1。(你可以忽略对角线，它们只是三角剖分的结果)
相反，这个示例不可接受，因为三个相邻节点之间的差异为2。
为了修复这个问题，我们需要像这样分割相邻的节点:
另一个可接受的解决方案示例如下:
这是我现在拥有的代码。
class Quadtree {
constructor({ x, y, width }, levels = 6, parent = null) {
this.x = x;
this.y = y;
this.width = width;
this.parent = parent;
this.children = null;
if (levels > 0) {
this.children = this.constructor.split(this, levels); // recursively split quadtree.
}
}
/**
* Checks for intersection.
* @param {x, y, radius} circle
* @param {x, y, width} square
* @return {boolean}
*/
static intersects(circle, square) {
let deltaX = circle.x - Math.max(square.x, Math.min(circle.x, square.x + square.width));
let deltaY = circle.y - Math.max(square.y, Math.min(circle.y, square.y + square.width));
return (deltaX * deltaX + deltaY * deltaY) < (circle.radius * circle.radius);
}
/**
* Splits a node.
*/
static split(node, levels) {
let width = node.width / 2;
let x = node.x;
let y = node.y;
// bottom left
let q1 = new Quadtree({
x: x,
y: y,
width
}, levels - 1, node);
// bottom right
let q2 = new Quadtree({
x: x + width,
y: y,
width
}, levels - 1, node);
// top left
let q3 = new Quadtree({
x: x,
y: y + width,
width
}, levels - 1, node);
// top right
let q4 = new Quadtree({
x: x + width,
y: y + width,
width
}, levels - 1, node);
return [q1, q2, q3, q4];
}
/**
* Gets the least amount of nodes covered by the given circle.
* @param {x, y, radius} circle
* @return {Array} An array of Quadtree-nodes.
*/
get(circle) {
if (this.children !== null && this.constructor.intersects(circle, { x: this.x, y: this.y, width: this.width })) { // we need to go deeper.
return this.children.reduce((arr, child) => {
return arr.concat(child.get(circle));
}, []);
} else {
return [ this ];
}
}
}
这是一个关于如何使用它的示例：
let tree = new Quadtree({ x: 0, y: 0, width: 100}, 2);
let nodes = tree.get({x: 15, y: 15, radius: 5}); // returns an array of nodes covering the whole region.
示例：
tree.get({x: -15, y: -15, radius: 5});
[ Quadtree { x: 0, y: 0, width: 100 } ] // returns the top node.
tree.get({x: 15, y: 15, radius: 5});
[ 7 Quadtree-nodes ]
最后一个示例返回了七个类似于以下的四叉树节点：
#-------#-------#
| | |
| | |
| | |
#---#---#-------#
| | | |
#---#---| |
| | | |
#---#---#-------#
如果有用的话，四叉树节点还会存储它们父节点的指针。
我是不是走错了方向？通过回溯树来强制执行约束条件，并跟踪位置等内容，对我来说似乎过于复杂。这里是否有不同的角度？
