Given two figures in uniform grid that touch each other. How to find length of shortest path which together with one of figures completely surroundes other figure? Could you suggest some algorithm?
Just in case the question is not clear, I attached example. Given two figures: black and red. In green is 14 units long path that together with black figure completely surroundes the red one.
shortest path
shortest path
 Attachments

 example.png (977 Bytes) Viewed 11065 times
Re: shortest path
The classic shortest path algorithm uses an array of all the unit squares (or points) and iterates one coststep at a time. But you must identify sets of "start" and "end" squares.
Since the figures touch, you could set black start and end squares on each side of the touching points, then subtract unneeded parts of the path at the end. But in some cases the path around the back of the black figure might be shorter than the path around the red. Maybe you could set a prohibited line that goes out the other side of the black figure...
Since the figures touch, you could set black start and end squares on each side of the touching points, then subtract unneeded parts of the path at the end. But in some cases the path around the back of the black figure might be shorter than the path around the red. Maybe you could set a prohibited line that goes out the other side of the black figure...
Re: shortest path
Here's an idea.
1. Start with the grid containing the black and red shapes.
2. Mark the black squares as being distance 0, and use Dijkstra's algorithm to mark all (reachable) empty squares with their distances to the black ones (i.e. mark with a 1 all empty neighbours of the squares marked 0, then mark with a 2 all empty neighbours of the squares marked 1, etc).
3. Look at all the squares that neighbour the red shape.
4. For each white numbered square neighbouring the red shape, draw in green the path from that square to the nearest black. This is easy using the numbers in the squares, since you just move from square to adjacent square and make sure that you go to a lower number in each step.
5. The black and the green squares together now form a shape that encircles the red shape. The outer boundary of this combined shape is the path you are looking for. Count how many green squares are on the outer boundary of this green/black shape, and you are done. You can do this by starting at the northernmost square that is green or black, which is guaranteed to be on the boundary, and then travelling around the shape.
This algorithm will fail if the shortest green path does not touch the red shape at all. This happens if the black almost completely encircles the red, and the green path just closes the gap in the black nearring. If that happens, the boundary in step 5 is nonconvex. To cope with this I think you would need one more step in the algorithm which fills in any dents in the boundary with appropriately coloured squares before you count how long it is, but I haven't worked out the details.
(Edit: fixed typo)
1. Start with the grid containing the black and red shapes.
2. Mark the black squares as being distance 0, and use Dijkstra's algorithm to mark all (reachable) empty squares with their distances to the black ones (i.e. mark with a 1 all empty neighbours of the squares marked 0, then mark with a 2 all empty neighbours of the squares marked 1, etc).
3. Look at all the squares that neighbour the red shape.
4. For each white numbered square neighbouring the red shape, draw in green the path from that square to the nearest black. This is easy using the numbers in the squares, since you just move from square to adjacent square and make sure that you go to a lower number in each step.
5. The black and the green squares together now form a shape that encircles the red shape. The outer boundary of this combined shape is the path you are looking for. Count how many green squares are on the outer boundary of this green/black shape, and you are done. You can do this by starting at the northernmost square that is green or black, which is guaranteed to be on the boundary, and then travelling around the shape.
This algorithm will fail if the shortest green path does not touch the red shape at all. This happens if the black almost completely encircles the red, and the green path just closes the gap in the black nearring. If that happens, the boundary in step 5 is nonconvex. To cope with this I think you would need one more step in the algorithm which fills in any dents in the boundary with appropriately coloured squares before you count how long it is, but I haven't worked out the details.
(Edit: fixed typo)
_{Jaap's Puzzle Page}
Re: shortest path
jaap, I appreciate your help, your idea is cute. Thank you a lot! I just finished programming and it works very well.
Just to add, in step 4 white squares touching the red shape only with corner must be checked too. I didn't mention previously but in my case black and red shapes actually will always have the same shape, so I think algorithm will never fail.
Only instead of Dijkstra's algorithm I implemented a triple cycle  two inner cycles are over all matrix elements and outer cycle is over distances 1, 2, ... . Outer cycle stops when there are no more changes in matrix. I expect that Dijkstra's will be more faster, right?
Just to add, in step 4 white squares touching the red shape only with corner must be checked too. I didn't mention previously but in my case black and red shapes actually will always have the same shape, so I think algorithm will never fail.
Only instead of Dijkstra's algorithm I implemented a triple cycle  two inner cycles are over all matrix elements and outer cycle is over distances 1, 2, ... . Outer cycle stops when there are no more changes in matrix. I expect that Dijkstra's will be more faster, right?
Re: shortest path
Good spot. Otherwise the green/black squares may encompass the red shape without actually forming a closed path around it.juris.c wrote:Just to add, in step 4 white squares touching the red shape only with corner must be checked too.
Yes, but I wouldn't worry about it till you find it to be a problem. By the way, you can stop the outer cycle earlier, namely when all squares neighbouring the red shape (incl. diagonally) have been filled.juris.c wrote:Only instead of Dijkstra's algorithm I implemented a triple cycle  two inner cycles are over all matrix elements and outer cycle is over distances 1, 2, ... . Outer cycle stops when there are no more changes in matrix. I expect that Dijkstra's will be more faster, right?
_{Jaap's Puzzle Page}