Efficient Q-Tree Algorithm: Understanding Parent-Child Relationships

1 reply · 1K views · last reply
sayuri2009
Messages
13
Reaction score
2
TL;DR
Cities
Hi,

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

Diagram of a quadtree partition of a plane with axes labelled NW, NE, SE and SW, showing four cities as dots with letter labels A, B, C and D placed in the quadrants.

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,
 

Discussion

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.