QuadTree查找邻居

Question

我正在寻找一种算法来寻找四叉树的邻居，在示例图像中，我得到了红色节点，如何找到蓝色节点。有什么想法吗？

​

​

Answer 1

有一些已知的算法。看看他们。

1. Kunio Aizawa et al. -四叉树中的常量时间邻居发现:一种实验性的Result
2. Kasturi Varadarajan -通过Quadtrees
3. Robert Yoder, Peter Bloniarz的所有最近邻树-在四叉树、八叉树和超八叉树中计算邻居的实用算法

Answer 2

如果您的语言对数组有很好的支持，并且您可以选择树的表示形式，那么事实证明这比各种论文所建议的要简单得多。

技巧是将父子关系表示为一个向量：

def neighbour(tree, node, direction):
    """Finds the neighbour of a node in an adaptive quadtree or it's D-dimensional
    generalization (orthantree?).

    Be very careful with indexing when implementing this. Because it indexes  
    physical space with arrays, sometimes you need to think of coords in terms
    of Euclidean coords, and other times in terms of array coords.

    Args:
        tree: an object holding a bunch of node attributes, indexed by node:
            * `parent`, an (N,)-array of integers. The `n`th element gives the 
               index of `n`'s parent. The parent of the root is -1.
            * `children`, an ((N,) + (2,)*D)-array of integers. The `n`th slice 
               gives the indices of `n`'s children. The bottom-left child of node 3
               in a quadtree would be (3, 0, 0). 
            * `descent`, an (N, D)-array with elements from {-1, +1}. The `n`th
               row gives which direction node `n` lies in compared to its parent.
               For example, the left-bottom quadrant in a quadtree would be `(-1, -1)`.
            * `terminal`, an (N,)-array of booleans. The `n`th element is True
               if node `n` is a leaf.
        node: an integer, the index of the node you want to find the neighbour of.
        direction: a (D,)-array with elements from {-1, +1}

    Returns:
        An integer giving the index of the neighbouring node, or -1 if it doesn't 
        exist.
    """
    direction = np.asarray(direction)

    # Ascend to the common ancestor
    neighbour_descents = []
    while True:
        if (direction == 0).all() or node < 0:
            break
        node_descent = tree.descent[node]
        neighbour_descent = node_descent*(1 - 2*abs(direction))
        neighbour_descents.append(neighbour_descent)

        direction = ((node_descent + direction)/2).astype(int)
        node = tree.parent[node]

    # Descend to the neighbour 
    for neighbour_descent in neighbour_descents[::-1]:
        if tree.terminal[node] or node < 0:
            break
        node = tree.children[(node, *(neighbour_descent.T + 1)//2)]

    return node

它支持位(?)、四叉树、八叉树和一般的N维树(hyperoctree？正交树？)。它还支持任何方向-基数或对角线。最后，向量化真的很容易。

灵感来自@torvin发布的Yoder基于FSM的方法，以及对任何数量的维度的要求。

There's test and demo code here。