1

私は、いくつかのボックスが矢印で接続されているいくつかのボックスを使用して、Webページに図を描画する必要がある割り当てを行っています。実際の図や矢印などすべてを描画できるようにすべてを設定しましたが、ボックスを最適な方法で配置するという問題に直面しています。これは、交差する線が最小限になるようにページをレイアウトすることを意味します。

2種類の図を作成する必要があります。1つは、左上に配置するボックスとすべてのボックスが階層を形成する、より階層的な図です。もう1つは、ボックスに特定の場所を設定する必要がなく、最終結果が階層ではない場合は、より注意が必要です。どちらのシナリオでも、2つのボックス間に複数の接続があります。これは、データベースのE/R図を最も読みやすい方法でレイアウトするのとほとんど同じです。

誰かがこれを行う方法またはこれを行う方法に関する情報を見つける場所を知っていますか？

前もって感謝します

./CJ

4

1 に答える 1

2

交差を最小限に抑えて任意のグラフをレイアウトすることは NP 困難な問題であるため、適切なヒューリスティックを見つける必要があります。

頭に浮かぶのはこれです：

  1. 縁がつながった円の周囲にアイテムを置きます。
  2. シミュレートされたアニーリングを使用してアイテムを交換し、交差の数を最小限に抑えることを目指します。
  3. たとえば、強制指向レイアウトを使用して片付けます。

もう 1 つのオプションは、スパニング ツリーを見つけてレンダリングし、バック リンクを追加することです。これにより、シミュレーテッド アニーリング アプローチよりも多くのクロッシングが生成される可能性がありますが、割り当ての最初の部分の解を再利用できるという利点があります。

頑張ってください！

于 2012-09-11T05:23:29.893 に答える