Finding a a path between two points on a 3d surface that proceeds through lowest value points.

Hello,

I have data (100X50 array for X, Y and Z coordiantes ) corresponding to the surface shown in the below image. I am interested in obtaining paths from flat region (right side yellow circle) of the surface to the minima at red and brown cricle on the left side of the surface. Only condition is that the path should proceed through lowest value points along the Z axis. I could obtain one path connecting yellow and red circles by using "min" function in matlab. I tried find peaks in order to obtain the other path (shown with black arrow in the image). But, the well around the brown circle is very shallow resulting the findpeaks gives only one peak at the region of red circle. Could you please help me to obtain the second path that connects yellow and brown circles. I have also attached my data file. "Shortestpath" function in matlab might be useful for this purpose. I am however not sure how to use it.

These type of paths are referred as "minimum energy paths" in chemistry, assuming that the Z-axis is energy and X- and Y-axis represent molecular coordiantes. In other words, I am looking for a steepest descent path between yellow and brown circles.

Thank you very much for your time

Regards,

Mahesh

[Mathieu NOE]

it would help if you could post the code and "Shortestpath" function

Answer 1

[Kanishk]

Hi Mahesh,

I understand you are interested in locating all local minima and finding a path through them.

To locate all the local minima in your surface plot you can use ‘imregionalmin’ along with ‘find’ function to get the indices of all minima.

[Xq, Yq] = meshgrid(unique(X), unique(Y));
Zq = griddata(X, Y, Z, Xq, Yq);
minimaIndices = find(imregionalmin(Zq));

To find a path to these points, you can implement pathfinding techniques. One effective method is Dijkstra’s algorithm, which explores all possible paths from the starting point, ensuring that the shortest path to each node is found. This approach is highly accurate but can be computationally intensive, especially for large datasets.

To implement this, you need to discretize your surface into a grid where each node represents a point on the surface, and the edges represent possible paths between these points with weights corresponding to the Euclidian distance between the points. After creating a graph from the points on the surface, you can use the ‘shortestpath’ function to get the desired path.

startNode = sub2ind(size(Xq), 20, 100); 
shortestPaths = cell(1, numel(minimaIndices)); 
for k = 1:numel(minimaIndices) 
    endNode = minimaIndices(k); 
    [path, ~] = shortestpath(G, startNode, endNode); 
    shortestPaths{k} = path; 
end 

I was able to find these paths using ‘shortestpath’ function to the local minima in the data.

Another approach is to sacrifice accuracy for speed by using gradient descent. This method is faster as it does not explore all possible paths but instead follows the gradient to find local minima. However, it may not always find the shortest path as it can get stuck in local minima that are not the global minimum.

Please go through the following documentation pages to learn more about ‘imregionalmin’ and ‘shortestpath’:

• https://www.mathworks.com/help/images/ref/imregionalmin.html
• https://www.mathworks.com/help/matlab/ref/graph.shortestpath.html

Hope this helps!

Thanks

Kanishk

[Mahesh]

Hi Kanishk,

Thank you very much!

This is exactly, I was looking for. I will implement this for my data and get back to you if I need more help.

[Mahesh]

@Kanishk, could you please share your matlab code that was used to get the above surface along with the minimum energy paths. Thank you!