Finding a a path between two points on a 3d surface that proceeds through lowest value points.
34 views (last 30 days)
Show older comments
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.
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/1737691/image.png)
Thank you very much for your time
Regards,
Mahesh
1 Comment
Accepted Answer
Kanishk
on 19 Aug 2024 at 4:00
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.
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/1755254/image.png)
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
More Answers (0)
See Also
Categories
Find more on Interpolation in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!