0

現在、私は最小コリドー長アルゴリズムに取り組んでおり、セットアップの一部には、問題内のすべての隣接ポイントのリストを作成することが含まれます。現在、2 つの配列があります。1 つは x 座標上の隣接する点でソートされ、もう 1 つは y 座標上の点でソートされています。また、2 つのリストを指定して近くのポイントを調べるだけで隣接関係を見つけています。ポイントの y が同じである場合 (隣接する x で並べ替えられたリスト上)、それらは同じ行にあります。同様に、それらが同じ x (y リスト上) を持っている場合、同じ行に嘘をつきます。

たとえば、次の部屋があるとします。

写真

次に、x隣接点のリストには、次の順序で点が含まれます: {v1, v2, v3, v4, v5, ... v21, v22} (それらはラベル付けされた順序と同じ順序のままです) また、リスト{v22, v16, v14, v9, v4, v13, v8, v3, v21, ... v5, v1} (基本的には y=x 上のグラフの反映)

前述のように、リスト上の近くのポイントを見て、隣接するポイントを見つけます。これはほとんどの点で問題なく機能しますが、次のエッジ ケースでは失敗します。

ここに画像の説明を入力

x隣接リストには{v1、v2、... v6、v7 ... v11、v12}が含まれ、私のアルゴリズムはv6とv7を隣接点として検出します。これらの 2 点の間に部屋があることをどのように検出できますか? 長方形と頂点の点のセットも利用できることに注意してください。前もって感謝します。

4

1 に答える 1

2

最後の例で v6 と v7 が隣接しているかどうか (つまり、接続されているかどうか) を位置だけに基づいて判断する方法がないため、位置ベースのアプローチを放棄することをお勧めします。代わりに、どのポイントが他のどのポイントに接続されているかを示すグラフを作成します。ポイントはグラフの頂点になり、隣接/接続されている頂点の各ペアの間にエッジを追加します。

グラフを作成するには、次のアルゴリズムを試すことができます (頭のてっぺんから)。

  1. 指定された頂点とエッジのないグラフを作成します
  2. 頂点 (ポイント) を x 座標でグループ化します。グループへの頂点のマップを作成するか、特定の頂点がどのグループに属しているかを調べる他の方法を作成します。
  3. グループごとに、そのグループ内の頂点を使用して素集合データ構造を作成します。
  4. 四角形のすべての垂直エッジを反復処理し、エッジごとに、そのエッジの端にある 2 つの頂点に対応するサブセットで和集合を実行します。
  5. グループを反復し、グループごとにそのサブセットを反復します。サブセットごとに、まずそのサブセットの頂点を y 座標で並べ替え、連続する頂点のペア間のグラフにエッジを追加します。

次に、x 座標と y 座標の役割を切り替えて (垂直エッジの代わりに水平エッジを使用して)、手順 2 ～ 5 を繰り返します。

当然のことながら、これはすべてのエッジ (線) が水平または垂直であるという前提に依存しています。

于 2013-05-28T00:10:37.847 に答える