Hallo,
ich arbeite gerade an einem kleinen Projekt, bei dem ein "Netz" so dynamisch wie möglich generiert werden soll. Das heißt: Ich habe einen zentralen Root-Knoten, der mehrere Kindknoten besitzt. Diese Kindknoten besitzen weitere Kindknoten. Momentan ist es noch eine 1:n - Beziehung: 1 Eltern-Knoten hat n Kinder. Später soll jedes Kind auch mehrere Eltern-Knoten und die Kindknoten untereinander Beziehungen haben können.
Jeder Knoten besitzt eine "Spannweite", innerhalb der sich seine Kinder platzieren dürfen.
Ich bin jetzt so weit, dass sämtliche Kinder kollisionsfrei platziert werden können. Im nächsten Schritt möchte ich auch die Pfade mit einbeziehen, so dass es am Ende keine Überschneidungen mehr gibt und alles "sauber aufgedröselt" ist. (Immer unter der Voraussetzung, dass es überhaupt eine Lösung für das vorgegebene Muster gibt.)
Mein Algorithmus sieht momentan so aus:
- Platziere alle Knoten in der Mitte des Bildschirms
- Prüfe für alle Knoten direkt am Root:
------ Kollidiert er mit seinem Elternknoten?
---------- Ja: Vergrößere den Abstand, bis keine Kollision mehr vorliegt
---------- Nein: Prüfe, ob du mit einem anderen Knoten deiner "Schicht" kollidierst
---------------- Ja: Platziere dich innerhalb der Spannweite neu
---------------- Nein: Valide Position erreicht, Knoten wird festgesetzt
------ Wiederhole die Prüfung x Iterationen lang / versuche innerhalb von x Iterationen die Kollisionen auszugleichen
------ Wenn die Kollisionen nicht aufgelöst werden können, erhöhe die Abstände und versuche es erneut
- Wenn alle Knoten direkt am Root eine valide (=kollisionsfreie) Position erreicht haben, baue die nächste Schicht auf
Mein Problem:
Um auch die Pfade richtig zu sortieren, fällt mir nur Brute-Force ein:
Permanent jeden Pfad mit jedem anderen auf Kollision überprüfen. Das klingt für mich aber ziemlich dirty und unperformant.
Geplant sind für das ganze Netz momentan ~ 20 Knoten. Ich würde es aber gern so bauen, dass ich auch ein paar mehr oder weniger reingeben kann, ohne alles zu crashen.
ich arbeite gerade an einem kleinen Projekt, bei dem ein "Netz" so dynamisch wie möglich generiert werden soll. Das heißt: Ich habe einen zentralen Root-Knoten, der mehrere Kindknoten besitzt. Diese Kindknoten besitzen weitere Kindknoten. Momentan ist es noch eine 1:n - Beziehung: 1 Eltern-Knoten hat n Kinder. Später soll jedes Kind auch mehrere Eltern-Knoten und die Kindknoten untereinander Beziehungen haben können.
Jeder Knoten besitzt eine "Spannweite", innerhalb der sich seine Kinder platzieren dürfen.
Ich bin jetzt so weit, dass sämtliche Kinder kollisionsfrei platziert werden können. Im nächsten Schritt möchte ich auch die Pfade mit einbeziehen, so dass es am Ende keine Überschneidungen mehr gibt und alles "sauber aufgedröselt" ist. (Immer unter der Voraussetzung, dass es überhaupt eine Lösung für das vorgegebene Muster gibt.)
Mein Algorithmus sieht momentan so aus:
- Platziere alle Knoten in der Mitte des Bildschirms
- Prüfe für alle Knoten direkt am Root:
------ Kollidiert er mit seinem Elternknoten?
---------- Ja: Vergrößere den Abstand, bis keine Kollision mehr vorliegt
---------- Nein: Prüfe, ob du mit einem anderen Knoten deiner "Schicht" kollidierst
---------------- Ja: Platziere dich innerhalb der Spannweite neu
---------------- Nein: Valide Position erreicht, Knoten wird festgesetzt
------ Wiederhole die Prüfung x Iterationen lang / versuche innerhalb von x Iterationen die Kollisionen auszugleichen
------ Wenn die Kollisionen nicht aufgelöst werden können, erhöhe die Abstände und versuche es erneut
- Wenn alle Knoten direkt am Root eine valide (=kollisionsfreie) Position erreicht haben, baue die nächste Schicht auf
Mein Problem:
Um auch die Pfade richtig zu sortieren, fällt mir nur Brute-Force ein:
Permanent jeden Pfad mit jedem anderen auf Kollision überprüfen. Das klingt für mich aber ziemlich dirty und unperformant.
Geplant sind für das ganze Netz momentan ~ 20 Knoten. Ich würde es aber gern so bauen, dass ich auch ein paar mehr oder weniger reingeben kann, ohne alles zu crashen.
