多个多边形的多边形内点算法
我有一个谷歌地图，上面有一堆多边形。
这是我感兴趣的一个问题：给定一个经纬度点，确定该点所在的所有多边形的最佳方法是什么。
明显的方法是对每个多边形迭代运行“多边形中的点”算法，但是我想知道是否有一种有效的算法来回答此类查询，特别是如果您有数千个多边形。
I've a google maps with bunch of polygons on it.
Here is a problem I'm interested in: Given a lat,lng point, what's the best way to determine all the polygons that this point lies in.
The obvious way is to run "point in polygon" algorithm iteratively for each polygon, but I was wondering if there an efficient algorithm to answer such queries esp if you have thousands of polygons.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
改进“针对每个多边形”算法的唯一方法是创建一组元数据，允许您跳过一些多边形。例如，如果对于数千个多边形，您有一个列表或一组列表，其中包含所有彼此重叠的多边形，那么您将能够快速消除许多多边形中的点比较。即找到包含一个点的第一个多边形，然后仅比较与该初始多边形相交/重叠的多边形，因为包含该点的任何多边形也必须与包含该点的其他多边形重叠。最坏的情况是 N 次比较，例如每个实现的比较。
您还可以创建多边形的逻辑/物理区域，例如某个区域中的多边形的象限。在象限示例中，您将/应该能够消除 3/4 的多边形以进行比较。这一切都取决于多边形的排列方式。
但无论如何，我认为对 for-each 算法的改进在于在多边形集合中创建/组织一些逻辑组。
The only way to improve on "for each polygon" algorithm would be to create a set of metadata which would allow you to skip some polygons. For example, if for your thousands of polygons you had a list, or set of lists, of all polygons that overlapped each other then you would be able to eliminate many point-in-polygon comparisons quickly. I.e. Find first polygon that contains a point, then compare only polygons that intersect/overlap that initial polygon because any polygon that contains the point would also have to overlap some other polygon that contains it. The worst case would be N comparisons e.g. your for each implementation.
You could also create logical/physical regions of polygons, such as quadrants for example, of polygons in a certain area. In the quadrant example you would/should be able to eliminate 3/4 of polygons for comparison. This all depends on how your polygons are arranged though.
But in any case, I think an improvement to the for-each algorithm lies in the creation/organization of some logical groups among your polygon collection.
我不知道它下面是什么，但是将空间过滤器应用于包含多边形特征的图层，为我预先选择多边形...示例就是这个，
void GRLayer::SetSpatialFilter （OGRGeometry * poFilter）http://www.gdal.org/ogr/classOGRLayer.html#0b4ab45cf97cbc470f0d60474d3e4169。我想许多 GIS 环境都有类似的功能。I dont know what underneath it, but applying spatial filter to the layer containing polygon feature pre-select polygons for me... Example is this one,
void GRLayer::SetSpatialFilter ( OGRGeometry * poFilter)http://www.gdal.org/ogr/classOGRLayer.html#0b4ab45cf97cbc470f0d60474d3e4169. I'd imagine many GIS environment has similar feature.