shortest path

Arrangements, sorting, packing, partitions, critical path analysis, networks, graphs, ...
Post Reply
juris.c
Posts: 23
Joined: Sat Oct 24, 2009 10:18 am

shortest path

Post by juris.c » Sat May 26, 2012 11:52 pm

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.
Attachments
example.png
example.png (977 Bytes) Viewed 11065 times

thundre
Posts: 356
Joined: Sun Mar 27, 2011 9:01 am

Re: shortest path

Post by thundre » Tue May 29, 2012 2:36 pm

The classic shortest path algorithm uses an array of all the unit squares (or points) and iterates one cost-step 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...
Image

User avatar
jaap
Posts: 540
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: shortest path

Post by jaap » Tue May 29, 2012 3:32 pm

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 northern-most 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 near-ring. If that happens, the boundary in step 5 is non-convex. 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)

juris.c
Posts: 23
Joined: Sat Oct 24, 2009 10:18 am

Re: shortest path

Post by juris.c » Wed May 30, 2012 3:14 pm

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?

User avatar
jaap
Posts: 540
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: shortest path

Post by jaap » Wed May 30, 2012 5:46 pm

juris.c wrote:Just to add, in step 4 white squares touching the red shape only with corner must be checked too.
Good spot. Otherwise the green/black squares may encompass the red shape without actually forming a closed path around it.
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?
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.

Post Reply