3D Sternkarte generieren

[voon]

Ich hab 100 Sterne. Die sind auf ganz unterschiedliche Weise verbunden, von 1 gelang ich zu 2, 3, 77 und 83. Von 2 zu 1, 3, 44 und 68. Von 3 zu 1, 2, 22, 31 und 77. Und so weiter. Graphisch ergibt das einen 3D Graphen. Wenn ich nur diese Verbindungen kenne, wie berechnet man effizient die 3D Koordinaten jedes Sterns, damit der Graph "ausgewogen" aussieht, die Verbindungen also nicht allzu unterschiedlich lang werden und das ganze als Karte dienen kann?

 

[benneq]

Das musst du noch mal genauer erläutern.

100 Sterne
Jeder Stern ist mit beliebig vielen anderen Sternen verknüpft. Immer bidirektional?
Du kennst die Koordinaten keines Sterns.
Wieso soll das ein 3D Graph ergeben? 1D oder 2D ginge genau so gut.
Kennst du die Entfernungen? oder 'nen Richtungsvektor?
Wie soll man ohne irgendwelche Referenzpunkte/-werte überhaupt irgendwelche Koordinaten bestimmen?

 

[voon]

Es geht nur darum, eine Verbindungskarte zu zeichnen, denk an einen Haltestellenplan fuer Busse. Die gewünschten Koordinaten sind nicht die echten der Sterne, sondern die fuer den Plan, damit das ansehnlich aussieht und nicht wie ein Topf Spaghetti. Alle Verbindungen bidirektional.

Zeichnen eines ungerichteten Graphen aus bekannten Verbindungen oder so ähnlich.

 

[ronny_kruse]

ich habe das so verstanden, dass er eine methode sucht, die sterne in einem 3D-raum so zu verteilen, dass die bekannten verbindungen einzelner sterne etwa gleich lang bleiben

 

[benneq]

Also suchst du im Grunde sowas: http://bl.ocks.org/paulovn/9686202
Nur in 3D ...

Ich glaub, ich würde ganz einfach vorgehen:

nimm den ersten Knoten (k1) und zeichne ihn
nimm alle Knoten, die direkt mit (k1) verknüpft sind und packe sie gleichmäßig verteilt auf eine Kugeloberfläche um (k1)

gehe alle Knoten durch, die direkt mit (k1) verknüpft sind. für jeden (kn):
    gehe alle Knoten durch, die direkt mit (kn) verknüpft sind
    ordne die gefundenen Knoten auf einer Halbkugel (die vom "parent" (=in diesem Fall (k1)) wegzeigt) an

und wiederholen, bis alle verbraucht sind.

... und zwischendurch natürlich Verknüpfungen zu bereits gezeichneten Knoten zeichnen.

Radius der ersten Kugel sollte von der Anzahl an direkten Verknüpfungen mit dem ersten Knoten abhängen.
Bei den weiten Halbkugeln, kann man Winkel (also evtl. 3/4 Kugel oder 1/4 Kugel) und Radius variieren.

Wenn es um Performance geht, sollte man evtl. auf einen Kubus statt einer Kugel setzen.

---

Wenn ich mir das richtig überlegt habe, hier ein Bsp:

k1 ist verknüpft mit k2, k3, k4
k2 ist verknüpft mit k1, k3, k5
k3 ist verknüpft mit k1, k2
k4 ist verknüpft mit k1
k5 ist verknüpft mit k2, k6

k1 zeichnen auf (0,0,0)

k1 Verknüpfungen durchgehen:
k2, k3, k4 zeichnen auf (-1,0,0) (0,-1,0) (0,0,-1) <- nicht gleichmäßig, aber keine Lust auf Formel und rechnen

k2 Verknüpfungen durchgehen:
Linie zu k1 schon vorhanden
Linie zu k3 zeichnen
k5 zeichnen auf (-2,0,0)

k3 Verknüpfungen durchgehen:
Linie zu k1 schon vorhanden
Linie zu k2 schon vorhanden

k4 Verknüpfungen durchgehen:
Linie zu k1 schon vorhanden

k5 Verknüpfungen durchgehen:
Linie zu k2 schon vorhanden
k6 zeichnen auf (-3,0,0)

 

[Nai]

Ich würde so eine einfache Pseudo Physik-Simulation mit folgenden Regeln schreiben:
-2 Sterne ziehen sich an, wenn sie miteinander verbunden sind
-2 Sterne stoßen sich ab, wenn sie sich zu Nahe kommen
Dann das n paar 1000 mal in der Zeit mit explizit Euler oder so integrieren und fertig

 

[asdfman]

Das Einhundertkörperproblem!