On Sat, 10 Sep 2011, Stuck Developer wrote:
This ought to be a classic problem but I haven't found a solution yet... Conceputally, I'm trying to find the shortest paths between all polygons within a maximum weighted distance over a grid of friction weights (as well as the total weighted distance of each of these shortest paths). The grid with all the weights (a "friction" value representing the weight to move over that particular grid cell) is currently used to create a network with one vertex per grid cell and edges to its immediate eight neighbours (in the cardinal and diagonal directions). The weight of each edge is calculated to the average weight of the vertex and its neigbours in the four cardinal directions and multiplied by sqrt(2) in the diagonal directions to compensate for the longer euclidean distance. Conceptually again, on this grid, there are a bunch of polygons. These are then made up ofcontiguous groups of vertices. Each polygon could thus be considered a set (or a component) of vertices with a unique id for each polygon. The problem now is to find the shortest path over the weighted grid between the edges of all polygons within a maximum weighted distance from each other. NOTE that the shortest path between two polygons should be able to pass through the weighted grid cells of other polygons along the way when these other polygons are not considered being source or target "vertex sets". I first tried to solve this by looping through all of the polygons and finding the shortest path between some representative vertex (e.g. the centroid grid cell) inside a source polygon to a representative vertex within each possible target polygon. I did this by setting all of the grid cell weights to zero within each of the two polygons, running the dijkstra_shortest_paths between their representative vertices and then resetting the weights within these two polygons before solving it for another pair of polygons. This actually works but the search goes bezerk within the polygons where all the edges have a cost of zero, and if these polygons are big enough, I run out of memory (I guess the shortest path becomes too long...).
You can give the internal edges some tiny (but non-zero) weight such that no path within a single polygon will be long enough to affect the overall results.
I'm thinking this should be possible to solve by instead initializing all of the vertices within each source polygon to "discovered" (i.e. black) somehow and initializing the priority queue and the cost in some corresponding manner. I just don't know how. Then there is the question of knowing when the shortest path to the target polygon has been reached... And thirdly if it would be possible to stop the search when a maximum weighted distance has been reached.
You can initialize vertices to black and add them to the queue; see dijkstra_shortest_paths_no_init on URL:http://www.boost.org/doc/libs/1_47_0/libs/graph/doc/dijkstra_shortest_pa... for details. Stopping the search is usually done by adding a visitor that throws an exception when a target distance (or a given vertex) is reached. You might also want to try A* search (URL:http://www.boost.org/doc/libs/1_47_0/libs/graph/doc/astar_search.html) if you have a heuristic for estimating path lengths to target vertices. The example on that page shows how to terminate the search at a target vertex; libs/graph/example/astar_maze.cpp in the Boost source tree has another A* example. -- Jeremiah Willcock