Algoritmo per disegnare alberi in modo efficiente?

Question

Ho bisogno di disegnare un albero della struttura aziendale (simile a un albero genealogico) in C#. Tutto il codice ancillare è lì. È colorato, interattivo e di fantasia. L'unico problema è l'algoritmo che in realtà decide dove mettere ogni nodo mi sta dando un sacco di dolore.

Per il momento, le scatole hanno dimensioni 100 x 50 e ho una classe chiamata StaffNode che rappresenta un membro dello staff in una particolare coordinata x, y.

L'algoritmo deve solo creare un List<StaffNode> con l'appropriato xe y di.

Questo è incredibilmente difficile.

In sostanza l'algoritmo ricorsivo è lungo la struttura aziendale, in modo da sinistra> destra, poi top-> verso il basso lungo l'albero. Ovviamente è male se due nodi sono uno sopra l'altro.

mi viene in mente un paio di algoritmi che potrebbero produrre qualcosa di simile:

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

Mentre qualcosa come questo sarebbe meglio, dal momento che l'albero è molto grande e lo spazio è molto limitato:

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

Qualcuno di voi ha dovuto disegnare un albero come questo prima? Se sei sicuro di aver incontrato i tanti ostacoli che ho. Qualche consiglio? Finora ho passato un'intera giornata.

Answer 1

Ci sono molti buoni algoritmi per disegnare alberi, ognuno dei quali mostra alcune proprietà diverse degli alberi. Se vuoi mostrare una gerarchia, c'è this code for WPF that draws hierarchies. Per una discussione più generale su come disegnare grafici e alberi, considerando l'aspetto di these lecture slides dettaglio di tali algoritmi. C'è anche these excellent slides che copre materiale simile.

Spero che questo aiuti!

Answer 2

È possibile utilizzare un approccio iterativo. Disporre l'albero usando qualcosa come il primo esempio che hai usato sopra. Quindi spostare nodi o sottostrutture più vicini tra loro, assicurandosi che non vi siano violazioni di vincoli (ad esempio: i nodi non possono sovrapporsi, i nodi figlio devono essere al di sotto dei nodi parentali).

Pro:

• semplice algoritmo.
• Ottiene una soluzione sufficientemente buona.
• Può essere applicato in modo continuo a un albero che cambia.
• Può essere fatto per sembrare freddo.

Contro:

• possono avere bisogno di molte iterazioni a guardare bene.
• non può trovare soluzione ottimale (viene catturato in un massimo locale)