Finding the distance to the nearest point in a point cloud on a single grid

Question

I have a three-dimensional grid of size AxBxC with equal distance, d, between points in the grid. Given multiple points, what is the best way to find the distance to the nearest point for each grid point (each grid point should contain the distance to the nearest point in the point cloud), given the following assumptions?

Suppose that A, B and C are quite large with respect to d, giving a grid of perhaps 500x500x500 and that there will be about 1 million points.

Also suppose that if the distance to the nearest point extends to the distance D, we do not care about the nearest distance of the point, and it can be safely set to some large number (D can be from 2 to 10 times) / p>

Since there will be a large number of grid points and search points, a simple comprehensive:

for each grid point:
   for each point:
     if distance between points < minDistance:
       minDistance = distance between points

not a good alternative.

I was thinking of doing something according to:

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 the buckets and do a radial search outward until the points for each grid point are found. Is this a good way to solve a problem or are there better / quicker ways? A solution suitable for parallelization is preferred.

Answer 1

, , , , . | Grid | = N, | | = M, O (N lg M), N , ( ) O (lg M).

. , . D , , , .

O (N + (D/d) ^ 3 M), , D/d .

D/d , , . , 5 1 , " " , , . , ( , , ) , " " , , , - " " .

Answer 2

octrees. , , , .

Answer 3

() , . , . , octtrees, kd- R-.

Answer 4

, , , , , . 3D- - . , .

, - , , , . ( ) . .

: -- .

Answer 5

, :
. python:

S = set of 1m startpoints
near = grid 500x500x500 -> nearest s in S
    initially s for s in S, else 0
for r in 1 .. D:
    for s in S:
        nnew = 0 
        for p in shell of radius r around s:
            if near[p] == 0:
                near[p] = s
                nnew += 1
        if nnew == 0:
            remove s from S  # bonk, stop expanding from s

" " 1d (bonk left, bonk right); 2d/3d .
/ :

near = grid 500x500x500 -> { dist, nearest s in S }
    initially { 0, s } for s in self, else { infinity, 0 }
for s in S:
    for p in approximatecube of radius D around s:
        if |p - s| < near[p].dist:  # is s nearer ?
            near[p] = { |p - s|, s }

"approximatecube" DxDxD, , ( 2d)

0 1 2 3 4 
1 1 2 3 4 
2 2 3 4 4
3 3 4 4
4 4 4

fwiw, , 500 ^ 3/1M ~ 2 ^ 7 ~ 5 ^ 3 . , 5x5x5 1M . , ~ 1/e - .