3
$\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.

Improve this question
$\endgroup$
4
  • 1
    $\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
    Commented Nov 27, 2015 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
    Commented Nov 27, 2015 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
    Commented Nov 27, 2015 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
    Commented Nov 27, 2015 at 11:44

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
3
  • $\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
    Commented Nov 28, 2015 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. ♦
    Commented Nov 28, 2015 at 20:20
  • $\begingroup$ Correct; For now, the paths being optimized is irrelevent. First finding the paths is important then optimize. $\endgroup$
    – riahc3
    Commented Nov 30, 2015 at 8:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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