7

我有以下。该结构是原型的，因此可以正常编译。

struct vertexNodeInfo
{
    vector<vertexNodeInfo> node;
};

我正在尝试写一个八叉树的东西。我想要做的是使用递归函数继续向每个节点添加一个节点，直到我到达一个特定点，此时该函数而不是添加另一个节点，而是添加一个叶子。如果可能的话，我想在没有添加更多节点或叶子时不使用内存。

也许模板在这种情况下会有所帮助，但我不知道如何使用它们......

我认为我没有很好地解释自己。这是一个图表：

分支递归结构

我不知道我所要求的内容是不可能的，还是太混乱而无法理解，或者只是愚蠢的，但我自己无法弄清楚。对不起，我无法更好地解释它。

我正在使用 C++98/03 (VC++2008) 并且不能使用 C++11

任何帮助都将不胜感激。

附加信息：

更好的解释：我想要一个数组数组的数组数组。内存使用在这方面非常重要（我存储了数百万个元素，因此单个字节会产生巨大的差异）。每个数组可以包含 8 个以上的数组，但在我需要使用它之前，我希望每个数组都不使用内存。这是一个八叉树。

更多附加信息：

这是另一个图表。它有点大，因此您可能需要右键单击它并选择Open image in new tab使其可读。

我不想要的是“棕色”（红色+绿色）框，其中每个框都为更多节点和叶数据保留内存。这将使用太多的内存来满足我的需求。

这基本上是我想要实现的目标，为简单起见，如图 2D 所示：

我对八叉树的想法的 2D 示例

4

4 回答 4

8

没有任何（手动）堆分配[1]：

struct NodeInfo { 
    int id; 
};

using Tree = boost::make_recursive_variant<
        NodeInfo,
        std::vector<boost::recursive_variant_>
    >::type;

我知道变体带有它们自己的“复杂性”，但保留了内存局部性并避免了手动内存管理。

现在，为了更接近您声明的优化目标，您可以使用std::array<T, 8>而不是std::vector，或者只是vector自定义使用allocator从内存池中分配。

示例程序（在 Coliru 上查看 Live）：

#include <iostream>
#include <boost/variant.hpp>
#include <vector>

struct NodeInfo { 
    int id; 
};

using Tree = boost::make_recursive_variant<
        NodeInfo,
        std::vector<boost::recursive_variant_>
    >::type;

// for nicer code:
using Branch = std::vector<Tree>;
using Leaf   = NodeInfo; 

static std::ostream& operator<<(std::ostream& os, Leaf const& ni) { 
    return os << ni.id; 
}
static std::ostream& operator<<(std::ostream& os, Branch const& b) { 
    os << "{ ";
    for (auto& child: b) os << child << " ";
    return os << "}";  
}

int main()
{
    Branch branch1 { 
        Leaf { 2 }, 
        Leaf { 1 }, 
        Branch { 
            Leaf { 42 }, 
            Leaf { -42 }, 
        }
    };

    Tree tree = Branch { branch1, Leaf { 0 }, branch1 };

    std::cout << tree << "\n";
}

印刷：

{ { 2 1 { 42 -42 } } 0 { 2 1 { 42 -42 } } }

[1]（在使用 std::vector 之外）

于 2013-10-20T14:43:06.347 回答
2

八叉树的核心结构是

struct Node {
    std::vector<T> items;
    std::array<std::unique_ptr<Node>, 8> subnodes;
    Box BoundingBox;
};
class Octree {
    Node n;
    //... stuff
public:
    Octree(Box location)
       : n(location) {}
};

如果您迫切需要叶节点上的一些额外字节（以及非叶节点上丢失的一些字节），您可以尝试使用指向子节点数组的指针，而不是按值保存它。

现在，如果T 是一个点，那么您可以使用 boost::variant 来仅存储 theitems 或the subnodes，因为每个点都保证恰好存在于一个子节点中，并且您可以选择具有items和之间的任意截止点有subnodes.

否则，如果 T 是一种边界框，您将无法逃脱，因为不完全适合任何子节点的边界框必须进入items列表，因此items无论是否存在列表都必须存在子节点。

我还要说的是，如果您迫切需要时间或空间优化，您应该认真研究自定义内存分配例程。

编辑：是的，我使用了一个指针数组，而不是指向数组的指针。总而言之，在没有强大的 C++11 支持的情况下描述该数组的正确初始化是一个彻头彻尾的婊子，在我个人的使用中，它并不能保证我实际上在制造该死的东西时遇到的严重问题。std::unique_ptr<std::array<Node>, 8>如果你愿意，你可以试试。从理论上讲，它应该是更好的选择。

于 2013-10-21T00:45:25.507 回答
0

多态性呢？

struct TreeElem {
    virtual ~TreeElem() {}
};

struct Node : public TreeElem {
    std::vector<TreeElem*> _children;
};

struct Leaf : public TreeElem {
    int _value;
};

您可以找出其余的（TreeElem 的虚拟成员）。

PS：如果它不仅仅是微不足道的，请使用智能指针。

于 2013-10-20T12:04:30.740 回答
-1

检查 che复合模式，您可以轻松地调整它以执行八叉树。在此之后，创建以实际八叉树深度为参数的递归函数，这样您就可以轻松地执行您想要的操作。不幸的是，我不太了解你的问题，所以我不能更准确。

于 2013-10-20T12:11:55.123 回答