spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Hi,

folgende Problemstellung:

Ich habe eine Pointcloud, in welcher die Punkte mehr oder weniger zufällig angeordnet sind (in der Realität kann das auch eine Ansammlung von Polylines sein, aber der Einfachheit halber belasse ich das mal bei Punkten). Die Punkte in dieser Wolke sollen nun optimiert werden, d.h. sie sollen ausgehend von der rechten oberen Ecke in eine Reihenfolge gebracht werden, in der möglichst nur sehr kurze Sprünge zwischen den Punkten ausgeführt werden.

In einem ersten Wurf habe ich das so realisiert, dass einfach immer der zum zuletzt bearbeiteten nächstgelegene, noch nicht neu angeordnete Punkt gesucht wird. Das verkürzt die Sprünge zwischen den Punkten schon enorm, allerdings scheint mir das Ergebnis nicht optimal zu sein. So kann es passieren, dass erst mal alle Punkte in einer Ecke bearbeitet werden, dann aber, um aus dieser Ecke heraus zu kommen, ein sehr großer Sprung ausgeführt werden muss. Hier habe ich das Gefühl, dass es _insgesamt_ noch kürzer ginge, wenn man an manchen Stellen eben nicht den nächstgelegenen Nachbarn sucht, sondern auch mal einen etwas weiter entfernten.

Nur: wie kriege ich die Suche nach so einer Route gebacken? Prinzipiell kann ich nach jeder Suche nach dem nächstgelegenen Punkt ja auch noch nach einem etwas weiter entfernten Punkt suchen, um mit diesem zu ermitteln, wie da das Gesamtergebnis wäre. Problem: ich muss für jeden Punkt UND jede Alternative den kompletten Algorithmus durchlaufen lassen. Das wäre dann prinzipiell für jeden nachfolgenden Punkt auch noch mal notwendig, was den Speicherverbruch und die Rechenzeit explodieren lassen würde. Und dabei weiß ich noch nicht mal, ob es genügt, nur eine alternative Möglichkeit zu untersuchen, prinzipiell können ja auch noch weiter entfernte Punkte interessanter sein.

Welche Alternativen gibt es hier, um so eine Wegoptimierung schneller und weniger Ressourcenaufwändig hinzubekommen?