Pro-G

[english]This page shows how to solve a common problem in geometry, with applications in CAD/CAM : How to find the shortest path going through a set of points ?

History

It all started form a “challenge” posted by Cliff Huprich on alt.machines.cnc newsgroup: find the shortest path going through 400 random X/Y points. Some people tried to solve the problem with existing (expensive) tools or simple heuristics.

We took the challenge by considering the problem as a general operations research problem, made some web searches and proposed to use a “Travelling Salesman” approach in some posts summarized below:

This is known as the “travelling salesman” problem.
see http://www.ing.unlp.edu.ar/cetad/mos/TSPBIB_home.html for a complete reference.
What you need is a program that would “sort” your list of points along the shortest path.
—
Made some more research on the “travelling salesman” problem (TSP) that
reminded me good old times at university…

Basically, TSP is a “NP-complete” (even “NP_hard”) problem, which means the absolute optimum path can only be found by trying all possible paths, which results in exponential complexity :  if it takes a time T to solve for N points, it will take N*T to solve for N+1 points. On a powerful PC, if you have more than about 100 points, forget it!

Luckily, there are several approximate methods and algorithms around. See http://w1.859.telia.com/~u85905224/tsp/TSP.htm for very nice, animated web-based solvers that illustrate the most common methods.

The efficiency of the various approximate methods depends on how the points are distributed : they work faster on points that are grouped in clusters or spread along a curve compared to random points.

http://www.math.princeton.edu/tsp/concorde.html is apparently the most efficient code available (check their “benchmarks” link ) but it still takes 7 mins for 1000 points, one hour for 1300, and days for 2000…
So to solve your problem, the first question is : do you accept sub-optimal solutions ?
The second is : how many points do you have ?
And the third : how are they spread in space ? (please send me a sample by e-mail)
—
I could compile concorde on Windows and it works pretty well in 2D now, about 5 secs for 1000 points on my dual AMD 1800.
Will modify it for 3D and ask Princeton if they allow me to release the executable
for free, because their license restricts use to academic research.
—

The “travelling salesman problem” (TSP) in general considers a “cost” for each pair of points (cities).
all you have to provide to the algorithm is simply this cost function.
If the function gives the (euclidian) distance between the points, it will solve the problem discussed here.
In the case where you have highway or routes, you assign them for example the travel time as cost (and even give different costs to the A->B and B->A route), and infinite (or very large) cost to pairs that have no direct route between them, which actually speeds the algorithm considerably up by limiting the search width. This is why TSP algorithms are tested/benchmarked precisely on “symmetric euclidian” problems like the one we have here.

As you see, the TSP approach is very powerful, but I still have a difficulty with the problem posed here as TSP solvers give the shortest *closed* path through all points. For an open path with a given start point, there should be a simple thing to do but I’m not sure which…

Links:

1. http://www.ing.unlp.edu.ar/cetad/mos/TSPBIB_home.html everything on Travelling Salesman Problem (TSP)
2. http://w1.859.telia.com/~u85905224/tsp/TSP.htm very nice, animated web-based solvers that illustrate the most common methods.
3. http://www.math.princeton.edu/tsp/concorde.html concorde solver
4. Kenneth Castelino Roshan D’Souza and Paul K. Wright “Tool-path Optimization for Minimizing Airtime during Machining” http://kingkong.me.berkeley.edu/~kenneth/research/pubs/airtime_minimization_joms.pdf

[/english]

XY Table for a miniature machine tool, with a minimal inertia and without any friction thanks to a flexible structure made of two titanium parts.

Reference:

1. Stuart T. Smith, Derek G. Chetwynd,”Foundations of Ultraprecision Mechanism Design “, 1992, CRC Press, ISBN-2884490019