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.359s)	6 (0.152s)	4 (0.219s)	2 (0.389s)

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	220	29
Quarter (~span/8) (r=124.9)	947	947	816	118
Tiny (~span/1000) (r=1)	99,670	101,892	136,684	96,713

Get Elements In Bounds

Get Elements In Bounds	KDTree2D (Balanced)	KDTree2D (Unbalanced)	QuadTree2D	RTree2D
Full (size=999.0x999.0)	433	405	360	18
Half (size=499.5x499.5)	1,826	1,829	1,217	88
Quarter (size=249.8x249.8)	7,101	7,061	3,773	380
Unit (size=1)	141,553	142,396	184,035	104,669

Approximate Nearest Neighbors

Approximate Nearest Neighbors	KDTree2D (Balanced)	KDTree2D (Unbalanced)	QuadTree2D	RTree2D
500 neighbors	8,278	16,262	12,321	59,125
100 neighbors	67,944	66,256	66,443	123,278
10 neighbors	205,384	175,412	147,026	169,773
1 neighbor	265,309	264,824	173,504	175,770

100,000 entries

Construction

Construction	KDTree2D (Balanced)	KDTree2D (Unbalanced)	QuadTree2D	RTree2D
100,000 entries	50 (0.020s)	84 (0.012s)	10 (0.092s)	51 (0.019s)

Elements In Range

Elements In Range	KDTree2D (Balanced)	KDTree2D (Unbalanced)	QuadTree2D	RTree2D
Full (~span/2) (r=199.5)	600	601	598	75
Half (~span/4) (r=99.75)	1,352	1,357	1,246	185
Quarter (~span/8) (r=49.88)	4,644	5,161	4,295	724
Tiny (~span/1000) (r=1)	122,350	122,654	168,403	132,231

Get Elements In Bounds

Get Elements In Bounds	KDTree2D (Balanced)	KDTree2D (Unbalanced)	QuadTree2D	RTree2D
Full (size=399.0x249.0)	4,561	4,608	4,403	233
Half (size=199.5x124.5)	9,475	11,753	7,853	964
Quarter (size=99.75x62.25)	24,906	31,545	20,178	3,755
Unit (size=1)	172,319	173,024	225,047	140,423

Approximate Nearest Neighbors

Approximate Nearest Neighbors	KDTree2D (Balanced)	KDTree2D (Unbalanced)	QuadTree2D	RTree2D
500 neighbors	9,721	9,662	11,206	59,108
100 neighbors	45,047	77,749	44,819	145,560
10 neighbors	225,024	173,728	162,370	191,394
1 neighbor	226,497	210,737	189,588	198,053

10,000 entries

Construction

Construction	KDTree2D (Balanced)	KDTree2D (Unbalanced)	QuadTree2D	RTree2D
10,000 entries	543 (0.002s)	813 (0.001s)	544 (0.002s)	510 (0.002s)

Elements In Range

Elements In Range	KDTree2D (Balanced)	KDTree2D (Unbalanced)	QuadTree2D	RTree2D
Full (~span/2) (r=49.50)	5,895	5,928	5,879	734
Half (~span/4) (r=24.75)	22,259	22,293	13,797	2,892
Quarter (~span/8) (r=12.38)	43,468	50,041	37,449	12,064
Tiny (~span/1000) (r=1)	156,856	154,166	216,619	151,008

Get Elements In Bounds

Get Elements In Bounds	KDTree2D (Balanced)	KDTree2D (Unbalanced)	QuadTree2D	RTree2D
Full (size=99.00x99.00)	44,870	44,431	46,015	2,341
Half (size=49.50x49.50)	158,404	158,408	36,718	8,951
Quarter (size=24.75x24.75)	73,174	100,027	73,199	34,155
Unit (size=1)	221,985	215,869	286,168	161,133

Approximate Nearest Neighbors

Approximate Nearest Neighbors	KDTree2D (Balanced)	KDTree2D (Unbalanced)	QuadTree2D	RTree2D
500 neighbors	12,710	12,540	13,860	55,727
100 neighbors	55,295	50,910	76,613	148,713
10 neighbors	224,136	205,429	174,339	210,086
1 neighbor	281,463	249,197	204,354	220,972

1,000 entries

Construction

Construction	KDTree2D (Balanced)	KDTree2D (Unbalanced)	QuadTree2D	RTree2D
1,000 entries	4,852 (0.000s)	7,961 (0.000s)	4,686 (0.000s)	4,557 (0.000s)

Elements In Range

Elements In Range	KDTree2D (Balanced)	KDTree2D (Unbalanced)	QuadTree2D	RTree2D
Full (~span/2) (r=24.50)	55,893	57,102	56,097	7,342
Half (~span/4) (r=12.25)	59,063	74,694	55,921	14,534
Quarter (~span/8) (r=6.13)	92,939	104,886	91,839	36,930
Tiny (~span/1000) (r=1)	222,827	220,241	299,788	212,909

Get Elements In Bounds

Get Elements In Bounds	KDTree2D (Balanced)	KDTree2D (Unbalanced)	QuadTree2D	RTree2D
Full (size=49.00x19.00)	430,814	430,852	452,791	23,445
Half (size=24.50x9.5)	156,729	263,248	120,573	70,856
Quarter (size=12.25x4.75)	246,056	260,412	181,261	158,165
Unit (size=1)	305,340	300,846	395,180	237,579

Approximate Nearest Neighbors

Approximate Nearest Neighbors	KDTree2D (Balanced)	KDTree2D (Unbalanced)	QuadTree2D	RTree2D
500 neighbors	42,240	42,911	35,795	59,620
100 neighbors	69,561	67,320	75,420	163,855
10 neighbors	231,731	244,310	193,392	234,017
1 neighbor	307,506	219,267	193,132	247,700

100 entries

Construction

Construction	KDTree2D (Balanced)	KDTree2D (Unbalanced)	QuadTree2D	RTree2D
100 entries	39,215 (0.000s)	35,460 (0.000s)	21,008 (0.000s)	20,576 (0.000s)

Elements In Range

Elements In Range	KDTree2D (Balanced)	KDTree2D (Unbalanced)	QuadTree2D	RTree2D
Full (~span/2) (r=4.5)	438,163	438,426	436,257	69,261
Half (~span/4) (r=2.25)	379,510	382,512	236,397	202,932
Quarter (~span/8) (r=1.13)	375,449	382,951	493,448	276,634
Tiny (~span/1000) (r=1)	379,149	383,140	492,984	274,349

Get Elements In Bounds

Get Elements In Bounds	KDTree2D (Balanced)	KDTree2D (Unbalanced)	QuadTree2D	RTree2D
Full (size=9x9)	1,353,163	1,359,911	1,307,730	195,074
Half (size=4.5x4.5)	469,727	472,652	323,903	299,135
Quarter (size=2.25x2.25)	492,315	502,632	619,837	313,482
Unit (size=1)	492,918	496,724	617,756	311,829

Approximate Nearest Neighbors

Approximate Nearest Neighbors	KDTree2D (Balanced)	KDTree2D (Unbalanced)	QuadTree2D	RTree2D
100 neighbors (max)	123,336	122,168	133,695	179,415
10 neighbors	250,408	233,758	253,757	270,169
1 neighbor	252,054	303,982	244,361	285,711

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