What's the best way to store 3D point cloud data, optimising for time it takes to find all the points in a sphere of 3D space, and also for time it takes to insert new data points into the data set?
I have a cloud of 3D point data (with each point also including some further attached data), and need to be able to query it to quickly find all the points within a user-specified sphere of 3D space, as well as to quickly add points to the data set.
My current implementation uses a naive linear array of data points, but unsurprisingly, that's not scaling well as my data set grows.
My priority is speed, both for finding points in the cloud and for inserting new points into the cloud (I'd really like to avoid needing to rebalance trees after every insertion, if I can). I never delete points from the data set, so speed for point removal isn't important at all. Memory usage also isn't important -- I'm quite happy to throw memory at this problem, if it'll speed things up!