TL;DR — What Problem This Solves Fast range/bounds/nearest‑neighbor queries on 2D data without scanning everything. Quick picks: QuadTree2D for broad‑phase; KdTree2D (Balanced) for NN; KdTree2D (Unbalanced) for fast rebuilds; RTree2D for bounds‑based data. This document contains performance benchmarks for the 2D spatial tree implementations in Unity Helpers.
Available 2D Spatial Trees QuadTree2D - Easiest to use, good all-around performanceKdTree2D - Balanced and unbalanced variants availableRTree2D - Optimized for bounding box queries Correctness & Semantics QuadTree2D and KdTree2D (balanced and unbalanced) guarantee the same results for the same input data and the same queries. They are both point-based trees and differ only in construction/query performance characteristics. RTree2D is bounds-based (stores rectangles/AABBs), not points. Its spatial knowledge and query semantics operate on rectangles, so its results will intentionally differ for sized objects and bounds intersection queries. Datasets 1,000,000 entries Construction Construction KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D 1,000,000 entries 4 (0.247s) 2 (0.346s) 4 (0.223s) 2 (0.379s)
Elements In Range Elements In Range KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D Full (~span/2) (r=499.5) 58 56 56 7 Half (~span/4) (r=249.8) 234 215 214 28 Quarter (~span/8) (r=124.9) 909 795 785 117 Tiny (~span/1000) (r=1) 8,280 5,565 6,973 6,724
Get Elements In Bounds Get Elements In Bounds KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D Full (size=999.0x999.0) 334 355 314 16 Half (size=499.5x499.5) 1,356 1,367 1,005 66 Quarter (size=249.8x249.8) 3,148 3,183 2,281 322 Unit (size=1) 5,612 5,606 5,577 2,834
Approximate Nearest Neighbors Approximate Nearest Neighbors KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D 500 neighbors 3,023 1,733 2,148 1,855 100 neighbors 2,828 1,863 2,308 1,802 10 neighbors 1,958 1,899 1,641 1,692 1 neighbor 1,961 1,957 1,464 1,465
100,000 entries Construction Construction KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D 100,000 entries 49 (0.020s) 77 (0.013s) 48 (0.021s) 43 (0.023s)
Elements In Range Elements In Range KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D Full (~span/2) (r=199.5) 539 527 536 71 Half (~span/4) (r=99.75) 1,065 1,073 1,012 171 Quarter (~span/8) (r=49.88) 2,494 2,710 2,448 577 Tiny (~span/1000) (r=1) 5,607 5,616 5,660 2,872
Get Elements In Bounds Get Elements In Bounds KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D Full (size=399.0x249.0) 2,462 2,524 2,549 209 Half (size=199.5x124.5) 3,563 3,901 3,304 674 Quarter (size=99.75x62.25) 4,726 4,934 4,519 1,550 Unit (size=1) 5,625 5,658 5,661 2,850
Approximate Nearest Neighbors Approximate Nearest Neighbors KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D 500 neighbors 1,562 1,612 1,236 1,407 100 neighbors 1,861 1,870 1,397 1,439 10 neighbors 1,942 1,904 1,456 1,464 1 neighbor 1,911 1,912 1,461 1,462
10,000 entries Construction Construction KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D 10,000 entries 541 (0.002s) 818 (0.001s) 541 (0.002s) 322 (0.003s)
Elements In Range Elements In Range KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D Full (~span/2) (r=49.50) 2,950 2,951 2,873 579 Half (~span/4) (r=24.75) 4,631 4,548 4,092 1,428 Quarter (~span/8) (r=12.38) 5,146 5,164 5,032 2,339 Tiny (~span/1000) (r=1) 5,581 5,646 5,680 2,865
Get Elements In Bounds Get Elements In Bounds KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D Full (size=99.00x99.00) 5,087 5,167 5,181 1,288 Half (size=49.50x49.50) 5,622 5,652 5,010 2,185 Quarter (size=24.75x24.75) 5,435 5,561 5,414 2,687 Unit (size=1) 5,699 5,709 5,749 2,817
Approximate Nearest Neighbors Approximate Nearest Neighbors KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D 500 neighbors 1,681 1,696 1,304 1,369 100 neighbors 1,893 1,888 1,387 1,445 10 neighbors 1,961 1,955 1,413 1,470 1 neighbor 1,971 1,917 1,422 1,471
1,000 entries Construction Construction KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D 1,000 entries 5,376 (0.000s) 7,429 (0.000s) 4,940 (0.000s) 889 (0.001s)
Elements In Range Elements In Range KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D Full (~span/2) (r=24.50) 5,370 5,367 5,348 2,032 Half (~span/4) (r=12.25) 5,333 5,421 5,199 2,425 Quarter (~span/8) (r=6.13) 5,541 5,567 5,433 2,713 Tiny (~span/1000) (r=1) 5,702 5,619 5,740 2,874
Get Elements In Bounds Get Elements In Bounds KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D Full (size=49.00x19.00) 5,747 5,690 5,800 2,590 Half (size=24.50x9.5) 5,567 5,775 5,629 2,806 Quarter (size=12.25x4.75) 5,629 5,739 5,698 2,842 Unit (size=1) 5,729 5,753 5,751 2,868
Approximate Nearest Neighbors Approximate Nearest Neighbors KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D 500 neighbors 1,862 1,871 1,386 1,412 100 neighbors 1,900 1,893 1,418 1,401 10 neighbors 1,959 1,965 1,468 1,428 1 neighbor 1,970 1,949 1,434 1,434
100 entries Construction Construction KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D 100 entries 43,859 (0.000s) 40,650 (0.000s) 26,954 (0.000s) 1,682 (0.001s)
Elements In Range Elements In Range KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D Full (~span/2) (r=4.5) 5,862 5,829 5,811 2,816 Half (~span/4) (r=2.25) 5,776 5,734 5,688 2,886 Quarter (~span/8) (r=1.13) 5,757 5,723 5,766 2,904 Tiny (~span/1000) (r=1) 5,727 5,583 5,765 2,904
Get Elements In Bounds Get Elements In Bounds KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D Full (size=9x9) 5,846 5,821 5,910 2,817 Half (size=4.5x4.5) 5,742 5,791 5,709 2,848 Quarter (size=2.25x2.25) 5,753 5,686 5,762 2,907 Unit (size=1) 5,684 5,702 5,835 2,898
Approximate Nearest Neighbors Approximate Nearest Neighbors KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D 100 neighbors (max) 1,869 1,918 1,447 1,447 10 neighbors 1,950 1,960 1,476 1,480 1 neighbor 1,968 1,955 1,475 1,478
Interpreting the Results All numbers represent operations per second (higher is better), except for construction times which show operations per second and absolute time.
Choosing the Right Tree QuadTree2D :
Best for: General-purpose 2D spatial queries Strengths: Balanced performance across all operation types, simple to use Weaknesses: Slightly slower than KdTree for point queries KdTree2D (Balanced) :
Best for: When you need consistent query performance Strengths: Fast nearest-neighbor queries, good for smaller datasets Weaknesses: Slower construction time KdTree2D (Unbalanced) :
Best for: When you need fast construction and will rebuild frequently Strengths: Fastest construction, similar query performance to balanced Weaknesses: May degrade on pathological data distributions RTree2D :
Best for: Bounding box queries, especially with large query areas Strengths: Excellent for large bounding box queries, handles overlapping objects well Weaknesses: Slower for point queries and small ranges Important Notes All spatial trees assume immutable positional data If positions change, you must reconstruct the tree Spatial queries are O(log n) vs O(n) for linear search Construction cost is amortized over many queries