给定一组多边形和一系列点，找出哪些多边形位于点 [英] Given a set of polygons and a series of points, find the which polygons are the points located

问题描述

这是类似于<一个问题href="http://stackoverflow.com/questions/6354662/identifying-the-original-edge-of-a-union-polygon">the一个在这里，但我想，这将是有益的，如果我能在一个更笼统改写它。

This is a question similar to the one here, but I figure that it would be helpful if I can recast it in a more general terms.

我有一组多边形，这些多边形可以互相接触，重叠，可以采取任何形状。我的问题是，给点列表，如何设计一个高效的算法，找出哪些多边形位于点？

I have a set of polygons, these polygons can touch one another, overlap and can take on any shape. My question is, given a list of points, how to devise an efficient algorithm that find which polygons are the points located?

之一的点的位置的有趣的限制是，所有的点都位于多边形的边缘，如果这有助于。

One of the interesting restriction of the location of the points is that, all the points are located at the edges of the polygons, if this helps.

据我所知，R树<一href="http://stackoverflow.com/questions/4063634/retrieve-set-of-rectangles-containing-a-specified-point">can帮助，但考虑到我正在做一系列的点，有没有更有效的算法，而不是计算每个点一个接一个？

I understand that r-trees can help, but given that I am doing a series of points, is there a more efficient algorithm instead of computing for each point one by one?

推荐答案

这里的关键搜索词是的点位置的。根据这个名字，有很多算法的计算几何文学各种情况，从特殊到一般。例如，此链接列出了各种软件包，包括我自己。 （一有点乱最新列表了。）

The key search term here is point location. Under that name, there are many algorithms in the computational geometry literature for various cases, from special to general. For example, this link lists various software packages, including my own. (A somewhat out-of-date list now.)

有速度和程序的复杂性（并因此实施工作）之间的显著权衡。最简单的对程序的方法是检查每个点对每一个多边形，使用标准的点在多边形code。但是，这取决于你有多少个多边形有这个可能比较缓慢。 更困难的是通过扫描平面来建立一个点位置数据结构 并查找所有的边到边的交点。请参阅这个维基百科文章看到一些你的选择。

There is a significant tradeoff between speed and program complexity (and therefore implementation effort). The easiest-to-program method is to check each point against each polygon, using standard point-in-polygon code. But this could be slow depending on how many polygons you have. More difficult is to build a point-location data structure by sweeping the plane and finding all the edge-edge intersection points. See the this Wikipedia article to see some of your options.

这篇关于给定一组多边形和一系列点，找出哪些多边形位于点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！