0

編集: 階層は、ここでの私の目標とはうまくいきません。元のリクエストのままですが、コアリクエスト（重複/非重複ルール）を満たすものを以下に回答しました。

1D 行のセットがあり、それぞれが 2 つの unsigned ints: start と end (start < end) で記述されているとします。重複するかどうかに基づいてグループを作成したいのですが、重複しない行をグループに含めたくありません。ラインが複数のグループに属している場合、グループ内のグループ内のグループを追跡するために、ある種の階層構造が必要になると思います...

ルールは次のとおりです。

  • 重複する行は、階層のできるだけ低い位置にグループ化する必要があります。
  • 重ならない行は同じグループにできません。

とにかく、ここに例の写真があります：

行

Line Aざっと見て、 and Line Cform Group 0、Line Hand Line Iform Group 1、 and Line Bisと言えますGroup 2。と、と、とLine Dはこれらの 3 つのグループすべてに含まれています。したがって、ここには 2 つの層のグループ化がありますが、問題の複雑さによっては、N が存在する可能性があると確信しています。また、私の例が表していないいくつかの問題があることも確信しています。Group 1Group 2Line EGroup 0Group 1Line FLine G

これを処理するための典型的なアルゴリズムは何ですか?

4

2 に答える 2

1

オーバーラップとオーバーラップしないという私の 2 つのルールは、階層構造と相容れないことに気付きました。これが私が落ち着いたアルゴリズムで、説明するきれいな写真があります。

改行

基本的なアイデアは、「重複する最大値」を見つけることになりました。行は昇順でソートする必要があり、次に左から右にループします。「クローズ」状態で開始します。これは、クローズされるのを待っている「オープン」グループがないことを意味します。現在反復されている行は、「アクティブな行」と見なされます。

ルール 1: クローズ状態でライン スタートが検出された場合、オープン状態に切り替えます。これが発生するポイントは、緑色の点で示されます。同じステップで複数の行がグループを開いている場合、どれが最初に遭遇するかは不明であるため、すべてに緑色の点を付けました。

終わりに達するまでラインを収集し続けます。

ルール 2: オープン状態でアクティブ ラインが終了している場合、すべてのアクティブ ライン (終了アクティブ ラインを含む) が新しいグループに配置されます。アルゴリズムは閉じた状態に切り替わります。グループが形成されるステップは青色で強調表示されます。これをトリガーする行末は、赤い点で示されます。1 つのステップで複数のドットを使用するルールは以前と同じです。

たとえば、形成される最初のグループはLine A、Line C、Line F、およびLine Gです。上記の 2 つのルールは、この例を処理するのに十分です。

この例では適用されない最終規則があります。

ルール 3: アルゴリズムが開いた状態で反復を終了する場合、すべてのアクティブな行が新しいグループに配置されます。

このアルゴリズムから得られる 4 つのグループは次のとおりです。

回線グループ

于 2012-10-04T21:18:40.330 に答える
0

階層的クラスタリングのいくつかの変種が法案に適合すると思います。類似度関数は、2 つの線分間の重なりの程度である可能性があります。

于 2012-10-04T15:47:27.527 に答える