patternMinor
Which method is preferred for storing large geometric objects in a quadtree?
Viewed 0 times
methodgeometricobjectspreferredlargeforwhichquadtreestoring
Problem
When placing geometric objects in a quadtree (or octree), you can place objects that are larger than a single node in a few ways:
For example:
In this image, you could either place the circle in all four of the leaf nodes (method #1) or in just the root node (method #2) or both (method #3).
For the purposes of querying the quadtree, which method is more commonplace and why?
- Placing the object's reference in every leaf for which it is contained
- Placing the object's reference in the deepest node for which it is fully contained
- Both #1 and #2
For example:
In this image, you could either place the circle in all four of the leaf nodes (method #1) or in just the root node (method #2) or both (method #3).
For the purposes of querying the quadtree, which method is more commonplace and why?
Solution
Assuming you are storing a reference, not the object itself, it may make sense to do this differently depending on your application.
For instance, if you were computing collisions with this (solid) circle and the collision was occurring in the lower left hand corner, it'd be easier if you had access to all geometry in that leaf directly from that leaf (method #3) (without having to traverse the tree upward and determine inherited geometry). But, say you were just using quadtrees for drawing geometry, you'd want to use method #1, because it only makes sense to draw something in the node for which it is fully contained (it would be more difficult to figure out which portion to draw for each leaf node and where).
As for what is more commonplace, my only experience with quadtrees is with writing an n-body simulation where the geometric objects were really just points that had no area, so I can't definitively answer that.
For instance, if you were computing collisions with this (solid) circle and the collision was occurring in the lower left hand corner, it'd be easier if you had access to all geometry in that leaf directly from that leaf (method #3) (without having to traverse the tree upward and determine inherited geometry). But, say you were just using quadtrees for drawing geometry, you'd want to use method #1, because it only makes sense to draw something in the node for which it is fully contained (it would be more difficult to figure out which portion to draw for each leaf node and where).
As for what is more commonplace, my only experience with quadtrees is with writing an n-body simulation where the geometric objects were really just points that had no area, so I can't definitively answer that.
Context
StackExchange Computer Science Q#7, answer score: 8
Revisions (0)
No revisions yet.