algorithm - Geohash 边界框搜索

Question

我想做一个边界框查询 geohashed 字符串的 Trie，其中点位于空间中心周围。当点跨越中心点时，我似乎找不到查询 trie 的好方法。

假设您在 16x16 空间中每个坐标有 4 位(总共 8 个)信息，其中每个框为 1x1。本质上是一个 16x16 的网格。

红线表示geohash中使用的四叉树最精细的划分。

Trie 代表上图。

bits=4, min=0, max=16, numBuckets=16.0, scaling=1.0, tree={
└── null
    ├── 0
    │   ├── (0110100) 00110100 = {(6, 6), hash=00110100}
    │   └── (1100000) 01100000 = {(6, 8), hash=01100000}
    └── 1
        ├── (0010101) 10010101 = {(8, 7), hash=10010101}
        └── (1000010) 11000010 = {(9, 8), hash=11000010}

边界框查询定义为左上角点和长度、宽度。例如(6,6 4x4) 应该返回 6,6 6,8 8,7 和 9,8。

我想到的一种方法是:从包含左上角坐标的最精确的框开始，逐渐降低精确度，直到我可以覆盖 4x4 正方形。但如果我这样做，我最终会在这个例子中查询整棵树。我只是没有看到“更好”的方法。

Answer 1

如果您可以向 trie 结构的节点添加额外信息，我会忽略 GeoHash 编码并将其视为任意树结构。从叶子开始，您可以计算每个节点周围的边界框，该边界框仅包含该节点下方的所有点。然后，当您自上而下搜索一个点(或区域)时，当其边界框未包含(或相交)您的查询点(或区域)时，您可以停止在节点处搜索。

如果您有能力保持更新，那么当您的搜索点或区域不在(或不相交)边界框内时，您将获得一个边界框，该边界框包含实际上在某个节点下方的所有点，即使搜索点或区域可能与某些点重叠，理论上 GeoHash 可以与该区域重叠。