我有一个多边形上的一堆google地图。用于多个多边形的点多边形算法
这是我感兴趣的一个问题:给定一个纬度,经度点,什么是决定一切,这一点就在于多边形的最好办法
最明显的方法是运行“多边形点“算法迭代每个多边形,但我想知道是否有一个有效的算法来回答这样的查询,尤其是如果你有成千上万的多边形。
我有一个多边形上的一堆google地图。用于多个多边形的点多边形算法
这是我感兴趣的一个问题:给定一个纬度,经度点,什么是决定一切,这一点就在于多边形的最好办法
最明显的方法是运行“多边形点“算法迭代每个多边形,但我想知道是否有一个有效的算法来回答这样的查询,尤其是如果你有成千上万的多边形。
改进“对于每个多边形”算法的唯一方法是创建一组允许您跳过某些多边形的元数据。例如,如果对于您的数千个多边形,您拥有所有相互重叠的多边形的列表或一组列表,那么您将能够快速消除多个点中多边形比较。即找到包含点的第一个多边形,然后仅比较与该初始多边形相交/重叠的多边形,因为包含该点的多边形也必须与包含该点的其他多边形重叠。最差的情况是N次比较,例如你的每个实现。
您还可以创建多边形的逻辑/物理区域,例如某些区域中的多边形的象限。在象限示例中,您将/应该能够消除3/4多边形以进行比较。这完全取决于你的多边形如何排列。
但是在任何情况下,我认为对每个算法的改进在于在多边形集合中创建/组织一些逻辑组。
我不知道它下面有什么,但将空间过滤器应用于包含多边形特征的图层为我预选多边形...例子是这一个,void GRLayer::SetSpatialFilter (OGRGeometry * poFilter)
http://www.gdal.org/ogr/classOGRLayer.html#0b4ab45cf97cbc470f0d60474d3e4169。我想像许多GIS环境具有类似的功能。