Finding distance to the closest point in a point cloud on an uniform grid
- by erik
I have a 3D grid of size AxBxC with equal distance, d, between the points in the grid. Given a number of points, what is the best way of finding the distance to the closest point for each grid point (Every grid point should contain the distance to the closest point in the point cloud) given the assumptions below?
Assume that A, B and C are quite big in relation to d, giving a grid of maybe 500x500x500 and that there will be around 1 million points.
Also assume that if the distance to the nearest point exceds a distance of D, we do not care about the nearest point distance, and it can safely be set to some large number (D is maybe 2 to 10 times d)
Since there will be a great number of grid points and points to search from, a simple exhaustive:
for each grid point:
for each point:
if distance between points < minDistance:
minDistance = distance between points
is not a good alternative.
I was thinking of doing something along the lines of:
create a container of size A*B*C where each element holds a container of points
for each point:
define indexX = round((point position x - grid min position x)/d)
// same for y and z
add the point to the correct index of the container
for each grid point:
search the container of that grid point and find the closest point
if no points in container and D > 0.5d:
search the 26 container indices nearest to the grid point for a closest point
.. continue with next layer until a point is found or the distance to that layer
is greater than D
Basically: put the points in buckets and do a radial search outwards until a points is found for each grid point. Is this a good way of solving the problem, or are there better/faster ways? A solution which is good for parallelisation is preferred.
