A data structure to handle moving points contact and containment within bounding boxes?

Question

I have many points in space moving over time. They move in space full of AABB bounding boxes (including nested ones, there are less BBs than points) I wonder if there is a data structure that would help with organization of points getting into bounding boxes detection.

Currently I thought of a kd-tree based on boxes centers to perform ANN on points movement, with boxes intersection /nesting hierarchy (who is inside /beside whom) for box detection.

Yet this is slow for so many points so I wonder if there is some specialized algorithm/data structure for such case? A way to make such query for many points at the same time?

Answer 1

I would suggest using some kind if quadtree. Basic quadtrees are already quite good with fast deletion/insertion, but there are special variants, that are better:

• The Quadtree proposed by Samet et al uses overlapping regions, which allow moving objects to stay in the same node for longer, before requiring reinsertion in a different node.
• The PH-Tree as technically a 'bit-level trie'. It basically looks like a quadtree, but has limited depth (64 for 64bit values), no reinsertion/rebalancing ever and is guaranteed to modify at most two nodes for every insertion or removal. At the same time, node size is limited by dimensionality, so maximum 8 points per node for 3D points or 64 entries when storing points and rectangles (boxes). Important for your case: Very good update performance (better than R-trees or KD-trees) and very good window-query performance. Window-queries would represent your AABBs when you look for points that overlap with a AABB. Moreover, you could also store th AABBs in the tree, then any window-query would return all points and other AABBs that it overlaps with (if that is useful for you).

Unfortunately, I'm not aware of any free implementation of Samet's quadtree. For the PH-Tree, you can find a Java version on the link given above and a C++ version here. You can also look at my index collection for Java implementations of various multidimensional indexes.