在单独的数据结构中保存八叉树叶节点的顶点

Question

我正在尝试为空间分解算法实现我自己的八叉树 class。我想做的是遍历树并将叶节点的顶点保存在向量中。

到目前为止，我以这种方式实现了八叉树（为简单起见，它是二维的）：

class AxisAlignedBox
{
public:
AxisAlignedBox(){}

AxisAlignedBox(Eigen::Vector2f min, Eigen::Vector2f max):_min(min),_max(max)
{
    _halfWidth = (_max(0) - _min(0))/2;
    _center << _min(0) + _halfWidth,_min(1) + _halfWidth;
}

AxisAlignedBox(Eigen::Vector2f center, float halfWidth):_center(center),_halfWidth(halfWidth)
{
    _min << _center(0) - _halfWidth,_center(1) - _halfWidth;
    _max << _center(0) + _halfWidth,_center(1) + _halfWidth;
}

void splitBox(AxisAlignedBox *boxes)
{
    int idx = 0;
    float halfWidth = _halfWidth/2;
    for(int j = -1; j < 2; j += 2)
        for(int i = -1; i < 2; i += 2)
        {
            boxes[idx] = AxisAlignedBox(Eigen::Vector2f (_center(0)+i*halfWidth,_center(1)+j*halfWidth),halfWidth);
            idx++;
        }

}

bool inRange(Eigen::Vector2f point)
{
    if(point(0) > _min(0) && point(0) < _max(0) && point(1) > _min(1) && point(1) < _max(1) )
        return true;
    else
        return false;
}

Eigen::Vector2f getMin(){return _min;}

Eigen::Vector2f getMax(){return _max;}

Eigen::Vector2f getCenter(){return _center;}

private:
Eigen::Vector2f _min;
Eigen::Vector2f _max;
Eigen::Vector2f _center;
float _halfWidth;
};

class OctreeNode
{
public:
OctreeNode(int depth, std::vector<Eigen::Vector2f> points, Eigen::Vector2f  min, Eigen::Vector2f max):_depth(depth)
{
    if(_depth < 0)
    {
        return;
    }
    else
    {
        _box = AxisAlignedBox(min,max);
        _points = points;

        AxisAlignedBox boxes[4];
        _box.splitBox(boxes);

        std::vector<Eigen::Vector2f> splittedPoints [4];

        for(int ii=0; ii < _points.size(); ii++)
            for(int boxId = 0; boxId < 4; boxId++)
                if(boxes[boxId].inRange(_points.at(ii)))
                    splittedPoints[boxId].push_back(_points.at(ii));

        for(int i = 0; i < 4; i++)
            if(!splittedPoints[i].empty())
            {
                _children[i] = new OctreeNode(depth-1,splittedPoints[i],boxes[i].getMin(),boxes[i].getMax());
            }
    }
}

OctreeNode* getChild1(){return _children[0];}
OctreeNode* getChild2(){return _children[1];}
OctreeNode* getChild3(){return _children[2];}
OctreeNode* getChild4(){return _children[3];}
int getDepth(){return _depth;}
AxisAlignedBox getBox(){return _box;}
private:
int _depth;
AxisAlignedBox _box;
std::vector<Eigen::Vector2f> _points;
OctreeNode* _children[4];
};

要用这个class，这是我在main里写的：

#include <iostream>
#include "AdaptiveGrid.h"

void visit(OctreeNode* octree);


int main()
{
std::vector<Eigen::Vector2f> dataSet;

for(float theta = 0; theta < 2*M_PI; theta += 0.034)
    dataSet.push_back(Eigen::Vector2f(0.8*cos(theta),0.8*sin(theta)));

Eigen::Vector2f min(-1,-1);
Eigen::Vector2f max(1,1);

std::cerr << "Dataset has " << dataSet.size() << " points\n";

OctreeNode *octree = new OctreeNode(2,dataSet,min,max);

visit(octree);

return 0;
}

void visit(OctreeNode* octree)
{
if(octree)
{
    if(octree->getDepth() == 0)
    {
        std::cerr << "Depth: " << octree->getDepth() << "\n";
        std::cerr << "center: " << octree->getBox().getCenter().transpose() << "\n";
    }
    visit(octree->getChild1());
    visit(octree->getChild2());
    visit(octree->getChild3());
    visit(octree->getChild4());
}
}

但是在访问第一个叶节点后，我得到一个分段错误：

dede@dede-P35V2:~/build/AdaptiveGrid/build$ ./adapative_grid

Dataset has 185 points

Depth: 0

center: -0.75 -0.75

Segmentation fault

拜托，你能解释一下我做错了什么吗？

谢谢。

Answer 1

您做错了什么：您忘记用 NULL 初始化 OctreeNode* _children[4];。

将行替换为：OctreeNode* _children[4] = { NULL, NULL, NULL, NULL };

在单独的数据结构中保存八叉树叶节点的顶点

Saving vertices of Octree leaf nodes in separate Data Structure

c++

tree-traversal

octree