Graphentheorie, Optimierung eines Graphen

[glkgereon]

Hallo,

Ich habe mal ein ziemlich allgemeines Problem, losgelöst von einer bestimmten Implementierung (ok, am Ende soll es in Java implementiert werden und die Anwendung soll am Ende der Datenspeicher für eine Physikengine sein, aber das ist hier erstmal egal :wink: ).

Ich habe eine (sehr große) Menge an Objekten, welche alle eine bestimmte Position in einem dreidimensionalen Raum besitzen.
Diese wird mittels eines Vektors mit drei Fließkommawerten angegeben.
An die zu verwendende Datenstruktur habe ich folgende Ansprüche:
- effiziente Verwaltung
- keine "harten" Grenzen, also keine Einteilung à là "Alle Objekte zwischen (0,0,0) und (1,1,1) in eine Liste"

Ausserdem sind folgende Operationen nötig:

höchste Priorität:
- Alle Objekte mit Abstand < x zu einem anderen Objekt holen
- Objekt über geringe Distanz verschieben

mittlere Priorität:
- Neues Objekt an gegebener Position einfügen
- Objekt löschen

niedrigste Priorität:
- gesamte Datenstruktur speichern / laden

So, nach etwas rumprobieren mit verschiedenen Konzepten, bin ich nun auf das verfallen, was ich anfangs sofort als "zu aufwendig und zu kompliziert zu warten" verworfen hatte.

Meine Idee ist ein Graph, in dem jedes Objekt mit den x (sagen wir mal 3-5) räumlich nächstgelegensten Objekten verknüpft ist.
Diese Idee habe ich erstmal als 2D-Struktur implementiert, dann kann man sie zu Debugzwecken auch mal schön visualisieren :-)
Das funktioniert auch zunächst erstmal ganz gut, 25 zufällige Punkte sähen dann zum Beispiel aus wie in Anhang 1.
Der Code findet sich im Anhang 2...

Nun habe ich aber folgendes Problem: Der Graph ist alles andere als optimal!
Man sehe sich nur "Root", "4" und "5" an, so ist klar, dass 4 nicht direkt mit Root verbunden sein sollte, sondern über 5.
Gibt es einen Algorithmus, der diese Fehler ausbügelt? (Am besten würde dieser direkt beim Einfügen von 5 die Verbindung zwischen 4 und Root kappen...)
Hierzu habe ich mal versucht eine Lösung zu schreiben (Siehe Code :wink: ). Die funktioniert zwar teilweise, teilweise aber auch nicht... Um genau zu sein hat sie noch ein recht seltsames Eigenleben...

Ein weiteres Problem sind die Mehrfachverknüpfungen...
Meines Erachtens macht das ganze Konzept nur Sinn, wenn es eben kein Baum ist, wie momentan, sondern ein Graph. Wie würde ich einfach und schnell Verbindungen zwischen zB 9 und 11 herstellen? (Also erkennen, dass ich hier welche herstellen sollte...)
Auch das sollte möglichst beim Einfügen passieren, und nicht große Teile des Baums durchlaufen müssen (Ich gehe davon aus, dass der Baum nachher mehrere hundert Einträge enthält.


Hat irgendwer da eine gute Idee, wie man das besser machen könnte oder sollte oder wie man die Mehrfachverknüpfungen in den Griff bekommt?