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