Create Line Paths Between Non-Uniformly Distanced Neighbors

Hi all,

I have about 10000 points scattered. I would like to form a line between every 2 points such they creates paths as we can already picture it in our mind by seeing the graph. The indices of those points are known. The problem is that the distance between the two or three neigboring points are not uniform, and thus setting a tolerance (e.g. within radius of a certain value form a path) would seemed not to work.

Eventually what I want is the matrix containing path indices (first column), node A of the each path (second column), and node B of each path (third column).

Is there any premade function in matlab that does this? Or is there any method to solve this? I don't have graph toolbox in my Matlab (e.g. graph, neighbors), but I can try to get them if needed.

Please suggestion. Thanks in advance.

Answer 1

[John D'Errico]

No, there are no premade functions to do it (that I know of.) As well, you are going to have a difficult time identifying things like bifurcations. Things that seem trivial for the eye/brain to do are often far less trivial to write computer code to do robustly.

I'd suggest starting with the CRUST algorithm. Do some reading here:

http://www.enseignement.polytechnique.fr/informatique/INF562/Slides/Slides_Reconstruction.pdf

http://www.cs.ubc.ca/~sheffa/dgp/ppts/crust.pdf

You MIGHT be able to find some viable code for CRUST in MATLAB, but what I did see was pretty crude.