3-Dimensional Shortest Path

Hello, I have a question about the shortest path algorithm.

I want to find shortest path in 3 dimensional space(for example, latitude, longitude, and altitude) I think it's possible that using "graphshortestpath" function in matlab is fine.

But in this case it's hard to make a graph matrix and a edge matrix...

So if someone knows that an efficient way to make for shortest path algorithm for 3 dimensional space, please help me.

Thanks in advance!

Answer 1

[Ahmet Cecen]

You are in luck. I have just released a code that does the very exact thing you want to the FileExchange. If you really need to use the toolbox function graphshortestpath, contact me for a version that uses that. Check the earlier sections of the file to find the efficient way to convert volumetric data into a graph, which should be the fastest most efficient way in the west (well while using MATLAB).

Here: http://www.mathworks.com/matlabcentral/fileexchange/55593-tortuosity---percolation---connected-path-calculation-for-3d-structures

[Helio]

Thanks for the reply Ahmet! As you said, now I'm trying to find the efficiency way to convert 3D into 2D. I'll contact you when it got stuck! Thanks again.

[Timothy Turk]

I get the following error when I try to run this. Can you help? I have installed Visual Studio for Windows.

Please Install a Compatible C++ Compiler (Like Visual Studio Compilers for Windows)Not enough input arguments.

Error in Tort3D (line 36)

[nx,ny,nz] = size(Alpha);

[Walter Roberson]

The most common cause for that error would be if you were using an old enough version of MATLAB that function names were still not case-sensitive (quite a while ago!) so that the Alpha was being treated as alpha and that alpha() function was being executed -- the alpha() function requires an input argument.

This in turn would require that Alpha (or alpha) had not been assigned to in the code at a point where the code expected it had been assigned to.

Answer 2

[Walter Roberson]

The A* and Dijkstra algorithms do not care at all about how many dimensions the graph is embedded in: they only care about the connection information and the distances (or the two combined in one.)

[Ahmet Cecen]

This is true, but graphshortestpath and similar functions will almost always require data in the form of an adjacency matrix, which is 2D. The problem here if I relate correctly is not that the graph is embedded in 3D, it is that there is no graph, simply volumetric data like a 3D maze for example: the corridors are 1s and walls are 0s. How do I transform that 3D maze into a 2D adjacency matrix in the most time and memory efficient way possible with MATLAB? That is the problem the submission I refer to solves. The rest is easy-peasy as you mentioned.

[Helio]

Thank you for your reply. Yes I'm with you, so I am trying to find the most efficiency way to transform. If you know a good way to transform considering sets of waypoints, could you please give me some idea?

[Steven Lord]

The shortestpath method for graph and digraph objects that was introduced in release R2015b can work on a weighted graph object. There's an example on that function's documentation page.