Information about NearestNeighbor function

I need to learn the algorithm behind the MatLab NN functions (on delauney triangulations). I need to program this in java so I would like any help pointing to an algorithm or a library.

Possibly a solution different than CGAL java bindings.

any help is greatly appreciated.

Answer 1

[José-Luis]

As far as I understand, Matlab uses qhull for delaunay triangulations. Is there a particular reason you want to use the qhull algorithm? The source code is freely available, but it's written in C++. Beware that it's not an insignificant amount of code and rewriting it all in Java is an ambitious project.

You are probably better off using JNI, but even that might require quite some work. I would advise not to try reinventing the wheel, unless you have compelling reasons to do so.

If you want to know what other algorithms can be used, then I would recommend looking at any computational geometry book.

[Rasael]

Thank you for your answer.

I already have made the triangulation myself (since I am triangulating an image there is no need of delauney).

I am in need of learning how the nearest neighbor function works on a delauney triangulation class (point to triangular surface). Specifically, an optimized algorithm.

[José-Luis]

I don't understand. If you don't have a Delaunay triangulation, how do you expect to get the nearest neighbors (in the euclidean sense) from it? The closest points would then not be guaranteed to be connected by edges.

Finding the closest points, given a Delaunay triangulation would amount to an iterative search of the connected points, calculating the euclidean distances for each iteration. If you are interested in a larger number of points, it might be more efficient to calculate all the euclidean distances between the point you are interested in and the rest from the get go.