Routing in Graph

Given an image such as below the goal is to find a shortest route from a coordinate to another coordinate on the image space. The route to follow black pixels.

Input black & white image for routing.

Using distance-weighted minimum cost path (MCP) implemented in ACLib it is quite easy to achieve the goal on any image size.

The shortest route found from top-left corner to bottom-right corner.

A close-up view of the top-left corner, i.e., the beginning is shown below.

Close up view of the beginning.

A close-up view of the bottom-right corner, i.e., the end is shown below.

Close up view of the end.

Further reading:

  • https://en.wikipedia.org/wiki/Minimum_routing_cost_spanning_tree
  • http://wiki.gis.com/wiki/index.php/Cost_Distance_Analysis
  • https://en.wikipedia.org/wiki/Shortest_path_problem

Leave a Reply

Your email address will not be published. Required fields are marked *