Basic idea of octrees:
Space is bounded by a cube. The location and size of this cube in space are arbitrary -- the important part is that it is finite in size. In other words, the values of the points must be bounded -- no infinite points.
D is the dimension of the cube (length of one side).
N is the maximum number of points per node. This should be some reasonably small number.
Start with a root cube with dimension DxDxD. Insert each point into the octree in the following manner:
Code:
insert_point_in_octree(root, point):
if the number of points in root is <= N:
add point to root
else:
split root, if not already split, into 8 subcubes of dimension D/2xD/2xD/2 -
-and divvy points into new subcubes
for each subcube:
if point is in subcube:
insert_point_in_octree(subcube, point)
return
This is like a binary tree, but instead of 2-way branching, we use 8-way branching. And we choose when to split based on how many points are at a node.
Searching the octree is similar, but the logic is more complex, because you have to exclude subcubes which cannot possibly contain points which are "close enough." This is how the octree gets its speed. I leave this difficult part to you