5,337
edits
Data Structures: Difference between revisions
→Spatial Data Structures
| Line 28: | Line 28: | ||
==Spatial Data Structures== | ==Spatial Data Structures== | ||
===Point Quadtree=== | |||
Extension of BST. | |||
===PM Quadtree=== | ===PM Quadtree=== | ||
Polygonal Map Quadtree<br> | |||
Simple to implement. See my implementation [https://github.com/dli7319/unity-data-structures here]. | Simple to implement. See my implementation [https://github.com/dli7319/unity-data-structures here]. | ||
Requires a known range (region) of values.<br> | |||
O(log k) where k is the region divided by the distance between the two closest points (i.e. your grid is <math>k \times k</math>). | |||
===PR Quadtree=== | ===PR Quadtree=== | ||
Point Region Quadtree<br> | |||
===MX Quadtree=== | ===MX Quadtree=== | ||
===K-d Tree=== | ===K-d Tree=== | ||
===Restricted Quadtree=== | |||
[https://pdfs.semanticscholar.org/ae3d/922cb5ac1eef9bab178e0a976b5eced069dd.pdf Reference]<br> | |||
Extension of AVL quadtree where the depth differs by at most one between your 4 children. | |||