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.362s) 5 (0.195s) 1 (0.745s) 3 (0.313s)
Elements In Range Elements In Range KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D Full (~span/2) (r=499.5) 100 98 92 16 Half (~span/4) (r=249.8) 406 409 405 78 Quarter (~span/8) (r=124.9) 1,600 1,594 1,644 344 Tiny (~span/1000) (r=1) 161,731 159,685 237,950 147,807
Get Elements In Bounds Get Elements In Bounds KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D Full (size=999.0x999.0) 315 362 328 20 Half (size=499.5x499.5) 1,746 1,723 1,772 108 Quarter (size=249.8x249.8) 6,787 6,916 6,997 546 Unit (size=1) 198,766 194,827 261,709 152,855
Approximate Nearest Neighbors Approximate Nearest Neighbors KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D 500 neighbors 16,775 35,374 26,298 3,663 100 neighbors 161,271 131,713 147,749 18,238 10 neighbors 506,799 494,356 261,774 29,127 1 neighbor 618,345 606,530 272,364 29,740
100,000 entries Construction Construction KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D 100,000 entries 44 (0.023s) 67 (0.015s) 15 (0.064s) 37 (0.026s)
Elements In Range Elements In Range KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D Full (~span/2) (r=199.5) 1,020 1,004 1,021 215 Half (~span/4) (r=99.75) 2,281 2,306 2,341 538 Quarter (~span/8) (r=49.88) 7,804 8,704 9,376 2,105 Tiny (~span/1000) (r=1) 195,261 196,197 279,042 194,307
Get Elements In Bounds Get Elements In Bounds KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D Full (size=399.0x249.0) 4,482 4,379 4,487 341 Half (size=199.5x124.5) 11,228 12,982 14,742 1,412 Quarter (size=99.75x62.25) 31,186 37,446 43,419 5,631 Unit (size=1) 228,484 225,721 315,803 205,613
Approximate Nearest Neighbors Approximate Nearest Neighbors KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D 500 neighbors 23,576 22,768 24,282 5,045 100 neighbors 107,485 190,998 99,608 17,425 10 neighbors 481,852 501,441 292,286 40,726 1 neighbor 596,868 616,172 301,254 43,377
10,000 entries Construction Construction KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D 10,000 entries 491 (0.002s) 669 (0.001s) 202 (0.005s) 413 (0.002s)
Elements In Range Elements In Range KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D Full (~span/2) (r=49.50) 10,059 10,063 10,024 2,149 Half (~span/4) (r=24.75) 38,194 37,816 39,638 8,431 Quarter (~span/8) (r=12.38) 70,930 83,939 99,255 33,540 Tiny (~span/1000) (r=1) 247,372 246,625 341,658 226,037
Get Elements In Bounds Get Elements In Bounds KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D Full (size=99.00x99.00) 44,817 44,113 44,394 3,536 Half (size=49.50x49.50) 164,390 168,864 172,050 13,410 Quarter (size=24.75x24.75) 98,908 135,348 171,080 50,695 Unit (size=1) 292,361 283,248 379,910 236,640
Approximate Nearest Neighbors Approximate Nearest Neighbors KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D 500 neighbors 30,990 30,435 29,942 5,229 100 neighbors 135,108 123,954 159,352 23,612 10 neighbors 495,078 493,259 327,237 54,246 1 neighbor 631,140 530,323 390,299 61,864
1,000 entries Construction Construction KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D 1,000 entries 4,416 (0.000s) 6,591 (0.000s) 1,976 (0.001s) 3,907 (0.000s)
Elements In Range Elements In Range KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D Full (~span/2) (r=24.50) 95,715 97,169 97,918 21,417 Half (~span/4) (r=12.25) 94,861 123,468 119,436 40,197 Quarter (~span/8) (r=6.13) 147,619 169,956 181,777 84,623 Tiny (~span/1000) (r=1) 346,917 348,862 458,277 320,193
Get Elements In Bounds Get Elements In Bounds KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D Full (size=49.00x19.00) 432,109 441,180 465,708 35,018 Half (size=24.50x9.5) 209,301 357,349 363,098 105,115 Quarter (size=12.25x4.75) 334,684 364,976 466,838 228,618 Unit (size=1) 404,675 390,143 502,011 337,746
Approximate Nearest Neighbors Approximate Nearest Neighbors KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D 500 neighbors 38,041 41,051 39,006 5,841 100 neighbors 156,877 152,010 160,805 24,720 10 neighbors 568,521 609,294 405,817 92,332 1 neighbor 531,965 641,229 334,066 106,525
100 entries Construction Construction KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D 100 entries 38,314 (0.000s) 37,593 (0.000s) 18,315 (0.000s) 18,382 (0.000s)
Elements In Range Elements In Range KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D Full (~span/2) (r=4.5) 707,466 707,344 698,430 190,481 Half (~span/4) (r=2.25) 579,526 574,963 734,467 379,167 Quarter (~span/8) (r=1.13) 580,850 585,912 742,405 427,445 Tiny (~span/1000) (r=1) 576,125 583,627 744,381 429,480
Get Elements In Bounds Get Elements In Bounds KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D Full (size=9x9) 1,564,474 1,567,597 1,584,871 282,253 Half (size=4.5x4.5) 641,201 644,062 792,659 419,895 Quarter (size=2.25x2.25) 650,761 653,857 788,861 438,508 Unit (size=1) 647,476 664,227 787,188 436,589
Approximate Nearest Neighbors Approximate Nearest Neighbors KDTree2D (Balanced) KDTree2D (Unbalanced) QuadTree2D RTree2D 100 neighbors (max) 191,767 191,405 180,671 154,573 10 neighbors 640,162 540,897 472,754 265,960 1 neighbor 658,223 565,971 517,711 350,069
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