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

Question

我正在尝试构建一个基于位置和最大深度细分区域的四叉树。我想用它来实现地形的细节层次。换句话说，我有一个位置 (x, y)，一个区域 (x, y, width)，我将它传递给某个方法 build(region, position, maxDepth)，然后它应该 return 一个数组覆盖整个平面的节点。

我的实现与此略有不同，深度和根区域由四叉树对象表示。为了获得总细分，然后调用成员方法 get(x, y, radius)，然后 returns 一个覆盖整个根区域的节点数组（查看底部的代码）。

为了避免出现伪影，相邻节点之间最多有 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 ]

最后一个例子 return 有七个这样的四叉树节点：

#-------#-------#
|       |       |
|       |       |
|       |       |
#---#---#-------#
|   |   |       |
#---#---|       |
|   |   |       |
#---#---#-------#

如果有用，四叉树节点还会存储一个指向其父节点的指针。

我是不是走错方向了？通过回到树上来强制执行约束，并跟踪位置等等，对我来说似乎过于复杂。这里有不同的角度吗？

Answer 1

只要对算法稍加修改，就可以保证相邻两个节点之间的距离不会超过两层。想法是当圆与某个矩形相交时拆分节点，矩形的尺寸取决于节点的正方形及其深度。

考虑什么会影响给定深度的节点是否需要拆分，从最深层开始向上。

无法拆分最大深度的节点。
深度为 maxDepth - 1 的节点只有在与圆相交时才应拆分。
如果深度为 maxDepth - 2 的节点与圆相交或与深度为 maxDepth 的节点相邻，则应将其拆分（因此保持不拆分将违反要求).但是后一种情况就相当于与被分裂的深度maxDepth - 1的节点相邻。反过来，这相当于有一个深度为 maxDepth - 1 的相邻节点与圆相交（请参阅上一段）。我们如何在不遍历相邻节点和回溯的情况下判断是否是这种情况？请注意，当前节点 (x, y, x + width, y + width) 及其所有相邻节点更深一层的并集等于方块 (x - width/2, y - width/2, x + width*2, y+width*2) 与根方块的交集。所以整个条件归结为找到圆、根方块和当前方块膨胀到两倍大小之间的交点。（见图。）
将类似的推理应用到下一层，深度maxDepth - 3的节点(x, y, x + width, y + width)如果圆、根方块和正方形 (x - width*3/4, y - width*3/4, x + width*5/2, y + width*5/2).
最后，将其推广到任意深度的节点，当且仅当圆、根方块和正方形之间存在交点时，节点(x, y, x + width, y + width)才应该分裂(x - width*inflationRatio/2, y - inflationRatio/2, x + width*(1+inflationRatio), y + width*(1+inflationRatio))，其中 inflationRatio = 2^(2-maxDepth+depth)。（这可以通过归纳法证明，其中每个膨胀方块等于节点和所有相邻膨胀方块更深一层的并集）。

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

Constructing a quadtree such that there is only one level difference between adjacent nodes (LOD)

algorithm

tree

quadtree

level-of-detail

data-structures