Graph Spacing Algorithmus

Question

Ich bin auf der Suche nach einem Algorithmus, der nützlich wäre, um x y Koordinaten für eine Anzahl von Objekten zu bestimmen, die auf dem Bildschirm angezeigt werden sollen. Jedes Objekt kann mit einem anderen Objekt in Beziehung stehen, und es kann eine beliebige Anzahl von Beziehungen geben, und es kann eine beliebige Anzahl dieser Objekte geben.

Es gibt keine Einschränkung für die Gesamtgröße des Bereichs, in dem diese Objekte angezeigt werden sollen.

Ich schreibe dies in PHP und würde versuchen, die Koordinaten in einem Array zu speichern.

Answer 1

Ein Weg, dies zu tun ist, ein Pseudo-Physik-Modell zu verwenden. Ihre Objekte haben eine abstoßende Kraft und eine anziehende Kraft, wenn sie befestigt sind.

Sie bewegen die Objekte entsprechend der Summe der auf sie angewendeten Kräfte: Berechnen Sie bei jedem Schritt die Summe der Kräfte, die auf ein Objekt wirken, und verschieben Sie es in Richtung der Kraft.

In Pseudo-Code, würde eine Iteration sein:

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]) 

Und die Iterationen stoppen, wenn die Objekte einen stabilen Zustand erreicht haben.

Sie werden wahrscheinlich mit verschiedenen Kraftgesetze experimentieren müssen. Insbesondere möchten Sie benachbarte Objekte schnell in ein Gleichgewicht bringen. Ich würde wieder in die Ferne mit einer Kraftintensität linear experimentiert (wie eine Feder) oder quadratisch (gravition/elektrische Anziehung)

Auch werden wahrscheinlich müssen Sie die Objekte bewegen zufällig Teile des Graphen von stucked verbleibenden zu verhindern. Die Menge der zufälligen Bewegung sollte für die ersten Iterationen groß sein und mit der Zeit abnehmen.

Answer 2

Die traditionellen Namen für das, was Sie tun möchten, sind Graph Layout und graph drawing. Es ist im Allgemeinen kein einfaches Problem. Die Diagramme sehen nur dann gut aus, wenn sie planar oder fast planar sind.