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

Paul Hsieh wrote:
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.)

Interesting, for a random cloud of points, would this be more efficient
than a linear search? If so, is there a cloud size where one approach
becomes more efficient than the other?

With either approach, you have to visit each point at least once and
calculate a distance.

--
Ian Collins.
.

Relevant Pages