algorithm - 匹配建筑物上的门牌号(多边形点测试的特例)

Question

带例子的任务

我正在使用来自 openstreetmap 的地理数据(国家大小)。建筑物通常是没有门牌号的多边形，带有门牌号的单个点位于建筑物的多边形内。建筑物可能有多个门牌号。

我想将门牌号与建筑物的多边形相匹配。

简单的解决方案

对于每个门牌号，对每个建筑物多边形执行多边形中的点测试。

问题

对于大约 50,000,000 座建筑物和 10,000,000 个地址点来说太慢了。

想法

为建筑物多边形构建和索引以加速搜索每个门牌号点的周围多边形。

问题

对于这种多边形结构，您会推荐什么索引或策略？多边形从不重叠，并且该区域被稀疏地覆盖。

---

这个问题被复制到 gis.stackexchange.com。建议在此处发布问题。

Answer 1

由于听起来您要测试的是格式正确的多边形，因此我会使用带 AABB 检查的空间散列，最后是完整的多边形中的点测试。希望到那时您将平均每个地址三个或更少的多边形点测试。

• 将您的数据覆盖的区域分成一个简单的网格，其中一个网格是中位数建筑物大小的小倍数(2 到 4)。 (也许 100-200 米？)
• 计算每个多边形的轴对齐边界框，将其(及其边界框)添加到边界框相交的每个网格位置。 (找出轴对齐边界框与常规轴对齐网格单元重叠的位置非常简单。我不会将网格存储在简单的二维数组中——我会使用映射二维整数网格坐标的哈希表，例如( 1023, 301), 到多边形列表)
• 然后遍历所有地址点。在哈希表中查找该点所在的单元格。遍历该单元格中的所有多边形，如果该点位于任何多边形的轴对齐边界框内，则执行完整的多边形点测试。

这有几个优点:

• 数据结构很简单——不需要花哨的库(除了处理多边形)。使用 C++、您的多边形库和 std 命名空间，这可以在不到一个小时内实现。
• 空间结构不是分层的——当您查找点时，您只需在哈希表中执行一次 O(1) 查找。

当然，网格作为空间结构的常见缺点:

• 不能很好地处理大小变化很大的多边形。不过，我希望因为您使用的是 map 数据，所以尺寸几乎总是在一个数量级内，甚至可能小得多。

假设您最终在每个网格中有 N 个最大多边形，并且每个多边形都有 P 点，并且您有 B 建筑物和A 地址，您正在查看 O(B*P + N*A)。由于 B 和 P 可能相对较小，尤其是平均而言，您可以考虑这个 O(B + N) —— 几乎是线性的。