通用四叉树 [英] Generic Quadtree

问题描述

我正在写一个四叉树类作为图形库的一部分，我面临着一个设计问题。
主要目标是允许库的用户使用自己的节点类型轻松扩展四叉树。每个节点都有一个指向它的四个子节点的第一个的指针。我使用protoype模式来克隆一个父节点（它的真实类型对于库是未知的）四次，当它被分裂。所以这里是Node类：

I am writing a quadtree class as a part of graphics library and I am facing a design issue. A main goal is to allow the user of the library to easily extend the quadtree with their own Node Types. Each node has a pointer to the first of its four childs. I use the protoype pattern to 'clone' a parent node (its real type is unknown to the library) four times when it is split. So here is the Node class:

class CNode {
  public:
    virtual CNode* clone();

  protected:
    CNode* pChilds;
}

库的用户现在可以定义自己的节点并添加一个遍历方法：

The user of the library may now define its own node and add a traverse method:

class MyNode : public CNode {
  public:
    virtual CNode* clone() {
      return new MyNode;
    }

    void myTraverse() {
      if(pChilds[0] != nullptr)
        static_cast<MyNode*>(pChilds[0])->traverse();
    }
}

可以看出，基类转换为派生类。或者，我可以做所有的四叉树相关的类模板，但我真的不想这样做。
我也不能使用boost。除此之外，任何和类似的RTTI或动态转换的解决方案都是慢的，因为四叉树是一个性能关键组件，必须尽可能快的运行！

As can be seen I have to do a cast from the base class to the derived class. Alternatively I could make all quadtree related classes templates but I really don't want to do that. I also cant use use boost. Besides that boost::any and similar solutions with RTTI or dynamic casting are to slow since the quadtree is a performance critical component and must to run as fast as possible!

是否有任何可能性来维持static_cast的速度，同时添加一些类型安全？ （一个四叉树只包含单一类型的节点）。

Is there any possebility to maintain the speed of the static_cast while adding some type safety? (a quadtree will only contain nodes of a single type).

推荐答案

我知道你说你不想使用模板，但这种事情是完全什么样的模板。通过使你的节点类成为一个虚拟类，你在每个构造和销毁上强制额外的开销，以及通过至少一个指针扩展节点结构的大小，这将减少高速缓存一致性。

I know you said you don't want to use templates, but this sort of thing is exactly what templates are for. By making your node class a virtual class, you force extra overhead on each construction and destruction, as well as expanding the size of the node struct by at least one pointer, which will reduce cache coherence.

此外，拒绝使用模板将导致您陷入 static_casts 和不安全代码的混乱。注意，例如，如果 pChilds 指向一个数组 MyNode 和 MyNode 有任何成员变量，那么下标运算符将不可见不能正常工作。

Also, refusing to use templates will lead you into a morass of static_casts and unsafe code. Note, for instance, that if pChilds points to an array of MyNode and MyNode has any member variables, then the subscript operator will invisibly not work properly.

这篇关于通用四叉树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！