2
\$\begingroup\$

A quadtree has limit on number of item in each nodes. Suppose a node has already has same number of item as the limit. If I add another item on same node the node should split and new item should be added there. What I dont understand, Is previously existed node should be shifted to the new node? or they will remain where they were (parent of newly craeted node)?

\$\endgroup\$
  • 2
    \$\begingroup\$ A node should only have either child-nodes (exactly four, as it is a quadtree) or items (as you call them), never both \$\endgroup\$ – tkausl Aug 12 '15 at 17:13
  • \$\begingroup\$ How should it handle cases like if item have been put on exact boundary of two node? does not belongs two any node, belongs to exact coordinate of intersection of two node \$\endgroup\$ – varuog Aug 12 '15 at 17:39
3
\$\begingroup\$

It's a quad tree so when you split it into 4 parts any entities belonging to the parent get divided between the children based on position.

\$\endgroup\$
  • \$\begingroup\$ How should it handle cases like if item have been put on exact boundary of two node? does not belongs two any node, belongs to exact coordinate of intersection of two node. \$\endgroup\$ – varuog Aug 12 '15 at 17:39
  • 2
    \$\begingroup\$ It belongs to both nodes in that case and the normal way to handle it is to put a pointer/reference to the entity in both \$\endgroup\$ – cfehunter Aug 12 '15 at 17:42
  • \$\begingroup\$ Or, usually you would design it such that you cannot be in both. At that point it's up to you on which way an item would go \$\endgroup\$ – CobaltHex Aug 13 '15 at 1:35
  • \$\begingroup\$ It depends what you're using the tree for. For culling and physics you kind of need to be able to add to multiple nodes because an object isn't a zero size singularity. \$\endgroup\$ – cfehunter Aug 13 '15 at 6:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.