1
$\begingroup$

I have the following points, shapes, and paths. I would like to find a path that goes through all of them:

example

I want a path that first traverses the circle, then traverses the square, then traverses the star in the middle, in that order.

It's simple to go to the circle from the bottom left and around it, hitting each point. However, the second shape (the square) is in the top right corner, so I have to go around the star (so I don't cross it) and traverse the square. Finally, I go to the middle, hit each of the points of the star and done. Once that is done, going backwards is pretty easy.

This is an easy example. In my situation, though, there can be hundreds of shapes in between each of them and I have to go to each shape in the order they are stated.

How do I calculate a path that avoids a particular shape (e.g., the star)? I'm not sure what algorithm to look for. Is it a Travelling salesman problem? A*?

The shapes are defined on a grid. This is what I mean:

Grid representation

"1" means the path must go thru here and "0" is empty space which can be used to get to from one place to another.

$\endgroup$
  • $\begingroup$ Do you have to traverse the points of each shape in a specific order, or is the starting point and traversal order (of a specific shape) arbitrary? If it is fixed, then isn't it just a matter of finding the shortest path from one shape to the next (while avoiding the other shapes, which is a fairly standard problem). $\endgroup$ – Tom van der Zanden Nov 27 '15 at 11:34
  • $\begingroup$ Well, if I have to pass the points in a square considering lower left is 0,0 and upper right is 1,1 I have to do something like: 0,0 to 0,1. 0,1 to 1,1. 1,1 to 1,0. 1,0 to 0,0. I cant do 1,1 to 0,0 as that would make a diagonal line and it would not be a square then. $\endgroup$ – riahc3 Nov 27 '15 at 11:38
  • $\begingroup$ That's not what I asked. I take that you have to presume the shape in clockwise or anticlockwise fashion (no diagonals) but the starting point can be arbitrary? I.e. you get to choose whether you start traversing a shape in the left corner, or in the right corner, or somewhere else? $\endgroup$ – Tom van der Zanden Nov 27 '15 at 11:42
  • $\begingroup$ Initially, the intitial path to go to the first shape (even if it is in the upper right corner) must be started from the lower left. But once I start that path, it doesnt matter if the shapes themselves are done clockwise, counterclockwise, reverse, forward, up, down, etc. If I need to go thru a entire shape again to go to another shape even thought I already did that path, that is fine too. $\endgroup$ – riahc3 Nov 27 '15 at 11:44
1
$\begingroup$

The key step is: get from point $Q$ to shape $S$, while avoiding shape $A$. For instance, point $Q$ might be the last point you visit on the circle, $S$ might be the square, and $A$ might be the star.

This can be solved using breadth-first search or A*. The vertices are the grid points labelled "0". You star the search at point $Q$, and try to find the shortest path to some point on $S$ (while at each step you only go through squares marked 0). You can solve this with either BFS or A*: BFS is simpler to implement, A* will run faster.


If you additionally want to find the shortest path through all of the shapes (something that's not stated in the question), then you can fo the following: for all points $Q$ in shape $S_1$, and all points $R$ in shape $S_2$, calculate the shortest way to get from $Q$ to $R$ while avoiding shape $A$. Then add these as edges to a directed graph (where the length of the edge $Q\to R$ corresponds to the length of the shortest such path). Also add edges $R \to R'$ for each pair of points $R,R'$ in the same shape where you can enter the shape via $R$ and exit via $R'$. Finally, you can compute the shortest path in this directed graph.

$\endgroup$
  • $\begingroup$ This won't necessarily give the global optimum, since it might be more optimal to detour a bit so that you can leave the shape somewhere else. $\endgroup$ – Veedrac Nov 28 '15 at 9:16
  • $\begingroup$ @Veedrac, the original question doesn't say anything about shortest paths, merely that the author wants to find a path. However, if you want the shortest paths, see my edited answer -- I've edited to show how to do that, too. $\endgroup$ – D.W. Nov 28 '15 at 20:20
  • $\begingroup$ Correct; For now, the paths being optimized is irrelevent. First finding the paths is important then optimize. $\endgroup$ – riahc3 Nov 30 '15 at 8:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.