8

私はグリッドを持っています:

グリッド

グリッドはセルで構成され、再帰的に小さなセルに分割されます。グリッド内の各子セルは、その親によって制約されます。

グリッド内のセルは、グラフのような構造で格納されます。各セルには、各コーナーに 1 つずつ、計 4 つの接続があります。各コーナーは、接続に平行で最も近いセルのエッジが同じ高さになるように、別のセルに接続します。このグリッドは、次の JSON で表すことができます。

{
    "grid1": 
    {
        "topLeft": null,
        "topRight": "grid2",
        "bottomLeft": "grid3",
        "bottomRight": "grid2",
        "topLeftDirection": null,
        "topRightDirection": "horizontal",
        "bottomLeftDirection": "vertical",
        "bottomRightDirection": "horizontal"
    },

    "grid2": 
    {
        "topLeft": "grid1",
        "topRight": "grid4",
        "bottomLeft": "grid1",
        "bottomRight": "grid5",
        "topLeftDirection": "horizontal",
        "topRightDirection": "horizontal",
        "bottomLeftDirection": "horizontal",
        "bottomRightDirection": "vertical"
    },

    "grid3": 
    {
        "topLeft": "grid1",
        "topRight": "grid2",
        "bottomLeft": null,
        "bottomRight": "grid10",
        "topLeftDirection": "vertical",
        "topRightDirection": "vertical",
        "bottomLeftDirection": null,
        "bottomRightDirection": "horizontal"
    },

    "grid4": 
    {
        "topLeft": "grid2",
        "topRight": "grid7",
        "bottomLeft": "grid5",
        "bottomRight": "grid5",
        "topLeftDirection": "horizontal",
        "topRightDirection": "horizontal",
        "bottomLeftDirection": "vertical",
        "bottomRightDirection": "vertical"
    },

    "grid5": 
    {
        "topLeft": "grid4",
        "topRight": "grid4",
        "bottomLeft": "grid6",
        "bottomRight": "grid6",
        "topLeftDirection": "vertical",
        "topRightDirection": "vertical",
        "bottomLeftDirection": "vertical",
        "bottomRightDirection": "vertical"
    },

    "grid6": 
    {
        "topLeft": "grid5",
        "topRight": "grid5",
        "bottomLeft": "grid9",
        "bottomRight": "grid8",
        "topLeftDirection": "vertical",
        "topRightDirection": "vertical",
        "bottomLeftDirection": "vertical",
        "bottomRightDirection": "horizontal"
    },

    "grid7": 
    {
        "topLeft": "grid4",
        "topRight": "grid11",
        "bottomLeft": "grid8",
        "bottomRight": "grid8",
        "topLeftDirection": "horizontal",
        "topRightDirection": "horizontal",
        "bottomLeftDirection": "vertical",
        "bottomRightDirection": "vertical"
    },

    "grid8": 
    {
        "topLeft": "grid7",
        "topRight": "grid7",
        "bottomLeft": "grid6",
        "bottomRight": "grid9",
        "topLeftDirection": "vertical",
        "topRightDirection": "vertical",
        "bottomLeftDirection": "horizontal",
        "bottomRightDirection": "vertical"
    },

    "grid9": 
    {
        "topLeft": "grid6",
        "topRight": "grid8",
        "bottomLeft": "grid10",
        "bottomRight": "grid10",
        "topLeftDirection": "vertical",
        "topRightDirection": "vertical",
        "bottomLeftDirection": "vertical",
        "bottomRightDirection": "vertical"
    },

    "grid10": 
    {
        "topLeft": "grid9",
        "topRight": "grid9",
        "bottomLeft": "grid3",
        "bottomRight": "grid12",
        "topLeftDirection": "vertical",
        "topRightDirection": "vertical",
        "bottomLeftDirection": "horizontal",
        "bottomRightDirection": "horizontal"
    },

    "grid11": 
    {
        "topLeft": "grid7",
        "topRight": null,
        "bottomLeft": "grid12",
        "bottomRight": "grid12",
        "topLeftDirection": "horizontal",
        "topRightDirection": null,
        "bottomLeftDirection": "vertical",
        "bottomRightDirection": "vertical"
    },

    "grid12": 
    {
        "topLeft": "grid11",
        "topRight": "grid11",
        "bottomLeft": "grid10",
        "bottomRight": null,
        "topLeftDirection": "vertical",
        "topRightDirection": "vertical",
        "bottomLeftDirection": "horizontal",
        "bottomRightDirection": null
    }
}

構造の描写は次のとおりです。

グリッドグラフ構造

グラフを見ると、小さな細胞群を含む大きな細胞群を見ることができます。 グリッド データ構造を取得してツリーに変換できるアルゴリズムを開発しようとしています。ツリーの各要素は、リーフ (グリッド内のセルを表す)、またはグリッド内の小さなコンテナーまたはセルを含むコンテナーのいずれかです。グリッドをツリーとして表示すると、次のようになります。

グリッドツリー構造

これまでのところ、私はあまり運がありませんでした。これが私がこれまでに試したことです：

  • 私は外で作業して、グリッドの大きな部分を決定し、それらを分割して小さな部分を見つけようとしました. 問題は、コンテナを構成するものと、グリッド自体以外にグリッド内で最大のものを選択する方法を判断するのが難しいことです。
  • 個々のセルを取り、その最大の親までチェーンをたどり、チェーンを組み合わせてグリッドを形成しようとしました。このアプローチの問題点は、親コンテナーが常に明確であるとは限らないことです。
  • グリッドを小さなグリッドに分割し、最大のエッジに沿って分割してみました。ただし、エッジの端に到達した場合、その端が実際にグリッドのエッジなのか、それともローカル エッジなのかを判断するのは困難です。
  • グリッド内のどのセルが直接の兄弟を持っているかを判断しようとしました (同じセルに接続しているセルの同じ側にある接続に注意することによって)。次に、これらをコンテナーに配置し、構造内のセルをコンテナーに置き換えて繰り返します。このアプローチは実際に機能する可能性があると思いますが、非常に面倒で非効率的です。
  • 最後に、ツリー マップを含むいくつかの異なるデータ構造を調べました。ツリー マップはこの例で使用するのに非常に優れたデータ構造だと思いますが、私のグリッドには既に構造が組み込まれています。ビルドされた kd ツリーを見つけることができたすべてのアルゴリズムは、グリッド内の既存の構造を想定していませんでした。

私はこれに本当にこだわっています。コメント、提案、またはアイデアをいただければ幸いです。

アップデート

Yochai Timmer の回答を見た後、グリッド構造がいかに重要であるかを強調したいと思います。以下は、同じように見える 2 つのボックスの例ですが、構造が異なり、結果としてツリー表現が大きく異なります。

異なる構造のグリッド

4

2 に答える 2

2

あなたの4番目のオプションが進むべき道だと思います。実装はそれほど複雑ではないと思います。グリッド内のすべてのボックスに初期化された (サイズ 1 のツリーとして) フォレストのルート ノードのセットを維持します。次に、そのセットを繰り返し処理し、調べているボックスが2 つのエッジを持つボックスに接続されているかどうかを確認します。そうである場合は、両方をより大きなボックスに置き換え、その大きなボックスをフォレスト内の親ノードにします。

微妙な点が 1 つありますが、それがアプリケーションでどれほど重要かはわかりません。上記の主な例では、ルートで 3 項ノードを取得しません。代わりに

     Root
/-----+-----\
|     |     |
A     B     C

あなたは次のようなものを得るでしょう

       Root
    /---^---\
   D        C
/--^--\
A     B

ただし、後処理ステップでそのような状況を検出し、後で修正できると思います。ツリーをたどり、各ノードについて、それが水平結合または垂直結合を表しているかどうかを確認し、ノード X が持っているかどうかを確認します。親の Y と同じ向きにしてから、X を削除し、その子を Y の追加の子にします。

于 2012-07-12T16:24:24.747 に答える
1

グリッドからグラフを作成できます。ここでは、すべての「ボックス」の間にエッジがあり、隣接しています。

次に、エッジの重みを決定します (私は min(v1,v2) を使用します)。

次に、最小スパニング ツリー アルゴリズムを使用してツリーを作成します。

于 2012-07-12T07:24:22.673 に答える