CODEWITHSUNDEEP
c++calgorithmnearest-neighbor
con-f-use
con-f-use

Reputation: 4028

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 approximates run even faster. I'm looking for a free C/C++ implementation of those better algorithms.

An ε-Approximate if fine.

Upvotes: 1

Views: 1079

Answers (2)

flob
flob

Reputation: 3908

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.

Upvotes: 2

templatetypedef
templatetypedef

Reputation: 372814

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!

Upvotes: 2

Related Questions