2011-11-27 43 views
11

Necesito dibujar un árbol de estructura corporativa (algo así como un árbol genealógico) en C#. Todo el código auxiliar está allí. Es de color, interactivo y elegante. El único problema es que el algoritmo que realmente decide dónde colocar cada nodo me causa mucha pena.Algoritmo para dibujar árboles de manera eficiente

Por el momento, las cajas tienen un tamaño de 100x50, y tengo una clase llamada StaffNode que representa un miembro del personal en una determinada coordenada x, y.

El algoritmo solo necesita crear un List<StaffNode> con las x e y apropiadas.

Esto es increíblemente complicado.

Básicamente, el algoritmo es recursivo a lo largo de la estructura corporativa, por lo tanto, izquierda-> derecha, luego arriba-> abajo a lo largo del árbol. Obviamente, es malo si dos nodos están uno encima del otro.

puedo pensar en algunos algoritmos que puedan producir algo como esto:

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

Mientras que algo como esto podría ser mejor, ya que el árbol es muy grande y el espacio es muy limitado:

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

¿Alguno de ustedes tuvo que dibujar un árbol como este antes? Si lo tienes estoy seguro de que has encontrado los muchos obstáculos que tengo. ¿Algun consejo? Hasta ahora he pasado un día entero en él.

+0

lo que estás tratando de hacer? ¿No debería hacerse en Microsoft Visio o algo así? – DrStrangeLove

+0

Tome un solucionador de Tetris ... – Dialecticus

+0

@DrStrangeLove No, estoy escribiendo una visualización interactiva. – user1002358

Respuesta

12

Hay muchos buenos algoritmos para dibujar árboles, cada uno de los cuales muestra algunas propiedades diferentes de los árboles. Si desea mostrar una jerarquía, está this code for WPF that draws hierarchies. Para una discusión más general sobre cómo dibujar gráficos y árboles, considere mirar these lecture slides detallando muchos de estos algoritmos. También hay these excellent slides que cubre material similar.

Espero que esto ayude!

+2

¡Eso es absolutamente perfecto! Justo lo que necesitaba.Utiliza el algoritmo de Reingold-Tilford. – user1002358

+1

@ user1002358 Gracias por ese comentario. Tuve problemas para entender el algoritmo de la respuesta que figura aquí, sin embargo, googlear el "algoritmo Reingold-Tilford" me llevó a [esta pregunta] (http://stackoverflow.com/q/13128750/302677), que encontré más útil. También resumí los pasos para codificar el algoritmo [aquí] (http://rachel53461.wordpress.com/2014/04/20/algorithm-for-drawing-trees/) en caso de que alguien más esté buscando una explicación simple – Rachel

1

Podría utilizar un enfoque iterativo. Diseña el árbol usando algo como el primer ejemplo que usaste arriba. Luego mueva los nodos o subárboles más cerca uno del otro, mientras se asegura de que no se violen las restricciones (por ejemplo: los nodos no se pueden superponer, los nodos secundarios deben estar debajo de los nodos principales).

Pros:

  • algoritmo simple.
  • Obtiene una solución lo suficientemente buena.
  • Se puede aplicar continuamente a un árbol cambiante.
  • Se puede hacer que se vea bien.

Contras:

  • pueden necesitar muchas iteraciones para quedar bien.
  • no puede encontrar la solución óptima (se ve atrapado en un máximo local)
+0

Usted puede hacer algo como esto en una sola iteración. –

+0

De acuerdo, pero a veces un enfoque de optimización iterativo puede ser útil si un algoritmo de pase único no es factible computacionalmente para un gran número de nodos. – geofftnz

Cuestiones relacionadas