2011-11-01 182 views
3

我有一个多边形上的一堆google地图。用于多个多边形的点多边形算法

这是我感兴趣的一个问题:给定一个纬度,经度点,什么是决定一切,这一点就在于多边形的最好办法

最明显的方法是运行“多边形点“算法迭代每个多边形,但我想知道是否有一个有效的算法来回答这样的查询,尤其是如果你有成千上万的多边形。

回答

0

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

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

但是在任何情况下,我认为对每个算法的改进在于在多边形集合中创建/组织一些逻辑组。