-
Notifications
You must be signed in to change notification settings - Fork 7
Performance Spatial Tree 2d Performance
github-actions[bot] edited this page Jan 26, 2026
·
6 revisions
- 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.
- QuadTree2D - Easiest to use, good all-around performance
- KdTree2D - Balanced and unbalanced variants available
- RTree2D - Optimized for bounding box queries
- 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.
| Construction | KDTree2D (Balanced) | KDTree2D (Unbalanced) | QuadTree2D | RTree2D |
|---|---|---|---|---|
| 1,000,000 entries | 4 (0.247s) | 2 (0.346s) | 4 (0.223s) | 2 (0.379s) |
| Elements In Range | KDTree2D (Balanced) | KDTree2D (Unbalanced) | QuadTree2D | RTree2D |
|---|---|---|---|---|
| Full (~span/2) (r=499.5) | 58 | 56 | 56 | 7 |
| Half (~span/4) (r=249.8) | 234 | 215 | 214 | 28 |
| Quarter (~span/8) (r=124.9) | 909 | 795 | 785 | 117 |
| Tiny (~span/1000) (r=1) | 8,280 | 5,565 | 6,973 | 6,724 |
| Get Elements In Bounds | KDTree2D (Balanced) | KDTree2D (Unbalanced) | QuadTree2D | RTree2D |
|---|---|---|---|---|
| Full (size=999.0x999.0) | 334 | 355 | 314 | 16 |
| Half (size=499.5x499.5) | 1,356 | 1,367 | 1,005 | 66 |
| Quarter (size=249.8x249.8) | 3,148 | 3,183 | 2,281 | 322 |
| Unit (size=1) | 5,612 | 5,606 | 5,577 | 2,834 |
| Approximate Nearest Neighbors | KDTree2D (Balanced) | KDTree2D (Unbalanced) | QuadTree2D | RTree2D |
|---|---|---|---|---|
| 500 neighbors | 3,023 | 1,733 | 2,148 | 1,855 |
| 100 neighbors | 2,828 | 1,863 | 2,308 | 1,802 |
| 10 neighbors | 1,958 | 1,899 | 1,641 | 1,692 |
| 1 neighbor | 1,961 | 1,957 | 1,464 | 1,465 |
| Construction | KDTree2D (Balanced) | KDTree2D (Unbalanced) | QuadTree2D | RTree2D |
|---|---|---|---|---|
| 100,000 entries | 49 (0.020s) | 77 (0.013s) | 48 (0.021s) | 43 (0.023s) |
| Elements In Range | KDTree2D (Balanced) | KDTree2D (Unbalanced) | QuadTree2D | RTree2D |
|---|---|---|---|---|
| Full (~span/2) (r=199.5) | 539 | 527 | 536 | 71 |
| Half (~span/4) (r=99.75) | 1,065 | 1,073 | 1,012 | 171 |
| Quarter (~span/8) (r=49.88) | 2,494 | 2,710 | 2,448 | 577 |
| Tiny (~span/1000) (r=1) | 5,607 | 5,616 | 5,660 | 2,872 |
| Get Elements In Bounds | KDTree2D (Balanced) | KDTree2D (Unbalanced) | QuadTree2D | RTree2D |
|---|---|---|---|---|
| Full (size=399.0x249.0) | 2,462 | 2,524 | 2,549 | 209 |
| Half (size=199.5x124.5) | 3,563 | 3,901 | 3,304 | 674 |
| Quarter (size=99.75x62.25) | 4,726 | 4,934 | 4,519 | 1,550 |
| Unit (size=1) | 5,625 | 5,658 | 5,661 | 2,850 |
| Approximate Nearest Neighbors | KDTree2D (Balanced) | KDTree2D (Unbalanced) | QuadTree2D | RTree2D |
|---|---|---|---|---|
| 500 neighbors | 1,562 | 1,612 | 1,236 | 1,407 |
| 100 neighbors | 1,861 | 1,870 | 1,397 | 1,439 |
| 10 neighbors | 1,942 | 1,904 | 1,456 | 1,464 |
| 1 neighbor | 1,911 | 1,912 | 1,461 | 1,462 |
| Construction | KDTree2D (Balanced) | KDTree2D (Unbalanced) | QuadTree2D | RTree2D |
|---|---|---|---|---|
| 10,000 entries | 541 (0.002s) | 818 (0.001s) | 541 (0.002s) | 322 (0.003s) |
| Elements In Range | KDTree2D (Balanced) | KDTree2D (Unbalanced) | QuadTree2D | RTree2D |
|---|---|---|---|---|
| Full (~span/2) (r=49.50) | 2,950 | 2,951 | 2,873 | 579 |
| Half (~span/4) (r=24.75) | 4,631 | 4,548 | 4,092 | 1,428 |
| Quarter (~span/8) (r=12.38) | 5,146 | 5,164 | 5,032 | 2,339 |
| Tiny (~span/1000) (r=1) | 5,581 | 5,646 | 5,680 | 2,865 |
| Get Elements In Bounds | KDTree2D (Balanced) | KDTree2D (Unbalanced) | QuadTree2D | RTree2D |
|---|---|---|---|---|
| Full (size=99.00x99.00) | 5,087 | 5,167 | 5,181 | 1,288 |
| Half (size=49.50x49.50) | 5,622 | 5,652 | 5,010 | 2,185 |
| Quarter (size=24.75x24.75) | 5,435 | 5,561 | 5,414 | 2,687 |
| Unit (size=1) | 5,699 | 5,709 | 5,749 | 2,817 |
| Approximate Nearest Neighbors | KDTree2D (Balanced) | KDTree2D (Unbalanced) | QuadTree2D | RTree2D |
|---|---|---|---|---|
| 500 neighbors | 1,681 | 1,696 | 1,304 | 1,369 |
| 100 neighbors | 1,893 | 1,888 | 1,387 | 1,445 |
| 10 neighbors | 1,961 | 1,955 | 1,413 | 1,470 |
| 1 neighbor | 1,971 | 1,917 | 1,422 | 1,471 |
| Construction | KDTree2D (Balanced) | KDTree2D (Unbalanced) | QuadTree2D | RTree2D |
|---|---|---|---|---|
| 1,000 entries | 5,376 (0.000s) | 7,429 (0.000s) | 4,940 (0.000s) | 889 (0.001s) |
| Elements In Range | KDTree2D (Balanced) | KDTree2D (Unbalanced) | QuadTree2D | RTree2D |
|---|---|---|---|---|
| Full (~span/2) (r=24.50) | 5,370 | 5,367 | 5,348 | 2,032 |
| Half (~span/4) (r=12.25) | 5,333 | 5,421 | 5,199 | 2,425 |
| Quarter (~span/8) (r=6.13) | 5,541 | 5,567 | 5,433 | 2,713 |
| Tiny (~span/1000) (r=1) | 5,702 | 5,619 | 5,740 | 2,874 |
| Get Elements In Bounds | KDTree2D (Balanced) | KDTree2D (Unbalanced) | QuadTree2D | RTree2D |
|---|---|---|---|---|
| Full (size=49.00x19.00) | 5,747 | 5,690 | 5,800 | 2,590 |
| Half (size=24.50x9.5) | 5,567 | 5,775 | 5,629 | 2,806 |
| Quarter (size=12.25x4.75) | 5,629 | 5,739 | 5,698 | 2,842 |
| Unit (size=1) | 5,729 | 5,753 | 5,751 | 2,868 |
| Approximate Nearest Neighbors | KDTree2D (Balanced) | KDTree2D (Unbalanced) | QuadTree2D | RTree2D |
|---|---|---|---|---|
| 500 neighbors | 1,862 | 1,871 | 1,386 | 1,412 |
| 100 neighbors | 1,900 | 1,893 | 1,418 | 1,401 |
| 10 neighbors | 1,959 | 1,965 | 1,468 | 1,428 |
| 1 neighbor | 1,970 | 1,949 | 1,434 | 1,434 |
| Construction | KDTree2D (Balanced) | KDTree2D (Unbalanced) | QuadTree2D | RTree2D |
|---|---|---|---|---|
| 100 entries | 43,859 (0.000s) | 40,650 (0.000s) | 26,954 (0.000s) | 1,682 (0.001s) |
| Elements In Range | KDTree2D (Balanced) | KDTree2D (Unbalanced) | QuadTree2D | RTree2D |
|---|---|---|---|---|
| Full (~span/2) (r=4.5) | 5,862 | 5,829 | 5,811 | 2,816 |
| Half (~span/4) (r=2.25) | 5,776 | 5,734 | 5,688 | 2,886 |
| Quarter (~span/8) (r=1.13) | 5,757 | 5,723 | 5,766 | 2,904 |
| Tiny (~span/1000) (r=1) | 5,727 | 5,583 | 5,765 | 2,904 |
| Get Elements In Bounds | KDTree2D (Balanced) | KDTree2D (Unbalanced) | QuadTree2D | RTree2D |
|---|---|---|---|---|
| Full (size=9x9) | 5,846 | 5,821 | 5,910 | 2,817 |
| Half (size=4.5x4.5) | 5,742 | 5,791 | 5,709 | 2,848 |
| Quarter (size=2.25x2.25) | 5,753 | 5,686 | 5,762 | 2,907 |
| Unit (size=1) | 5,684 | 5,702 | 5,835 | 2,898 |
| Approximate Nearest Neighbors | KDTree2D (Balanced) | KDTree2D (Unbalanced) | QuadTree2D | RTree2D |
|---|---|---|---|---|
| 100 neighbors (max) | 1,869 | 1,918 | 1,447 | 1,447 |
| 10 neighbors | 1,950 | 1,960 | 1,476 | 1,480 |
| 1 neighbor | 1,968 | 1,955 | 1,475 | 1,478 |
All numbers represent operations per second (higher is better), except for construction times which show operations per second and absolute time.
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
- 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
📦 Unity Helpers | 📖 Documentation | 🐛 Issues | 📜 MIT License
- Inspector Button
- Inspector Conditional Display
- Inspector Grouping Attributes
- Inspector Inline Editor
- Inspector Overview
- Inspector Selection Attributes
- Inspector Settings
- Inspector Validation Attributes
- Utility Components
- Visual Components
- Data Structures
- Helper Utilities
- Math And Extensions
- Pooling Guide
- Random Generators
- Reflection Helpers
- Singletons