2010-04-18 27 views
5

Estoy buscando un algoritmo que sería útil para determinar las coordenadas x y para un número de objetos para mostrar en la pantalla. Cada objeto puede estar relacionado con otro objeto y puede haber cualquier cantidad de relaciones y puede haber cualquier cantidad de estos objetos.Algoritmo de espaciado de gráficos

No hay restricciones en el tamaño total del área en la que se mostrarán estos objetos.

Estoy escribiendo esto en php y estaría buscando almacenar las coordenadas en una matriz.

Respuesta

3

Una forma de hacerlo es utilizar un modelo de pseudo-física. Tus objetos tienen una fuerza de repulsión y una fuerza atractiva si están unidos.

Mueva los objetos según la suma de las fuerzas aplicadas a ellos: en cada paso, calcule la suma de las fuerzas aplicadas a un objeto y muévalo en la dirección de la fuerza.

En pseudocódigo, una iteración sería:

for each object o1 
    force[o1] = 0 
    for each object o2 
     if o1 and o2 are linked 
     force[o1] += attraction_force(o1, o2) 
     else 
     force[o1] += repulsion_force(o1, o2) 

for each object o1 
    move(o1, force[o1]) 

Y deja las iteraciones cuando los objetos han alcanzado un estado estable.

Probablemente necesite experimentar con diferentes leyes de fuerza. En particular, desea que los objetos adyacentes alcancen un equilibrio rápidamente. Me gustaría experimentar con una lineal de la intensidad de la fuerza con la distancia (como un resorte) o cuadrática (gravition/atracción eléctrica)

También es probable que tenga que mover los objetos al azar para evitar que partes del gráfico de permanecer stucked. La cantidad de movimiento aleatorio debe ser grande para las primeras iteraciones y disminuir con el tiempo.

+0

Me gustaría agregar una sutileza sobre las que ya ha creado: si los objetos están vinculados, la atracción mutua debe detenerse a cierta distancia entre sí. Cuando se acerquen, deberían comenzar a repelerse unos a otros. Por supuesto, este comportamiento podría incorporarse en la función 'attraction_force' y modelarse como atracción negativa. De esta forma, el objeto vinculado buscaría una cierta distancia estándar entre sí. – Ideogram

0

Los nombres tradicionales para lo que quieres hacer son diseño gráfico ygraph drawing. No es en general un problema fácil. Los diagramas solo se verán bien si son planar o casi planar.

Cuestiones relacionadas