重複する線分を見つけるアルゴリズム

StackOverflow https://stackoverflow.com/questions/1424923

質問 

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の間の線分。

正確に重複する線分を見つける最も速い方法は何ですか？

役に立ちましたか？

解決

各形状がエッジのリストである場合：

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（エッジ）、そしてあなたはそれよりうまくやらないでしょう。ただし、具体的に何をしたいかによっては、この解決策では満足できない場合があります。

他のヒント

N本の線分が与えられた場合、最悪の場合、O（n ^ 2）の交差点が存在する可能性があります。各ポリゴンが同じエッジを共有するN個のポリゴンがある場合を考えてください。この状況が発生するのを防ぐために追加された制約がない限り（追加を省略した場合）、最悪の場合、思いつく最良のアルゴリズムはO（N ^ 2）になります。 ^ 2）。

実際には、線分セグメントの交点を見つけるための計算幾何学で最も効率的なアルゴリズムは、スイープ線アルゴリズムです。すべての交差点を見つけるための最悪の場合の実行時間はO（k log n）です。ここで、kは交差点の数です（これはN ^ 2の場合がありますが、めったにありません。）

必要なアルゴリズムの正確な説明は、計算幾何学のセクションのトーマスHコーメンによるアルゴリズムの紹介。

twolfe18のアルゴリズムは良さそうです。ただし、一致するエッジが同じように記述されていない場合は、さらに複雑になる場合があります。この例では、P1とP2の両方がn2-n6エッジを共有しています。ただし、P2のエッジは、代わりにセグメントn2-n7で記述される場合があります（n2-n6とn6-n7が共線の場合）。次に、2つのエッジが重なっているかどうかを判断するために、より複雑なハッシュ方法が必要になります。セグメントをラインにマッピングし、ハッシュテーブルでラインを検索し、ラインのパラメータースペースで間隔ツリーを使用してラインの2つのセグメントが交差するかどうかをテストすることにより、2つのエッジがオーバーラップするかどうかを確認できます。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top