Performance Spatial Tree 2d Performance - Ambiguous-Interactive/unity-helpers GitHub Wiki
2D Spatial Tree Performance Benchmarks
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 performance
KdTree2D - Balanced and unbalanced variants available
RTree2D - 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.
Performance Benchmarks
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