空间搜索-Quad Tree

Posted on 2020-01-16 Edited on 2022-11-09 In geo Views:

geo quad tree

Quad Tree四叉树

四叉树是一种非常简单的空间索引技术。在四叉树中，每个节点代表一个bbox，该bbox覆盖被索引空间的某些部分，而根节点则覆盖整个区域。每个节点要么是一个叶子节点-在这种情况下，它包含一个或多个索引点，并且没有子级；要么是一个内部节点，在这种情况下，它正好具有四个子级，每个象限一个子级，方法是将沿两个轴的一半-因此得名。

geo-quadtree-nearest
四叉树如何划分索引区域的表示。

将数据插入四叉树很简单：

从根开始，确定您的点占据哪个象限。递归到该节点并重复，直到找到叶节点。然后，将您的点添加到该节点的点列表中。如果列表超过了某些预定的最大元素数，请分割节点，然后将这些点移动到正确的子节点中。

quad tree
四叉树内部结构的表示形式。

要查询四叉树，请从根开始，检查每个子节点，然后检查其是否与要查询的区域相交。如果是这样，则递归到该子节点。每当遇到叶节点时，请检查每个条目以查看其是否与查询区域相交，如果存在，则将其返回。

请注意，四叉树非常规则-实际上，它是Trie树，因为树节点的值不取决于要插入的数据。这样的结果是，我们可以以一种简单明了的方式对节点进行唯一编号：只需对每个象限以二进制编号（左上角为00，右上角为10，依此类推），而节点的数目就是串联从其根部开始，计算其每个祖先的象限数。使用此系统，示例图像中右下角的节点将被编号为1101。

如果我们为树定义了最大深度，那么我们可以在不参考树的情况下计算点的节点号-只需将节点的坐标标准化为适当的整数范围（例如，每个32位)，然后将x和y坐标-每个位对在假设的四叉树中指定一个象限。