当前位置: 首页 > 知识库问答 >
问题:

C中的四叉树实现:异常抛出读访问冲突

宣星光
2023-03-14

我试图在C语言中实现一个四叉树,但是我有一个读访问冲突,我花了几个小时试图弄清楚。请注意,我已将所有成员变量公开,仅用于调试工作。

每当我试图细分一个象限,即根象限,我得到

抛出异常:读取访问冲突。标准::_Vector_alloc

四叉树由一个指向连续象限数组的指针和点组成。这些指针被传递到每一个象限,所以它们能够写入而不需要复制。

我做错了什么?你能提出改进的建议吗?

这是我的四叉树类:

  class Quadtree
{
private:

    Boundary rootBoundary;
public:
    std::vector<Ball>* dataPtr = nullptr;
    std::vector<Quadrant>* quadrantPtr = nullptr;
    Quadtree(const Boundary& b);


};

    Quadtree::Quadtree(const Boundary& bo)
    :rootBoundary(bo)
{
    std::vector<Ball>* bPtr = new std::vector<Ball>;
    std::vector<Quadrant>* qPtr = new std::vector<Quadrant>;
    quadrantPtr = qPtr;
    dataPtr = bPtr;


    Quadrant Root(bo, quadrantPtr, dataPtr);

}

四叉树包含所有象限以及数据存储。

这是象限类:

 class Quadrant
    {
    private:

    public:
        std::vector<Quadrant>* quadrantPtr = nullptr;
        std::vector<Ball>* dataPtr = nullptr;
        Boundary m_boundary;
        std::vector<unsigned int> elementIndex;
        int first_child_index = -1;
        int count = 0;

        Quadrant(Boundary b, std::vector<Quadrant>* qPtr, std::vector<Ball>* dPtr);
        void Subdivide();
        bool Insert(Ball* Ball);
        void Display(sf::RenderWindow& myWindow);

    };


Quadrant::Quadrant(Boundary b, std::vector<Quadrant>* qPtr, std::vector<Ball>* bPtr)
    :dataPtr(bPtr), quadrantPtr(qPtr), m_boundary(b)
{
    qPtr->push_back(*this);
}
void Quadrant::Subdivide()
{
    float cx = m_boundary.m_Centre.x;
    float cy = m_boundary.m_Centre.y;
    float qw = m_boundary.m_halfSize.x / 2;
    float qh = m_boundary.m_halfSize.y / 2;

    sf::Vector2f halfSize{ qw, qh };
    first_child_index = quadrantPtr->size();

    Boundary NE(sf::Vector2f{ cx + qw, cy - qh }, halfSize);
    Quadrant NEQ(NE, quadrantPtr, dataPtr);
    Boundary NW(sf::Vector2f{ cx - qw, cy - qh }, halfSize);
    Quadrant NWQ(NW, quadrantPtr, dataPtr);
    Boundary SE(sf::Vector2f{ cx + qw, cy + qh }, halfSize);
    Quadrant SEQ(SE, quadrantPtr, dataPtr);
    Boundary SW(sf::Vector2f{ cx - qw, cy + qh }, halfSize);
    Quadrant SWQ(SW, quadrantPtr, dataPtr);


}

bool Quadrant::Insert(Ball* ball)
{
    if (!m_boundary.ContainsPoint(*ball))
    {
        return false;
    }
    if (count < 4)
    {
        elementIndex.push_back(dataPtr->size());
        count++;
        return true;
    }
    else
    {
        if (first_child_index == -1)
        {
            std::cout << "subdividing" << std::endl;
            Subdivide();
        }
        for (int i = 0; i < 4; i++)
        {
            if (quadrantPtr->at(first_child_index + i).Insert(ball))
            {
                return true;
            }
        }
    }

}

void Quadrant::Display(sf::RenderWindow& myWindow)
{
    myWindow.draw(m_boundary.boundary);
    if (first_child_index != -1)
    {
        for (int i = 0; i < 4; i++)
        {
            quadrantPtr->at(first_child_index + i).Display(myWindow);
        }
    }
}

以下是表示象限AABB的边界类:

class Boundary
{
private:

public:
    sf::Vector2f m_Centre;
    sf::Vector2f m_halfSize;
    sf::RectangleShape boundary;
    Boundary();
    Boundary(const sf::Vector2f& centre, const sf::Vector2f& halfSize);
    bool ContainsPoint(const Ball& ball) const;
    ~Boundary();

};

Boundary::Boundary()
{

}
Boundary::Boundary(const sf::Vector2f& Centre, const sf::Vector2f& HalfSize)
    :m_Centre(Centre), m_halfSize(HalfSize)
{
    boundary.setSize(m_halfSize + m_halfSize);
    boundary.setOrigin(m_halfSize);
    boundary.setPosition(m_Centre);
    boundary.setFillColor(sf::Color::Transparent);
    boundary.setOutlineColor(sf::Color::White);
    boundary.setOutlineThickness(2);
}
bool Boundary::ContainsPoint(const Ball& ball) const
{
    bool contains = false;
    if (ball.ball.position.x > m_Centre.x - m_halfSize.x && ball.ball.position.x < m_Centre.x + m_halfSize.x)
    {
        if (ball.ball.position.y > m_Centre.y - m_halfSize.y && ball.ball.position.y < m_Centre.y + m_halfSize.y)
        {
            contains = true;
        }
    }
    return contains;
}

共有1个答案

谭琛
2023-03-14

您的< code>Root对于构造函数来说是本地的。也就是说,它在< code>Quadtree构造结束时被销毁。改为使其成为类成员。

你也不需要用< code>new来创建向量,它们本身就是指针。使它们也成为类成员,并使用< code >

注意:成员顺序很重要,它是它们初始化的顺序。

 类似资料:
  • 我正在尝试为我的3D环境创建一个四叉树(所有元素都在平坦的地形上,因此它们可以用2D数据表示),但我对它的精细部分的实现有点迷路。 我将首先描述我当前的四叉树,然后讨论它的缺陷,然后提出问题。 我目前拥有的是一个四边形树,它接受一个非常具体的矩形,我在其中定义了x,z,宽度和前向。以下是我的操作概述。 将对象插入四元树: 检查当前节点是否有子节点。如果是,请检查对象是否能够完全适应四个节点中的任何

  • 主要内容:一个动态数组的例子,throw 用作异常规范,请抛弃异常规范,不要再使用它在《 C++异常处理》一节中,我们讲到了 C++ 异常处理的流程,具体为: 抛出(Throw)--> 检测(Try) --> 捕获(Catch) 异常必须显式地抛出,才能被检测和捕获到;如果没有显式的抛出,即使有异常也检测不到。 在 C++ 中,我们使用 throw 关键字来显式地抛出异常,它的用法为: throw exceptionData; exceptionData 是“异常数据”的意思,它

  • 四叉树是一个二维空间递归细分。它使用了平分划分实现,将每一个块平分成了四个同等大小的方块。每个点存在于一个唯一的节点中;如果同一位置包含多个点,那么这多个点中的其中一些点将存储于内部节点,而非叶子结点。四叉树可用于加速各种空间操作,例如计算正多边形的体积的Barnes-Hut近似算法或者冲突检验。 d3.geom.quadtree() 创建一个新的四叉树工厂使用默认的x访问器,y访问器及范围。返回

  • 我读过这段代码,其中接口抛出异常,但实现它的类没有抛出异常或捕获异常,这是为什么?它在java中是合法的还是安全的?

  • 抛出异常的行为是否可能抛出不同的异常? 为了抛出异常,必须(可选地)分配新对象,并调用其构造函数(隐式调用fillinstacktrace)。在某些情况下,听起来像addSupressed也被称为。那么如果没有足够的内存会发生什么呢?JVM是否需要预分配内置异常?例如,(1/0)会抛出OutOfMemoryError而不是ArithmeticException吗? 此外,构造函数是一个方法调用,因

  • 当调用glDraweElements()时,我得到了一个错误,我不知道为什么:/I是使用OpenGL的新手,我正在尝试了解它的工作原理。 注意:我正在使用此库将OBJ文件转换为OpenGL应该能够使用的数组:https://github.com/korre/java-obj-to-opengl/blob/master/MeshObjectLoader.java