Quadtree
Source: https://jimkang.com/quadtreevis/
Quadtrees are a way of partitioning space so that it’s easy to traverse and search. Some possible uses of that include:
Hit detection
Let’s say you have a bunch of points in a space, like in the maps above. Someone asks you if some arbitrary point p is within your bunch of points. How can you find out if you have that point? A:
- You could set up a quadtree. When you have it search for p, it will find out which quadrant it is inside. Then, it will find out what quadrant within that quadrant it is inside. And so forth.
- After it finds its way to that rectangle node, it merely needs to see if any of the four children equal p.
Finding the nearest neighbor
Rather than ask you whether any of them match a given point, someone asks you what the nearest point you have to an arbitrary point among your points. With a quadtree, while searching, you can say, “OK, there’s no way anything in this quadrant has any chance of being the nearest neighbor” and eliminate a lot of point comparisons that way.
Other uses:
- Image processing
- Mesh generation
- Spatial indexing, point location queries, and range queries
- Efficient collision detection in two dimensions
- View frustum culling of terrain data
- Storing sparse data, such as a formatting information for a spreadsheet or for some matrix calculations[citation needed]
- Solution of multidimensional fields (computational fluid dynamics, electromagnetism)
- Conway’s Game of Life simulation program.
- State estimation
- Quadtrees are also used in the area of fractal image analysis
- Maximum disjoint sets
Created from: Algorithms to know before system design interviews 202211231052
uid: 202211231054 tags: #algorithms #software-engineering