# Which method is preferred for storing large geometric objects in a quadtree?

When placing geometric objects in a quadtree (or octree), you can place objects that are larger than a single node in a few ways:

1. Placing the object's reference in every leaf for which it is contained
2. Placing the object's reference in the deepest node for which it is fully contained
3. 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?

• Certainly it should be a reference. I intend to ask if, for the purposes of querying the quadtree, there should be references in the the leaves, non-leaves, or both. Mar 6, 2012 at 19:45
• P.S. Edited to hopefully make intentions of the question clearer. Mar 6, 2012 at 19:46
• What is the query you are trying to support?
– Joe
Mar 6, 2012 at 21:45
• @Joe I am particularly interested in collision detection, spacial indexing, and region/frustum culling. Mar 7, 2012 at 5:45
• @nsantorello The rule may be different depending on which of those queries you want to support, but this seems very relevant for collision detection: stackoverflow.com/questions/4434335/…
– Joe
Mar 7, 2012 at 6:11

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.

• Thanks Rafe, I think you are right that it depends on the application. Mar 6, 2012 at 19:49

One of the advantages of a Quadtree is that you don't have to split a node into its child nodes if all of the child nodes would contain the same information. This can save you a lot of memory and can make processing faster.

Following this principle, I think it makes more sense to store it only in the root node (method #2). It could save you a lot of memory and I think would also make processing easier. For example, if you tried to find intersections of the circle with a line that goes through three of the leaf nodes, you would either need to compute the intersection separately for each leaf node, or remember that you already intersected with this circle.

On the other hand, if you have objects in leaf nodes, it could help you eliminate false positives (objects that you have to check for intersection, because they are in the correct node, but that don't actually intersect).

So, I think both approaches have their uses and I'm not sure how to choose which one to use.

I probably wouldn't use approach #3, because I don't see any positives about it.