google-maps - 多个多边形的多边形算法中的点

Question

我有一张谷歌地图，上面有一堆多边形。

这里有一个我感兴趣的问题:给定一个经纬度点，确定该点所在的所有多边形的最佳方法是什么。

最明显的方法是对每个多边形迭代运行“多边形中的点”算法，但我想知道是否有一种有效的算法来回答此类查询，尤其是如果您有数千个多边形。

Answer 1

改进“针对每个多边形”算法的唯一方法是创建一组允许您跳过某些多边形的元数据。例如，如果对于数千个多边形，您有一个列表或一组列表，其中包含所有相互重叠的多边形，那么您将能够快速消除许多多边形中的点比较。 IE。找到第一个包含点的多边形，然后只比较与该初始多边形相交/重叠的多边形，因为包含该点的任何多边形也必须与包含它的其他多边形重叠。最坏的情况是 N 次比较，例如您的每个实现。

您还可以创建多边形的逻辑/物理区域，例如某个区域中多边形的象限。在象限示例中，您将/应该能够消除 3/4 的多边形以进行比较。不过，这完全取决于多边形的排列方式。

但无论如何，我认为 for-each 算法的改进在于在多边形集合中创建/组织一些逻辑组。