木を効率的に描画するためのアルゴリズムですか？

Question

私は、C＃で企業の構造ツリー（家系のような）を描く必要があります。すべての補助コードはそこにあります。それは色付けされ、インタラクティブで、派手です。唯一の問題は、実際に各ノードをどこに置くかを決めるアルゴリズムで、私に多くの悲しみを与えていることです。

今のところ、ボックスのサイズは100x50です。特定のx、y座標のスタッフメンバーを表すStaffNodeというクラスがあります。

アルゴリズムでは、適切なxとyを使用してList<StaffNode>を作成するだけで済みます。

これは信じられないほどトリッキーです。

基本的に、アルゴリズムは企業構造に沿って再帰的です（ツリーに沿って左→右、上→下）。 2つのノードが互いに重なっていると明らかに悪いことです。

私はこのような何かを生み出す可能性があるいくつかのアルゴリズムを考えることができ

：

  * 
    o   O 
o o o o o  O 
o   O O O O O 
       O 

ツリーが非常に大きく、スペースが非常に限られているので、このようなものは、より良いでしょうに対し：

 * 
    o  O 
o o o o o O 
o  O O O O O 
      O 

これまでのようなツリーを描かなければならなかった人はいますか？もしあなたが私が持っている多くのハードルに出会ったと確信しています。任意のヒント？これまで私は一日を費やしてきました。

Answer 1

ツリーを描画するためのアルゴリズムは数多くあり、それぞれツリーのさまざまな特性を示しています。階層を表示する場合は、this code for WPF that draws hierarchiesがあります。グラフや木を描く方法のより一般的な議論については、these lecture slidesを参照して検討することを検討してください。同様の素材をカバーするthese excellent slidesもあります。

希望すると便利です。

Answer 2

繰り返しアプローチを使用できます。上で使用した最初の例のようなものを使ってツリーをレイアウトします。次に、制約が違反していないことを確認しながら、ノードまたはサブツリーを互いにより近くに移動させます（たとえば、ノードは重複できず、子ノードは親ノードの下になければなりません）。

長所：

• 単純なアルゴリズム。
• 十分な解決策を得ます。
• 変化するツリーに連続して適用できます。
• 涼しく見せることができます。

短所：

• 良く見えるように多くの反復が必要な場合があります。
• あなたが何をすべきかをしようとしている（局所的な最大値に引っ掛かり）