4 
n4------n3--------------------n2--n1
| | | | | | | |
| | | | | | P1 |
| | | | | | | |
| | | | n6--n5
| | | | | |
| | n11--n10 |
n17 P4 | | | P2 |
| | | | P3 | n7
| | n12---n9 |
| | | | n8
| | | | | |
n16------------n15---------n14------------n13

上記の ASCII アートには、正確に重なる線分を持つ 4 つのポリゴン (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（エッジ）、そしてそれ以上のことはできません。ただし、具体的に何をしたいのかによっては、このソリューションでは満足できない場合があります。

于 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 が同一線上にある場合)。次に、2 つのエッジが重なるかどうかを判断するために、より複雑なハッシュ メソッドが必要になります。セグメントをラインにマッピングし、ハッシュテーブルでラインを調べてから、ライン上のパラメーター空間でインターバル ツリーを使用して、ライン上の 2 つのセグメントが交差するかどうかをテストすることで、2 つのエッジが重なるかどうかを判断できます。

于 2009-10-11T03:41:46.717 に答える