Efficient Q-Tree Algorithm: Understanding Parent-Child Relationships

  • Thread starter Thread starter sayuri2009
  • Start date Start date
  • Tags Tags
    Algorithm Search
Join the discussion
Ask a follow-up here, or get your own question answered by working scientists, mathematicians and engineers — people, not an autocomplete.
Real named experts · corrections over time · the nuance an AI answer skips
Sign up Log in
1 reply · 1K views
sayuri2009
Messages
13
Reaction score
2
TL;DR
Cities
Hi,

I don't get what the conditions below exactly means.

1610198442449.png

Its which u they are talking about? Is the u the parent or children? Does it mean u = B? and the children are A,C,D?
if u is in the quadtree rooted by v:NW then u:x < v:x and u:y ≥ v:y;

Thanks,
 
Physics news on Phys.org
sayuri2009 said:
Its which u they are talking about?
## u ## stands for any node, not any particular one.

sayuri2009 said:
Is the u the parent or children?
Every node can be both a parent and a child.

sayuri2009 said:
Does it mean u = B? and the children are A,C,D?
There are many ways to build a quadtree, but if you start with B at the root then ## B.parent = B.NE = B.SE = \mathrm{null} ##, ## B.NW = A ## and ## B.SW ## can be either of ## C ## or ## D ## depending on how you build the tree.

Edit: quadtrees are less useful for representing scattered points as they are likely to be sparse and unbalanced, they are more useful for representing a square lattice.