构造四叉树，使得相邻节点（LOD）之间只有一个层级差]]

Question

bounty过期在1小时内

。这个问题的答案有资格获得+ 50声望赏金。Mario希望对此问题引起更多关注：“我在这个问题上太咬牙了。这个问题的答案可能对许多人有帮助。”

我正在尝试构建一个四叉树，该四叉树根据位置和最大深度来细分区域。我想用它来实现地形的详细程度。换句话说，我有一个位置（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 ]
最后一个示例返回七个这样的四叉树节点：

#-------#-------#
|       |       |
|       |       |
|       |       |
#---#---#-------#
|   |   |       |
#---#---|       |
|   |   |       |
#---#---#-------#
如果有用，则四叉树节点还将存储指向其父节点的指针。

我是朝错误的方向前进吗？通过回到树上来加强约束，并跟踪位置以及什么都不对我来说似乎过于复杂。这里有不同的角度吗？

我正在尝试构建一个四叉树，该四叉树根据位置和最大深度来细分区域。我想用它来实现地形的详细程度。换句话说，我有一个位置（x，y），一个...

Answer 1

请考虑什么因素会影响从最深级别开始的给定级别的节点是否需要拆分。