Good path minimization algorithm 2D in Java and VTK

Question

I would like to find an algorithm for path minimization with some constraints in Java with VTK. As input I am going to give an area for the polygon which is constant, the center of mass of the polygon, and a cost image. As output I'd like a list of points which compose a path in 2D that is the minimal path length on the cost image satisfying the two constraints of specific area and center of mass. Does anyone know of a way to do this with Java and VTK? I was looking at building off of vtkDijkstraImageGeodesicPath, but I'm not sure even where to start. Honestly, my math in this field is rusty.

Thanks

Answer 1

As mentioned it sounds like the travelling salesperson problem. One way I have found to get reasonable answers is to start with three nodes (only one possible solution) and then for each subsequent node work out where it is cheapest to insert the node in the existing path. It works in n^2 time and is certainly not going to give you the best solution, but it should give reasonable solutions.