查找重叠线段的算法
n4------------------n3--------------------n2--n1 | | | | | | | P1 | | | | | | | n6--n5 | | | | n11--n10 | n17 P4 | | P2 | | | P3 | n7 | n12---n9 | | | n8 | | | n16------------n15---------n14------------n13
在上面的 ASCII 艺术中，有四个具有完全重叠线段的多边形（P1、P2、P3、P4）。例如，多边形 P2（由节点 n3、10、9、12、15、14、13、8、7、6 和 2 之间的线段形成）和 P1（n1、2、5 和 6）在n2 和 n6 之间的线段。
找到完全重叠的线段的最快方法是什么？
n4------------------n3--------------------n2--n1 | | | | | | | P1 | | | | | | | n6--n5 | | | | n11--n10 | n17 P4 | | P2 | | | P3 | n7 | n12---n9 | | | n8 | | | n16------------n15---------n14------------n13
In the above ASCII art, there are four polygons (P1, P2, P3, P4) with exactly-overlapping line segments. For example, polygon P2 (formed by line segments between nodes n3, 10, 9, 12, 15, 14, 13, 8, 7, 6, and 2) and P1 (n1, 2, 5, and 6) overlap at the line segment between n2 and n6.
What is the fastest way to find line segments that overlap exactly?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
如果每个形状都是边列表，那么：
它的 O(边)，并且你不会做得比这更好。这个解决方案可能并不令人满意，具体取决于您具体想要做什么。
If each shape is a list of edges then:
its O(edges), and your not going to do better than that. this solution might not be satisfactory depending on what you want to do specifically though.
给定 N 条线段，在最坏的情况下可能有 O(n^2) 次交点。想象一下这样的情况：有 N 个多边形，每个多边形共享相同的边。除非有一个附加的约束来防止这种情况发生（您省略了添加），那么在最坏的情况下您能想到的最佳算法将是 O(N^2)，因为简单地列出交集就是 O(N ^2）。
实际上，计算几何中用于查找线段交点的最有效算法是扫线算法。最坏情况下查找所有交叉点的运行时间是 O(k log n)，其中 k 是交叉点的数量（可以是 N^2，但很少如此。）
您可以在 < a href="http://books.google.ca/books?id=NLngYyWFl_YC&dq=cormen+intro+to+algo&printsec=frontcover&source=bn&hl=en&ei=5COvSs6ACoj2sQPFupTNCw&sa=X& oi=book_result&ct=result&resnum=4#v=onepage&q=&f=false" rel="nofollow noreferrer">计算几何部分中 Thomas H Cormen 的算法简介。
Given N line segments, in the worst case there can be O(n^2) intersections. Just think of the case where you have N polygons where each polygon shares the same edge. Unless there is an added constraint to prevent this situation from happening (that you omitted to add) then the best algorithm you can come up with will be O(N^2) in the worst case, since simply listing the intersections is O(N^2).
In practice, the most efficient algorithms in computational geometry for finding intersections of line segments are sweep line algorithms. Their worst case running time to find all intersections is O(k log n) where k is the number of interesections (this can be N^2, however it rarely is.)
You can find a description of exactly the algorithm you need in Introduction to algorithms by Thomas H Cormen in the section on computational geometry.
twolfe18的算法看起来不错。然而，如果匹配边缘的描述不同，则可能会增加复杂性。在您的示例中，P1 和 P2 都共享 n2-n6 边。但 P2 的边可能由线段 n2-n7 来描述（如果 n2-n6 和 n6-n7 共线）。然后，您将需要更复杂的哈希方法来确定两条边是否重叠。您可以通过将线段映射到线上，在哈希表中查找线，然后使用线上参数空间中的区间树测试线上的两个线段是否相交来判断两条边是否重叠。
twolfe18's algorithm looks good. There may be an added complication, however, if matching edges are not identically described. In your example, P1 and P2 both share the n2-n6 edge. But P2's edge might be described by the segment n2-n7 instead (if n2-n6 and n6-n7 are colinear). You'll then need a more complicated hashing method to determine if two edges overlap. You can tell whether two edges overlap by mapping segments onto lines, looking up the line in a hashtable, then testing whether two segments on a line intersect using an interval tree in parameter space on the line.