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

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

4

3 回答 3

3

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

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(edges)，你不会做得比这更好。这个解决方案可能并不令人满意，具体取决于您具体想做什么。

于 2009-09-15T03:52:52.447 回答
0

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

在实践中，计算几何中用于寻找线段交点的最有效算法是扫描线算法。他们找到所有交叉点的最坏情况运行时间是 O(k log n)，其中 k 是交叉点的数量（可以是 N^2，但很少如此。）

您可以在计算几何部分的 Thomas H Cormen 的算法简介中找到您需要的算法的准确描述。

于 2009-09-15T05:21:23.503 回答
0

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

于 2009-10-11T03:41:46.717 回答