I computed the minimum spanning tree of 3D points and now want to extract the path (i.e. node per node) of the whole MST.
I did this with the following code:
DT = delaunayTriangulation(pts);
e = DT.edges;
plist1 = pts(e(:,1),:);
plist2 = pts(e(:,2),:);
diffs = plist2-plist1;
dists = vecnorm(diffs');
G = graph(e(:,1), e(:,2), dists);
[mst, pred] = minspantree(G);
I totally forgot to describe my very special input data. It is data sampled from a rail-bound measurement system (3D Positions), so the MST is almost a perfect path with few exceptions.
The predecessor nodes vector doesnt seem to fit my needs. I would expect the points to be topologically sorted, but this is not the case if I sort the input points using this vector.
Basically, it would be enough for me to just determine the "start" and "end"-nodes of the tree, just like the built-in plot-function does. Then, I could compute the shortest path, which would give me a node list. In other words, I want to extract [19578, 2207] from the mst.
Here is a picture of the plot-function result. If the plot function can do this almost instantly, there must be a way I can do it.
I came up with this solution for now. It does not take too long, but longer than the plot function, which finds the same node-pair as "start" and "end", so I thought there might be a "trick".
function idx = sortMST(pts)
[mst,~] = buildMST(pts);
d1nodes = find(degree(mst)==1);
dists = distances(mst, d1nodes, d1nodes);
maximum = max(max(dists));
idx = bfsearch(mst,d1nodes(i));