True shortest path in binary image/map

Question

How can i find the true shortest path in a binary image/map?

I have looked into Different algorithms, e.g. Dijkstra and A* but they only yield an approximateion of the the shortest path as all pixels are only connected in a "8 connected" way.

What algorithm can i use to get the true shortest path - The red line in the figure below?

Answer 1

Well, using a 8-connected grid implies that you only can will find paths which advance in the orientations given by the 8-neighbors (0, +/-45, +/-90, +/-135, 180). As you show in the picture attached.

If you are required to solve this problem using A*, Dijkstra or similar, the only way to patch this problem is to increase the variety of angles for your paths, increasing the connectivity of your grid (16 or 32-connected). Even with this, you have limited orientations for your paths.

To solve the problem you are describing in your question, other kind of algorithms are used, like Theta*, Field D* or Block A*. These algorithms are able to find paths in any angle (as you require in your problem) even using a 8-connected grid as basis for the search. Take a look to the Wikipedia entry: Any-angle path planning to have more information about this kind of search.

I hope my answer helps.