Performance Spatial Tree 2d Performance

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	3 (0.312s)	6 (0.151s)	4 (0.221s)	3 (0.314s)

Elements In Range

Elements In Range	KDTree2D (Balanced)	KDTree2D (Unbalanced)	QuadTree2D	RTree2D
Full (~span/2) (r=499.5)	59	59	58	7
Half (~span/4) (r=249.8)	238	238	217	28
Quarter (~span/8) (r=124.9)	946	946	813	119
Tiny (~span/1000) (r=1)	99,724	101,966	137,096	99,994

Get Elements In Bounds

Get Elements In Bounds	KDTree2D (Balanced)	KDTree2D (Unbalanced)	QuadTree2D	RTree2D
Full (size=999.0x999.0)	407	411	366	19
Half (size=499.5x499.5)	1,795	1,802	1,221	88
Quarter (size=249.8x249.8)	7,115	6,980	3,798	380
Unit (size=1)	141,664	144,487	183,791	104,753

Approximate Nearest Neighbors

Approximate Nearest Neighbors	KDTree2D (Balanced)	KDTree2D (Unbalanced)	QuadTree2D	RTree2D
500 neighbors	8,206	16,253	12,254	59,120
100 neighbors	67,908	66,022	66,565	123,474
10 neighbors	202,943	190,315	149,013	170,797
1 neighbor	267,876	241,162	175,228	177,513

100,000 entries

Construction

Construction	KDTree2D (Balanced)	KDTree2D (Unbalanced)	QuadTree2D	RTree2D
100,000 entries	50 (0.020s)	83 (0.012s)	50 (0.020s)	9 (0.109s)

Elements In Range

Elements In Range	KDTree2D (Balanced)	KDTree2D (Unbalanced)	QuadTree2D	RTree2D
Full (~span/2) (r=199.5)	600	601	599	74
Half (~span/4) (r=99.75)	1,351	1,356	1,246	185
Quarter (~span/8) (r=49.88)	4,642	5,154	4,293	722
Tiny (~span/1000) (r=1)	122,543	122,801	168,775	132,560

Get Elements In Bounds

Get Elements In Bounds	KDTree2D (Balanced)	KDTree2D (Unbalanced)	QuadTree2D	RTree2D
Full (size=399.0x249.0)	4,453	4,549	4,563	238
Half (size=199.5x124.5)	9,453	11,770	7,930	964
Quarter (size=99.75x62.25)	26,044	31,978	19,472	3,795
Unit (size=1)	172,836	173,333	224,605	140,946

Approximate Nearest Neighbors

Approximate Nearest Neighbors	KDTree2D (Balanced)	KDTree2D (Unbalanced)	QuadTree2D	RTree2D
500 neighbors	9,740	9,685	11,231	59,001
100 neighbors	44,921	77,959	48,783	147,429
10 neighbors	225,534	200,018	163,465	192,974
1 neighbor	225,465	276,002	161,053	201,342

10,000 entries

Construction

Construction	KDTree2D (Balanced)	KDTree2D (Unbalanced)	QuadTree2D	RTree2D
10,000 entries	233 (0.004s)	835 (0.001s)	541 (0.002s)	508 (0.002s)

Elements In Range

Elements In Range	KDTree2D (Balanced)	KDTree2D (Unbalanced)	QuadTree2D	RTree2D
Full (~span/2) (r=49.50)	5,875	5,924	5,920	734
Half (~span/4) (r=24.75)	22,210	22,289	13,798	2,918
Quarter (~span/8) (r=12.38)	43,481	50,510	37,612	12,063
Tiny (~span/1000) (r=1)	158,679	152,879	217,222	151,558

Get Elements In Bounds

Get Elements In Bounds	KDTree2D (Balanced)	KDTree2D (Unbalanced)	QuadTree2D	RTree2D
Full (size=99.00x99.00)	43,343	44,704	45,372	2,406
Half (size=49.50x49.50)	158,570	140,495	36,370	9,239
Quarter (size=24.75x24.75)	73,307	98,718	73,266	34,653
Unit (size=1)	222,078	213,762	286,948	162,138

Approximate Nearest Neighbors

Approximate Nearest Neighbors	KDTree2D (Balanced)	KDTree2D (Unbalanced)	QuadTree2D	RTree2D
500 neighbors	12,580	12,647	13,889	55,797
100 neighbors	46,902	50,902	78,242	148,788
10 neighbors	184,894	207,390	178,180	211,248
1 neighbor	282,350	285,939	207,301	224,225

1,000 entries

Construction

Construction	KDTree2D (Balanced)	KDTree2D (Unbalanced)	QuadTree2D	RTree2D
1,000 entries	5,291 (0.000s)	7,668 (0.000s)	4,816 (0.000s)	4,595 (0.000s)

Elements In Range

Elements In Range	KDTree2D (Balanced)	KDTree2D (Unbalanced)	QuadTree2D	RTree2D
Full (~span/2) (r=24.50)	57,007	56,693	56,124	7,330
Half (~span/4) (r=12.25)	59,134	74,131	56,058	14,528
Quarter (~span/8) (r=6.13)	92,781	104,908	92,734	36,895
Tiny (~span/1000) (r=1)	222,860	220,260	303,674	216,071

Get Elements In Bounds

Get Elements In Bounds	KDTree2D (Balanced)	KDTree2D (Unbalanced)	QuadTree2D	RTree2D
Full (size=49.00x19.00)	430,126	429,961	459,090	23,704
Half (size=24.50x9.5)	157,744	263,111	120,855	71,562
Quarter (size=12.25x4.75)	247,926	262,495	181,191	158,034
Unit (size=1)	305,499	302,558	400,384	237,879

Approximate Nearest Neighbors

Approximate Nearest Neighbors	KDTree2D (Balanced)	KDTree2D (Unbalanced)	QuadTree2D	RTree2D
500 neighbors	42,223	42,920	36,490	59,756
100 neighbors	69,426	67,325	75,633	164,039
10 neighbors	222,227	243,970	195,434	236,157
1 neighbor	278,527	245,828	195,817	250,082

100 entries

Construction

Construction	KDTree2D (Balanced)	KDTree2D (Unbalanced)	QuadTree2D	RTree2D
100 entries	41,322 (0.000s)	32,362 (0.000s)	27,322 (0.000s)	20,703 (0.000s)

Elements In Range

Elements In Range	KDTree2D (Balanced)	KDTree2D (Unbalanced)	QuadTree2D	RTree2D
Full (~span/2) (r=4.5)	438,910	439,298	438,875	69,290
Half (~span/4) (r=2.25)	378,963	382,697	237,452	205,575
Quarter (~span/8) (r=1.13)	379,230	382,620	494,646	277,996
Tiny (~span/1000) (r=1)	379,206	382,740	496,709	278,197

Get Elements In Bounds

Get Elements In Bounds	KDTree2D (Balanced)	KDTree2D (Unbalanced)	QuadTree2D	RTree2D
Full (size=9x9)	1,272,354	1,354,621	1,394,343	195,271
Half (size=4.5x4.5)	476,706	472,738	323,833	299,443
Quarter (size=2.25x2.25)	493,145	500,843	622,143	314,123
Unit (size=1)	493,109	499,483	620,950	314,175

Approximate Nearest Neighbors

Approximate Nearest Neighbors	KDTree2D (Balanced)	KDTree2D (Unbalanced)	QuadTree2D	RTree2D
100 neighbors (max)	123,698	123,197	135,888	180,194
10 neighbors	250,243	208,673	255,381	271,081
1 neighbor	244,327	312,085	267,884	290,000

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