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:
- I can have many more geometries in space than those in the example.
- Each geometry is visited only once
- 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.
- 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.)
- 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.