Kollisionsabfrage mehrerer Pfade |
| 01.02.2015, 15:12 | cassidy | Auf diesen Beitrag antworten » |
| Kollisionsabfrage mehrerer Pfade vorweg: Ich bin kein Student und das Ganze ist keine Hausaufgabe, sondern ein eigenes just for fun-Projekt. Ich arbeite zurzeit an einem Programm, welches mir eine netzartige Struktur generieren soll. D.h.: - es gibt einen zentralen Root - am Root hängen mehrere Kindknoten - jeder der Kindknoten hat weitere Kinder - momentan noch 1:n - 1 Elternknoten hat mehrere Kindknoten. Ich bin jetzt so weit, dass die Knoten so lange neu platziert werden, bis sie nicht mehr miteinander kollidieren. Als nächstes möchte ich auch die Pfade mit einbeziehen, sodass es am Ende keine Überschneidungen mehr gibt. Momentan fällt mir dazu nur Brute-Force ein: Immer wieder jeden Pfad mit jedem anderen auf Kollision überprüfen, bis keine Kollisionen mehr vorhanden sind. Das scheint mir aber sehr "dirty" und unperformant. Gibts dazu vielleicht auch bessere Ansätze? Mein Algorithmus für die Knoten ist momentan so aufgebaut: (Jeder Knoten besitzt eine Spannweite, innerhalb dessen sich seine Kinder platzieren dürfen.) - 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 (rekursiv) die nächste Schicht auf |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
| Die Neuesten » |
|
