Re: How to find closest point(s) around a specific point in point cloud?

On Mar 30, 1:17 pm, robert <robert.kj.karls...@xxxxxxxxx> wrote:
I can't find any site with information about the simplest way to
locate the n number of closest points adjacent to a point in a 3d
point cloud with scattered data.

Basically, I've got an array, call it V, with a couple of hundred
positions [x,y,z] and a value (eg [0-100).

Let's say I wanted to pick the 5 closest points around a specific
point, call it P, with a value like [x,y,z] = [10,20,30]

Hmmm ... a couple hundred points ... almost doesn't seem worth
optimizing this, but, what the hell, let's say you want to know these
points with ridiculously high performance.

The best thing I can think of is to use a voxel bounding box
partition. So you would make a voxel-space data structure that gives
the list of points in each voxel. So for any two adjacent voxels, the
minimum distance between a pair of points, on in each, is W =
2*sqrt(3)*voxelresolution. (You can do smaller than this depending on
the position of P within its voxel, but I leave that as an exercise to
the reader.)

So the idea is that you would examine spherical shells around the
point P in radius steps of size W. Basically any voxel in a shell
less than or equal to the current radius, but not already visited (so
you would want to maintain a boolean 3D array to keep track of this)
would be examined for the number of points in the list, and just
accumulated until the value, say n, number of points on the list have
been added. Then proceed for one more shell iteration and add any
incidental points to the list.

This will give a candidate set of points that are no more than W
farther than the nth furthest point away from P. Now compute the
distances between P and each of the candidate points, and store them
in an array. Then use the median select algorithm to find the
smallest n values in the array, and back map them to the closest n
points in this list, which will be your answer.

In general, this algorithm will be limited either by the number of
points that are captured in the first pass that are in excess of the
first n points (which is why you want to decrease the size of W), or
the amount of time wasted looking at empty voxels (which will depend
on your voxel resolution). Intuitively I would guess that the ideal
voxel resolution would have about n/27 number of points in each
average voxel, but you would want to play with this (it will almost
surely be n*(some factor) which works best) to see what works best.

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/
.

Relevant Pages