Good data structure for euclidean 3d data queries?

Question

Hi guys,

What's a good way to store point cloud data so that it's optimal for an application that will do one of these two queries?

1. Nearest (i.e. lowest euclidean distance) data point to (x,y,z)
2. Get all the points inside a sphere with radius R around a point (x,y,z)

The structure will only be filled once, but read many times. A lowish memory footprint would be nice as I may be dealing with datasets of > 7 million points, but speed should be of primary concern. A library would be nice, but I wouldn't mind implementing it myself if it's something doable with limited expertise in the area.

Thanks in advance!

Answer 1

A Kd-Tree you get O(log(n)) nearest neighbor, and usually range queries will be fast.

There are a bunch of libraries referenced there. I have not used any of them.

You might also look at CGAL. I have used CGAL for other things, it is tolerably fast, extremely comprehensive, but the documentation will drive you to drink.

Answer 2

A huge portion of the decision in data structures will depend on the spatial organization of the data. For example, highly clustered data tends to have different performance charateristics in kd-trees than evenly distributed data.

KD-Trees are very good for both of these queries.

Octree can be a good option in many cases, as well, and is potentially easier to implement.

There are many libraries out there that do this, using various algorithms. Searching for k-nearest neighbor searching will reveal many useful libraries. I've had pretty good luck with ANN in the past, for example.