Advice on data structure for point clouds [closed]

Question

I want to use a data structure in C# to store three dimensional points and use nearest neighbor search, radius search and possibly other operations. The goal is to implement segmentation, triangulation, filtering (median and possibly others), measurement, matching and maybe other things.

I found k-d trees and octrees to be the most used data structures for this job. Since it is necessary that points can be added or removed from the point cloud, octrees seem the way to go. Do you know of a reason against them?

However, since it will be necessary to add new points, if one is outside the boundaries of my octree, I would have to create the whole tree again because my dimensions have changed. Is there a way around this? This sounds very costly and is a scenario that right now I can not say if it will happen often or not, but want to be prepared for.

Is there a website/paper about octrees and operations on them, especially knn and radius search? I found libraries like PCL, but a description of the operations and not just code would be a big help.

Answer 1

nice blog on octree algorithms https://geidav.wordpress.com/2014/07/18/advanced-octrees-1-preliminaries-insertion-strategies-and-max-tree-depth/

here is the bible on space aware datastructures Foundations of Multidimensional and Metric Data Structures – August 22, 2006 by Hanan Samet