guido - Mo 29.11.10 14:51
Titel: Image Pfadoptimierung

---

Hallo,

hab hier folgendes Problem:

Eine Bilddatei, Vektoren liegen vor im Format X/Y/Farbe :Integer;

Gezeichnet sein könnte z.B. in der Reihenfolge: 1 Figur oben links, eine unten rechts, die nächste oben rechts
und die letzte unten links. Das Ergebnix sind logischerweise ein paar unnütze "Leerfahrten"

Diesen Weg gilt es zu optimieren. Im Prinzip also wie eine Plotter-Pfadoptimierung
oder eine Verfahrwegoptimierung für ne CNC.

Hat jemand von euch eine ähnliche Optimierung schon mal gemacht oder hat eine nette Idee ?

Danke und Gruss
Guido

Xion - Mo 29.11.10 15:09

---

Erstmal das banalste:

Brute Force

Du berechnest einfach alle möglichen Entfernungen und nimmst die kürzeste. Das funktioniert, dauert aber eeeeewig.

Aber es gibt da sicher fertige Algorithmen für, man müsste nur den Namen kennen :D

jaenicke - Mo 29.11.10 15:33

---

Das hört sich doch sehr nach dem Traveling Salesman Problem an. Das gab es als Traveling Weihnachtsmann Problem mit diversen Lösungen auch schon bei einem Adventsgewinnspiel hier.

bummi - Mo 29.11.10 18:48

---

Die umgebenden Rechtecke sortieren (y,x)?

delphi10 - Mo 29.11.10 22:26

---

Vielleicht hilft das http://wiki.delphigl.com/index.php/Tutorial_Pathfinding weiter.

Horst_H - Di 30.11.10 00:38

---

Hallok,

TSP mit Christofides ? ANt-algoritm und wie sie alle heissen mögen.
Man stelle sich mal ein O neben C vor.
OC dann wäre es günstig beim C oben anzufangen bis zur Mitte dann zum O zu wechseln, es komplett zu zeichnen und dann wieder zum C zu wechseln, um den Rest fertigzustellen.
Das ist ja ganz schön vertrackt, dass es auch günstig sein kann, einen Linienzug auch zwischendurch zu verlassen.

Gruß Horst