Algorithm to find the shortest path and its length for moving between many geometries

Question

I have a set of 2D geometric figures in Cartesian space, as shown in the image. Each geometric figure has a start point and an end point (among other characteristics). For closed geometries, such as a circle, the start and end points are the same and for open geometries, such as lines, both points are different.

I need an efficient way to find the shortest path and its length (red lines), to go from one geometry to the next, starting from an origin O (usually a corner of the bounding box of all geometries) and returning to the same origin point. I already know the length of the geometries (black lines) if needed.

Criteria I have to consider:

1. I can have many more geometries in space than those in the example.
2. Each geometry is visited only once
3. To go from the starting point to the end point of each geometry (or vice versa), you can only go through the geometry itself, that is, to go from point A to point B, you can only go through the path of the circle; to go from point E to point G, you can only go through the path of the curve EG; to go from point J to point F, you can only go through the straight line FJ.
4. Once the start or end point of a geometry is reached, the geometry must be traversed from end to end (this is especially relevant for open geometries since the start and end points are different.)
5. The path must begin in the geometry whose starting point is closest to the origin.

What I currently do is:

• Put all unique points (A, C, E, F, G, H, J) in a list of points. I know that the pair of points E and G or F and J belong to the same open geometry, respectively.
• Calculate the Euclidean distance of all the points in the list, with respect to the current origin O, obtain the closest one and save it (A, in the example of the image).
• As we know that A is part of a closed geometry (a circle), it is taken out of the list of points and A is the new origin point used to find the next closest point and save it (E, in this example).
• Since we know that E is an end of an open geometry, we remove E from the list of points and the new origin point is G (the other end of the same open geometry). This is due to considerations 3 and 4 mentioned above.
• The next closest point is calculated with respect to G (getting H, in the example). And the process is repeated, until the list of points is exhausted.
• At the end, I add up the distances of the line segments OA, AE, GH, HJ, FC, CO.

The problem is that this approach is slow, especially when there are many geometries, since for each iteration I have to calculate the Euclidean distances of each point in the list with respect to the current origin and then obtain the point with the smallest distance.

I wonder if anyone knows of a better approach or an algorithm to find the shortest path (taking into account the above considerations) that might be useful to solve this problem in a better way.

Answer 1

There's actually an easy way to represent the open geometries within an ordinary TSP instance:

• Represent each closed geometry as a single "endpoint" vertex.
• Represent each open geometry as 3 vertices: Two "endpoint" vertices, and a "middle" vertex that is connected only to these two endpoints. (If the TSP solver you use expects a complete graph, you can just assign extremely large values to all but these two distances.)

All endpoint vertices are connected by an edge to all other endpoint vertices.

Because each middle vertex is reachable only from its two endpoints, and in the TSP problem, every vertex must be visited, every valid solution must visit each middle vertex immediately after one of its corresponding endpoints and immediately before the other one. That is, each middle vertex must be traversed in one of two "directions" from its endpoints. The solver is able to choose whichever combination of directions works out best overall.

(Notice that simply representing an open geometry as 2 vertices connected by an edge isn't guaranteed to work, since the solution is not required to contain that edge.)

This means your problem is no harder than TSP -- but as BlueRaja - Danny Pflughoeft pointed out, TSP is already NP-complete, so don't expect a fast (polynomial-time) optimal solution. That said, very large instances of TSP have been solved to optimality by Concorde, though in practice you would probably settle for one of the many good, fast heuristics.