This repository aims to show a new method by upward searching for efficiently searching a quadtree.
The combination of a loose quadtree with a multilayer grid enables O(1) time complexity for insertion. Based on this feature, we can rapidly determine the insertion position for the search region. From this point upwards to the top, the path is predetermined, requiring only the search of a 3x3 area along this path. Consequently, a significant number of intersection checks can be skipped. For the remaining levels, the coordinates of nodes intersecting with the search region can be directly calculated, eliminating the need for individually checking each node for intersection.
- Very fast search
- Smaller size for each node
- Items found are relatively ordered in terms of size
- Low space utilization when there are fewer entities
- Looseness can only be 2
quadtree.rs is a normal quadtree implementation. grid_loose_quadtree.rs is a loose quadtree combined with a multilayers grid, which also implements the up-search function. Additionally, up_search_quadtree.rs is the result obtained by retaining only the up-search function and optimization based on grid_loose_quadtree.rs.
up_search_quadtree_original.rs is the original idea of up-search quadtree, which is based on a normal (non-loose) quadtree. It achieves O(1) insertion by an O(1) lowest common ancestor finding approach. Although using the up-search method, there is basically no performance improvement. However, this file may be helpful in understanding the up-search method, as it is simpler than the current version.
cargo benchSearch 10000 times among 10000 balls of different sizes using the bounds of each of them:
| Quadtree | GridLooseQuadtree | UpSearchQuadtree |
|---|---|---|
| 7.08ms | 4.79ms | 2.82ms |
Of these, the first two results are obtained using the traditional method.