algorithm - 如何通过坐标给定的点来识别可变大小的区域？

Question

使用经度和纬度将 map 划分为大小可变的区域。

为简单起见，让我们将 map 视为笛卡尔平面，将经度和纬度视为 x,y 坐标。

区域始终是一个矩形。例如，一个区域可以表示为 x∈(0,3],y∈(30,50]笛卡尔平面中的范围是有限的，但非常大。

那么，当给定一个 x,y 坐标时，我们如何识别该坐标所属的区域？

例如，当我们有一个 x,y 坐标 (2, 36) 时，我们如何有效地找到它属于区域 x∈(0,3],y∈(30,50]?

Answer 1

如我的评论所述，您可以使用 R-tree 解决此问题.链接的 wiki 文章提供了比我想象的更好的解释，但基本概念非常简单:

给定一组区域 R0(在您的示例中为矩形)，您构造一组R1 更少 区域，通过将原始区域分组区域并计算它们的边界矩形。

作为一个例子，考虑下面的一组区域(我想保持符号简单，这就是为什么我只考虑对角线上的正方形:通过 (p, s) 我的意思是一个正方形左下角位于 (p, p) 且边长为 s:

R0 = {(0, 1), (1, 1), (3, 1), (4, 1)}

我们现在可以对前两个和最后两个区域进行分组，并计算它们的边界矩形以到达 R1:

R1 = {(0, 2), (3, 2)}

现在的技巧是，给定一个查询点(1.5, 1.5)，我们不必检查R0 中的所有区域。我们首先对R1 进行查询，发现该点位于(0, 2) 区域内。因此，我们只需要在该边界矩形的 children 中搜索，它们是 R0 中的前两个区域。

---

当然，这是一个非常简单的例子。实际上，您希望在 R1 中的每个边界矩形中只有少数(一些较低的常数，例如 4)R0 区域。所以当你有很多输入区域时，R1 中仍然会有很多矩形。幸运的是，我们可以再次应用相同的技巧，并从 R1 中创建一组较小的边界矩形 R2。依此类推，直到您到达一组 Rn，它只包含几个矩形。

因此您创建了一棵完整的树:整个区域是根。 Rn 中的每个矩形都是顶级 child ，依此类推。

查询就像我在简单示例中描述的那样工作:您只需要递归包含查询点的矩形，理想情况下您可以排除许多其他矩形。

---

那么为什么我说理想？让我们回到示例并假设我将第一个和最后一个矩形以及中间两个矩形分组。那会给我一组不同的边界矩形:

R1 = {(0, 5), (1, 3)}

这些矩形是重叠的，因此与上面相同的查询点将在两个 矩形中。也就是说，我们仍然需要检查 R0 的所有区域。

因此，正确划分矩形非常重要。找到最佳划分的问题是 NP-hard，因此您必须使用启发式方法。一个简单的方法是按左 x 坐标对矩形进行排序并相应地划分它们。在下一级别中，您将通过 y 坐标执行相同的操作。当所有矩形均匀分布且接近正方形时，该方法效果很好。