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	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