问跨多个多边形搜索点的最佳方法

EN

进一步优化：

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

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

1. 为每个多边形创建一个边界框。
2. 定义大小相等的覆盖地图的“瓦片”。
3. 为每个瓦片创建一个重叠的多边形列表。您可以通过首先检查边界框是否与平铺重叠来执行此操作。如果存在，则检查多边形是否与切片重叠。

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

1. 确定您所在的磁贴。这是一个快速的operation.
2. Now，你有一个潜在的列表，每个多边形，检查点是否在边界框中。

如果是，请使用您提到的代价更高的算法检查该点是否位于面中。

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

想想极端的情况：

• 一个覆盖整个地图的巨大磁贴：

你会得到一个地图中所有元素的列表，你必须检查所有的边界框。

• 非常小的瓦片(对于每个国家只有一个多边形的地图来说是1x1米)：

你会得到大量的瓷砖。所有多边形将被分割到多个瓦片上，并且每个瓦片将只有一个多边形。但是，一旦您确定了点在哪个切片中(最快)，几乎可以100%确定只有一个多边形需要检查。

你需要介于两者之间。如果您只需要一次，那么您可能希望选择较低的内存占用，而不是性能。最佳平铺大小也可以取决于多边形大小的均匀性。因此，没有自动计算最优平铺大小的方法，你只需要稍微调整一下，直到得到正确的大小。