Data Structures
Requirements:
- access point values (coordinates)
- find neighbours
- within a certain radius “r”
- the “k” nearest neighbours
Storing Values
- values per element
- unique index for every point,
Octrees
Hierarchical spatial data structure
- divide-and-conquer
- binary subdivision
each node contains:
- dimensions [xmin,xmax] x [ymin,ymax] x [zmin,zmax]
- pointers to eight children
- empty for leaf-nodes
- unique label