I'm using c++ and have some problems with the QuadTree design.

I have some components which are not related to the QuadTree directly. These components are eg. RenderableMesh, PointLight, etc. Some of them should be handled by a QuadTree and some of them should not.

I have a "reflection" system, so I can determine the type of a given component, that's not a problem.

A simple restriction is if I want to use a component in a QuadTree, it has to be inherited from the IBoundComponent which can be used to get the bounding box of the object (using a pure virtual function which is implemented in the exact Component)

This seems okay for me but for fast remove/insert operations of "changed components" (eg. the point light's radius is changed) I should store the current node/cell of the QuadTree. And here comes the real problem. Or actually problems.


Because the IBoundComponent does not know about the QuadTree directly, it has to have a public function pair which can be used to set/get the current node. I could use "friend class QuadTree" but that would restrict the spatial implementation to the QuadTree class.


The Node class of the QuadTree is hidden (private). Of course I could store a void* in the IBoundComponent and cast it. Or a base class (eg. ITreeNode) could be used and the QuadTree's Node should inherit from it.

Maybe a cleaner design would be the following:

Don't store anything in the IBoundComponent (expect the bounds...). When a component is changed, I could store the pre-update bounds as well as the post-update bounds. This way I can find which node contains the component and which will contain it. However this is an extra search. So it's a performance loss for cleaner design.

Do you have any good idea? I've searched here but cannot find a good answer for this situation.


My approach is that there is a IQuadTreeItem class that has a member QuadTreeNode to the parent node and a virtual method ToBounding() that returns the correct bounding container. I think the member variable is very clean and it provides nice and fast access for relocating and removing among other operations.

  • \$\begingroup\$ I ended up with using friend class, because I have to store and read the QuadTreeNode through the QuadTree only. I don't want to have a public member pointer because everyone could read and/or write it. Is this an acceptable design? \$\endgroup\$ – csisy May 22 '16 at 22:41
  • \$\begingroup\$ Friend sounds always sketcy to me. \$\endgroup\$ – Tyyppi_77 May 23 '16 at 4:05
  • 1
    \$\begingroup\$ Better using a public function/member and let everyone modify it? This can be acceptable as well since everyone who has access to the source code can make it crash or malfunctioning. \$\endgroup\$ – csisy May 23 '16 at 7:22
  • \$\begingroup\$ Probably, but it's mostly just all opinnions at this point. \$\endgroup\$ – Tyyppi_77 May 23 '16 at 8:10
  • 1
    \$\begingroup\$ I guess the best would be using a dll and simply don't export it. I will follow this way so I accept your answer. Thanks! :) \$\endgroup\$ – csisy May 23 '16 at 8:43

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.