7

私は次のものを持っています。構造体はプロトタイプ化されているため、正常にコンパイルされます。

struct vertexNodeInfo
{
    vector<vertexNodeInfo> node;
};

私はoctreeのことを書こうとしています。私がやりたいことは、再帰関数を使用して、特定のポイントに到達するまで各ノードにノードを追加し続けることです。その時点で、関数は別のノードを追加するのではなく、リーフを追加します。可能であれば、ノードまたはリーフが追加されていない場合は、メモリを使用したくありません。

この状況ではテンプレートが役立つかもしれませんが、それらの使用方法がわかりません...

自分のことをうまく説明できていないと思います。これが図です:

分岐再帰構造体

私が求めていることが不可能なのか、理解するのが難しすぎるのか、それとも単純にばかげているのか、私にはわかりませんが、自分でそれを理解することはできません. うまく説明できなくてすみません。

C++98/03 (VC++2008) を使用していますが、C++11 を使用できません

どんな助けでも大歓迎です。

追加情報:

より良い説明: データの配列の配列の配列の配列が必要です。これにはメモリ使用量が非常に重要です (私は数百万の要素を保存しているので、1 バイトが大きな違いになります)。各配列にはさらに 8 つの配列を含めることができますが、それを使用する必要があるまでは、各配列がメモリを使用しないようにしたいと考えています。それは一種のオクトリーです。

その他の追加情報:

これが別の図です。少し大きいので、右クリックして選択する必要があるかもしれませんOpen image in new tab

私が望んでいないのは、すべてのボックスがより多くのノードとリーフ データの両方のためにメモリを予約する「茶色」(赤 + 緑) のボックスです。それは私のニーズに対してあまりにも多くのメモリを使用します。

これは基本的に私が達成しようとしているもので、簡単にするために 2D として描かれています。

octree の私の考えの 2D の例

4

4 に答える 4

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 を使用してitems またはのみを格納することで回避できます。これは、各ポイントが正確に 1 つのサブノードに存在することが保証されており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

複合パターンを確認すると、八分木を実行するように簡単に適応させることができます。この後、実際のオクツリーの深さを引数として取る再帰関数を作成して、必要なことを簡単に実行できるようにします。残念ながら、私はあなたの質問をよく理解していないので、これ以上正確には言えません。

于 2013-10-20T12:11:55.123 に答える