1
多くの場合、セグメントの端がお互いに交差する範囲のセグメントがあります。これらのセグメントをポリラインにマージしたいと思います。範囲のセグメントをポリラインの範囲にマージ/結合するためのアルゴリズムが必要です
O(N_segments)に余分なストレージを使用せずに（たとえば、セグメントポイントのツリーや他の空間データ構造を構築してその上で作業する必要がない）アルゴリズムがありますか？
私が持っているセグメントの数は、O（10）です。だから、それらをハッシュテーブルやマップ（赤黒の木）のような動的なデータ構造に入れることは、そのデータ構造をスタックに置いてメモリの割り当てを避けなければ、最後のO(N^2)ループよりも高価になるでしょう（私が使用していポリラインは限りポイントの数が十分小さいとして割り当てを回避する、small_vectorを使用して実装され
現在、私はこれを作ってみた：。
polylines = []
// 1. Append each segment to a range of polylines, merging when possible:
for each segment in segments:
for each polyline in polylines:
merge_result = merge(segment, polyline)
if (not merge_result) continue
polyline = merge_result
goto done
// either polylines empty or no merge possible
polylines.append(segment)
done:
continue
// 2. Try to merge the polylines among themselves until no more merges are possible
// Pure brute force, quadratic
done = false
while not done:
for p1 in polylines:
for p2 in polylines[p1..end]:
merge_result = merge(p1, p2)
if not merge: continue
p1 = merge_result
polylines.remove(p2)
done = false
goto restart
restart: continue
しかし、第二のループはっきりと二次的なので、セグメント間でセグメントのシーケンスをマージ/結合/結合するためのより良いアルゴリズムがあるのだろうかと思います。
なぜデータ構造の作成を避けるのですか？私は、複数のセグメントが約O（n）時間で終点を共有しているかどうかを検出するために、セグメントの終点のマップを作成します。 – MrSmith42
[関連記事]（http://stackoverflow.com/questions/1436091/joining-unordered-line-segments?rq=1）は、検索をスピードアップするためにエンドポイントのハッシュを計算することを提案しています。 –
@ MrSmith42私はO（10）セグメントの注文を扱うので、スタック上にマップを作成しない限り、ダイナミックマップを作成するコストは最終的なO（N^2）ループのコストを超過するでしょう。これが私が余分なデータ構造なしでそれを行うためのより良いアルゴリズムに興味を持った理由です。スタック上のマップを試してみて、ベンチマークします。提案していただきありがとうございます。 – gnzlbg