Finding distance to the closest point in a point cloud on an uniform grid

Posted by erik on Stack Overflow See other posts from Stack Overflow or by erik
Published on 2010-04-29T06:19:13Z Indexed on 2010/04/29 6:57 UTC
Read the original article Hit count: 418

Filed under:

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.

© Stack Overflow or respective owner

Related posts about algorithm