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 2 (0.339s) 6 (0.163s) 4 (0.225s) 3 (0.274s)
Elements In Range Elements In Range KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D Full (~span/2) (r=499.5) 59 59 55 7 Half (~span/4) (r=249.8) 238 231 204 28 Quarter (~span/8) (r=124.9) 945 927 813 119 Tiny (~span/1000) (r=1) 98,293 99,231 136,859 98,699
Get Elements In Bounds Get Elements In Bounds KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D Full (size=999.0x999.0) 270 394 359 17 Half (size=499.5x499.5) 1,774 1,812 1,224 69 Quarter (size=249.8x249.8) 6,874 7,157 3,820 361 Unit (size=1) 141,582 145,100 184,680 101,563
Approximate Nearest Neighbors Approximate Nearest Neighbors KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D 500 neighbors 8,170 16,230 12,171 59,089 100 neighbors 67,998 66,044 66,325 123,678 10 neighbors 203,190 195,156 145,400 170,276 1 neighbor 263,680 261,576 143,886 176,123
100,000 entries Construction Construction KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D 100,000 entries 49 (0.020s) 84 (0.012s) 49 (0.020s) 50 (0.020s)
Elements In Range Elements In Range KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D Full (~span/2) (r=199.5) 600 601 585 74 Half (~span/4) (r=99.75) 1,354 1,324 1,202 185 Quarter (~span/8) (r=49.88) 4,641 5,036 4,274 721 Tiny (~span/1000) (r=1) 120,657 120,129 168,546 130,169
Get Elements In Bounds Get Elements In Bounds KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D Full (size=399.0x249.0) 4,494 4,508 4,609 236 Half (size=199.5x124.5) 9,417 11,739 7,955 957 Quarter (size=99.75x62.25) 25,018 31,756 19,444 3,787 Unit (size=1) 172,229 173,621 226,206 136,957
Approximate Nearest Neighbors Approximate Nearest Neighbors KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D 500 neighbors 9,746 9,649 11,279 59,259 100 neighbors 45,035 78,375 48,623 141,809 10 neighbors 224,805 201,634 161,243 191,622 1 neighbor 204,442 272,235 186,148 199,245
10,000 entries Construction Construction KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D 10,000 entries 547 (0.002s) 205 (0.005s) 534 (0.002s) 510 (0.002s)
Elements In Range Elements In Range KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D Full (~span/2) (r=49.50) 5,835 5,923 5,910 716 Half (~span/4) (r=24.75) 22,309 22,365 13,492 2,851 Quarter (~span/8) (r=12.38) 43,600 50,531 36,923 11,864 Tiny (~span/1000) (r=1) 158,469 150,623 212,018 149,034
Get Elements In Bounds Get Elements In Bounds KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D Full (size=99.00x99.00) 44,427 44,160 45,629 2,400 Half (size=49.50x49.50) 138,733 137,563 36,764 9,208 Quarter (size=24.75x24.75) 71,422 99,969 73,188 34,689 Unit (size=1) 217,195 215,448 288,202 161,586
Approximate Nearest Neighbors Approximate Nearest Neighbors KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D 500 neighbors 12,737 12,616 13,946 55,527 100 neighbors 55,274 49,313 78,099 148,808 10 neighbors 227,411 158,790 169,058 209,840 1 neighbor 223,606 265,422 200,809 221,366
1,000 entries Construction Construction KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D 1,000 entries 5,151 (0.000s) 7,776 (0.000s) 4,694 (0.000s) 4,555 (0.000s)
Elements In Range Elements In Range KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D Full (~span/2) (r=24.50) 56,995 56,230 55,896 7,058 Half (~span/4) (r=12.25) 59,112 74,559 55,979 13,922 Quarter (~span/8) (r=6.13) 92,658 104,920 92,486 35,680 Tiny (~span/1000) (r=1) 222,202 220,277 297,368 206,152
Get Elements In Bounds Get Elements In Bounds KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D Full (size=49.00x19.00) 426,624 431,008 373,813 23,621 Half (size=24.50x9.5) 156,916 256,359 117,824 71,241 Quarter (size=12.25x4.75) 246,321 255,452 181,493 157,622 Unit (size=1) 299,240 298,725 399,346 236,769
Approximate Nearest Neighbors Approximate Nearest Neighbors KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D 500 neighbors 41,173 42,778 36,594 59,730 100 neighbors 68,908 67,186 74,762 162,066 10 neighbors 229,540 233,936 192,974 227,546 1 neighbor 306,128 230,085 193,384 228,793
100 entries Construction Construction KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D 100 entries 39,370 (0.000s) 22,675 (0.000s) 14,641 (0.000s) 21,231 (0.000s)
Elements In Range Elements In Range KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D Full (~span/2) (r=4.5) 424,908 350,023 429,776 68,536 Half (~span/4) (r=2.25) 368,298 327,663 232,135 198,728 Quarter (~span/8) (r=1.13) 361,799 333,252 484,465 270,330 Tiny (~span/1000) (r=1) 366,765 339,049 491,007 271,447
Get Elements In Bounds Get Elements In Bounds KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D Full (size=9x9) 1,213,305 1,199,091 1,381,012 193,676 Half (size=4.5x4.5) 366,200 390,340 324,182 296,281 Quarter (size=2.25x2.25) 389,918 419,365 622,169 304,900 Unit (size=1) 377,223 449,661 606,231 303,985
Approximate Nearest Neighbors Approximate Nearest Neighbors KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D 100 neighbors (max) 85,200 110,718 130,989 171,955 10 neighbors 175,016 222,050 233,907 270,041 1 neighbor 178,877 289,379 231,762 284,316
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