Approximate for average distance to nearest neighbour?

And another algorithm I'm looking for: A free C/C++ implementation of the average distance to nearest neighbour problem.

So basically I have a cloud of points in 3D and I want the average over the distances between all points and their respective nearest neighbours. So easiest way to do this would be to find the nearest neighbour for every point, calculate the distance of that neighbour to the point, and devide the sum of those distances by the number of points. However, there are much better algorithms, as this has much redundancy and ap开发者_开发百科proximates run even faster. I'm looking for a free C/C++ implementation of those better algorithms.

An ε-Approximate if fine.

---

The C++ library FLANN allows you to do "fast approximate nearest-neighbor searches." It's written in C++ and claims to be one of the fastest implementations of this sort of search available.

Hope this helps!

---

You might try a Quadtree, as described in this question. There are many implementations for your problem in other 3D/2D graphic libraries, too.

I used GEOS, the 'Geometry Engine, Open Source' once in a project some years ago and was very satisfied.