Zitat von
CalganX:
Problem ist, dass sich in jeder Iteration alle Objekte bewegen (unterschiedliche Richtung, unterschiedliche Weite, etc.). Bleibt es dann immer noch so perfomant, wie du sagst?
Nein, das ändert natürlich alles.
Man kann bei der Entfernungsermittlung die Hälfte einsparen, werden man beachtet, das Entfernung von A->B gleich B->A ist.
Zitat von
CalganX:
Mir ist gerade wieder eingefallen, wie ich die Delaunay-Triangulation verwenden könnte
Das wäre natürlich eine wirklich grosse Einsparung.
Pro Punkt müssen in der Regel dann nur noch 3 bis 8 Vektoren überprüft werden, um das Minimum zu finden.
Ich würd's einfach mal mit meiner "Brute-Force" Methode probieren; könnte mir vorstellen, dass das trotz der vielen Berechnungen und Vergleiche doch noch recht schnell sein kann.
Wenn die Anzahl der Objekt verzehnfacht wird, verhundertfacht sich der Aufwand ~O(N^2)
