Quadtrees
Motivation
Suppose we have a set of 2D points and we want to be able to query how many points lie in a particular rectangle.
A brute force approach would be
We want a way to more efficiently count points contained within a rectangular region.
Explanation
Each node in a Quadtree has a bounding rectangle. If the node is not a leaf then it has 4 children, splitting the rectangle into four quadrants.
Points are also attached to nodes. We define a constant specifying the maximum number of points associated with each node.
Insertion
Query
Use recursion to count the number of points in a
given range.Consider only nodes that overlap with the query range.
Time Complexity
If the points are distributed uniformly in the root’s
range, then insertions and queries are logarithmic.
However, if they are not uniformly distributed
then it can degrade to linear time.
Quadrant Contains a Point
Region Intersects a Quad
Types of Quadtrees
Region quadtree – Divides region into sub-quadrants based on the areas with more detailed information.
Image processing – only subdivide if pixels differ in color.
Variable resolution data field – each parent has the average value of its children.
Point quadtree – Divide the region at the point that is inserted (like a binary tree but with 4 pointers).
-d trees are preferred. Point-region (PR) quadtree – What we implemented.
Edge quadtree – Stores lines/curves with approximation.
Polygonal map (PM) quadtree – stores polygons.
Compressed quadtrees – only storing subtrees whose leaves have interesting data and removing empty intermediate nodes.
Conclusion
Quadtrees are used to efficiently query the number of points contained within various rectangular ranges.
Quadtrees are most efficient when the points are uniformly distributed.
Lab 24: Quadtrees
Let’s take a look at the lab based on today’s lecture.