这是一个类似于这里的问题的问题，但我我认为如果我能用更通用的术语重述它将会很有帮助。
我有一组多边形，这些多边形可以相互接触、重叠并且可以呈现任何形状。我的问题是，给定一个点列表，如何设计一种有效的算法来查找这些点位于哪些多边形？
点位置的有趣限制之一是，所有点都位于多边形的边缘（如果这有帮助的话）。
我知道 r-trees 可以提供帮助，但考虑到这一点我正在做一系列点，是否有更有效的算法而不是对每个点进行逐个计算？
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.
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?
发布评论
评论（3）
这里的关键搜索词是点位置。在这个名称下，计算几何文献中有许多算法适用于从特殊到一般的各种情况。例如，此链接列出了各种软件包，包括我自己的软件包。 （现在的列表有点过时了。）
速度和程序复杂性（以及实施工作）之间存在显着的权衡。最简单的编程方法是使用标准的多边形点代码检查每个多边形的每个点。但这可能会很慢，具体取决于您有多少个多边形。
比较困难的是通过扫平面建立点位置数据结构
并找到所有边-边交点。请参阅这篇维基百科文章了解一些选项。
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.)
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.
我认为你遇到的是关于问题的直觉（这是一种准模拟感知）与必然为 O(n) 的计算方法。
给定一个平面、一个简并多边形（一条线）以及该平面上的任意一组点，这些点是否与该线相交或落在该线的“上方”或“下方”？即使对于这种退化情况，我也无法想到小于 O(n) 的方法。
要么必须检查每个点与直线的关系，要么必须将这些点划分为某种树状结构，这至少需要 O(n) 次操作，但很可能更多。
如果我更擅长计算几何，我也许可以权威地说你刚刚重述了克利的衡量问题，但事实上我只需要建议它。
I think you are bumping up against intuition about the problem (which is a quasi-analog perception) versus a computational approach which is of necessity O(n).
Given a plane, a degenerate polygon (a line), and an arbitrary set of points on the plane, do the points intersect the line or fall "above" or "below" it? I cannot think of an approach that is smaller than O(n) even for this degenerate case.
Either, each point would have to be checked for its relation to the line, or you'd have to partition the points into some tree-like structure which would require at least O(n) operations but very likely more.
If I were better at computational geometry, I might be able to say with authority that you've just restated Klee's measure problem but as it is I just have to suggest it.
如果点只能落在边缘上，那么只需检查边缘即可在 O(n) 时间内找到多边形。
否则，您必须对 O(n log n) 中的多边形进行三角剖分，以针对 O(n) 中的三角形进行测试。
您还可以用从每个线段延伸的线来划分空间，注意哪一侧位于相应多边形的内部/外部。如果一个点落在一条边上或者位于多边形每条边的内部，则该点位于多边形内部。在最坏的情况下，边的数量为 O(n)，但在平均情况下，多边形的数量趋于 O(m)。
R 树在这两种情况下都会有所帮助，但前提是您有多个点需要测试。否则，构建 R 树将比搜索三角形列表更昂贵。
If points can only fall on the edges, then you can find the polygons in O(n) by just examining the edges.
If it were otherwise, you'd have to triangulate the polygons in O(n log n) to test against the triangles in O(n).
You could also divide the space by the line extended from each segment, noting which side is inside/outside of the corresponding polygon. A point is inside a polygon if it falls on an edge or if it's on the inside part of every edge of the polygon. It's O(n) on the number of edges in the worst case, but tends to O(m) on the number of polygons on the average case.
An R-tree would help in both cases, but only if you have several points to test. Otherwise, constructing the R-tree would be more expensive than searching through the list of triangles.