查找重叠线段的算法

Question

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之间的线段。

找到完全重叠的线段的最快方法是什么？

Answer 1

如果每个形状都是边缘列表，那么：

initialize map<edge, list of shapes> map
for each Shape s
  for each Edge e in s
    list l = map.get(e)
    if(l == null) 
      l = new list()
    l.add(s)
    map.put(e, l)

for each <edge, list> in map.entries
  if(list.size > 1)
    do something with this common edge

它的O（边缘），你不会做得更好。这个解决方案可能不会令人满意，具体取决于你想要做什么。

Answer 2

给定N个线段，在最坏的情况下可以有O（n ^ 2）个交叉点。想想你有N个多边形的情况，其中每个多边形共享相同的边。除非有一个额外的约束来防止这种情况发生（你省略了添加），否则在最坏的情况下，你能想出的最佳算法将是O（N ^ 2），因为简单地列出交叉点是O（N ^ 2）。

实际上，用于查找线段交叉点的计算几何中最有效的算法是扫描线算法。找到所有交叉点的最坏情况是运行时间为O（k log n），其中k是相互关系的数量（这可能是N ^ 2，但很少是。）

您可以在 Thomas H Cormen的算法简介在计算几何的部分。

Answer 3

twolfe18的算法看起来不错。然而，如果没有相同地描述匹配的边缘，则可能存在额外的复杂性。在您的示例中，P1和P2都共享n2-n6边缘。但P2的边缘可能由段n2-n7描述（如果n2-n6和n6-n7是共线的）。然后，您将需要更复杂的散列方法来确定两条边是否重叠。您可以通过将线段映射到线上来查看两条边是否重叠，在哈希表中查找线，然后使用线上参数空间中的间隔树测试线上的两个线是否相交。