geolocation - 在多个多边形中搜索点的最佳方法

Question

我需要将给定点（纬度，经度）与几个多边形进行匹配，以确定是否存在匹配。

最简单的方法是遍历每个多边形并应用多边形中的点检查算法，但这非常昂贵。

我所做的下一个优化是为每个多边形（上限、下限）定义一个边界矩形，并针对每个边界框迭代检查该点（与检查多边形中的所有点相比，比较少）。

还有其他可能的优化吗？绑定矩形点或 geohash 上的空间索引会有所帮助吗？

Answer 1

进一步优化：

边界框的想法很好。检查一个点是否在边界框中非常快。

如果您仍然需要更快的速度，您可以像这样进行更多的预计算：

1. 为每个 polgon 创建一个边界框。
2. 定义覆盖地图的相同大小的“图块”。
3. 对于每个图块，创建一个重叠的多边形列表。您可以通过首先检查边界框是否与图块重叠来做到这一点。如果是这样，您检查多边形是否与图块重叠。

搜索时，请执行以下操作：

1. 确定你所在的瓷砖。这是一个快速的操作。
2. 现在您有了潜在多边形的列表。
3. 对于每个多边形，检查该点是否在边界框中。
   如果是，请使用您提到的更昂贵的算法检查该点是否在多边形中。

我已经多次使用过这个算法，而且速度非常快。通过更改磁贴大小，您可以在内存占用和性能之间选择适当的平衡：

想想极端情况：

• 一个覆盖整个地图的巨大图块：
  您将获得地图中所有元素的列表，您必须检查所有边界框。

• 非常小的图块（对于每个国家只有一个多边形的地图为 1x1 米）：
  您将获得大量图块。所有的多边形将被分割成许多块，每个块只有一个多边形。但是，一旦您（快速）确定了该点在哪个图块中，几乎可以 100% 确定只有一个多边形需要检查。

你需要介于两者之间。如果您只是偶尔需要它，您可能希望选择低内存占用而不是性能。最佳切片大小还取决于多边形大小的同质性。所以，没有自动的方法来计算最佳的瓷砖大小，你只需要稍微调整一下，直到你做对了。