我正在尝试构建一个四叉树，它根据位置和最大深度细分区域。我想用它来实现地形的细节层次。换句话说，我有一个位置 (x, y)，一个区域 (x, y, width)，然后我将它传递给某个方法 build(region, position, maxDepth)，然后它应该返回一个覆盖整个飞机。
我的实现与此略有不同，深度和根区域由四叉树对象表示。要获得总细分，然后调用成员方法 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 ]
最后一个示例返回七个四叉树节点，如下所示：
#-------#-------#
| | |
| | |
| | |
#---#---#-------#
| | | |
#---#---| |
| | | |
#---#---#-------#
如果有用的话，四叉树节点也会存储一个指向其父节点的指针。
我会朝着错误的方向前进吗？通过返回树来执行约束，并跟踪位置等等，对我来说似乎过于复杂。这里有不同的角度吗？
