四叉树实现_编程黑洞网

我已经在C ++中实现了一个四叉树。我发誓，忽略与Wikipedia上伪代码的任何明显相似之处，全都在您的脑海中。

我该如何改善它？算法速度/空间的改进，我可能想要的任何其他功能...以及一般实践。

#ifndef _QUADTREE_H_
#define _QUADTREE_H_

#include <vector>
#include <iostream>

struct Point
{
    float x, y;
    Point(float x = 0, float y = 0):x(x), y(y){};
};

struct AABB
{
    Point centre;
    Point halfSize;

    AABB(Point centre = Point(), Point halfSize = Point()): centre(centre), halfSize(halfSize){};

    bool contains(Point a)
    {
        if(a.x < centre.x + halfSize.x && a.x > centre.x - halfSize.x)
        {
            if(a.y < centre.y + halfSize.y && a.y > centre.y - halfSize.y)
            {
                return true;
            }
        }
        return false;
    }

    bool intersects(AABB other)
    {
        //this right > that left                                          this left <s that right
        if(centre.x + halfSize.x > other.centre.x - other.halfSize.x || centre.x - halfSize.x < other.centre.x + other.halfSize.x)
        {
        // This bottom > that top
            if(centre.y + halfSize.y > other.centre.y - other.halfSize.y || centre.y - halfSize.y < other.centre.y + other.halfSize.y)
            {
                return true;
            }
        }
        return false;
    }
};

template <typename T>
struct Data
{
    Point pos;
    T* load;

    Data(Point pos = Point(), T* data = NULL): pos(pos), load(data){};
};


template <class T>
class Quadtree
{
    private:
        //4 children
        Quadtree* nw;
        Quadtree* ne;
        Quadtree* sw;
        Quadtree* se;

        AABB boundary;

        std::vector< Data<T> > objects;

        int CAPACITY;       
    public:
        Quadtree<T>();
        Quadtree<T>(AABB boundary);

        ~Quadtree();

        bool insert(Data<T> d);
        void subdivide();
        std::vector< Data<T> > queryRange(AABB range);
};

template <class T>
Quadtree<T>::Quadtree()
{
    CAPACITY = 4;
    nw = NULL;
    ne = NULL;
    sw = NULL;
    se = NULL;
    boundary = AABB();
    objects = std::vector< Data<T> >();
}

template <class T>
Quadtree<T>::Quadtree(AABB boundary)
{
    objects = std::vector< Data<T> >();
    CAPACITY = 4;
    nw = NULL;
    ne = NULL;
    sw = NULL;
    se = NULL;
    this->boundary = boundary;
}

template <class T>
Quadtree<T>::~Quadtree()
{
    delete nw;
    delete sw;
    delete ne;
    delete se;
}

template <class T>
void Quadtree<T>::subdivide()
{
    Point qSize = Point(boundary.halfSize.x, boundary.halfSize.y);
    Point qCentre = Point(boundary.centre.x - qSize.x, boundary.centre.y - qSize.y);
    nw = new Quadtree(AABB(qCentre, qSize));

    qCentre = Point(boundary.centre.x + qSize.x, boundary.centre.y - qSize.y);
    ne = new Quadtree(AABB(qCentre, qSize));

    qCentre = Point(boundary.centre.x - qSize.x, boundary.centre.y + qSize.y);
    sw = new Quadtree(AABB(qCentre, qSize));

    qCentre = Point(boundary.centre.x + qSize.x, boundary.centre.y + qSize.y);
    se = new Quadtree(AABB(qCentre, qSize));
}

template <class T>
bool Quadtree<T>::insert(Data<T> d)
{
    if(!boundary.contains(d.pos))
    {
        return false;
    }

    if(objects.size() < CAPACITY)
    {
        objects.push_back(d);
        return true;
    }

    if(nw == NULL)
    {
        subdivide();
    }

    if(nw->insert(d))
    {
        return true;
    }
    if(ne->insert(d))
    {
        return true;
    }
    if(sw->insert(d))
    {
        return true;
    }
    if(se->insert(d))
    {
        return true;
    }

    return false;   
}

template <class T>
std::vector< Data<T> > Quadtree<T>::queryRange(AABB range)
{
    std::vector< Data<T> > pInRange = std::vector< Data<T> >();

    if(!boundary.intersects(range))
    {
        return pInRange;
    }

    for(int i = 0; i < objects.size(); i++)
    {
        if(range.contains(objects.at(i).pos))
        {
            pInRange.push_back(objects.at(i));
        }
    }

    if(nw == NULL)
    {
        return pInRange;
   }

    std::vector< Data<T> > temp = nw->queryRange(range);
    pInRange.insert(pInRange.end(), temp.begin(), temp.end());

    temp = ne->queryRange(range);
    pInRange.insert(pInRange.end(), temp.begin(), temp.end());

    temp = sw->queryRange(range);
    pInRange.insert(pInRange.end(), temp.begin(), temp.end());

    temp = se->queryRange(range);
    pInRange.insert(pInRange.end(), temp.begin(), temp.end());

    return pInRange;
}
#endif

我对定义并不特别满意CAPACITY就像我一样，将const int CAPACITY = 4;放在标头中要比两次拥有更好，但是在类声明中进行初始化是C ++ 14，对吗？

该死的@Morwenn我是英语。初始化与您的异教徒拼写。

很抱歉，您可以随意回滚。我能理解你的痛苦ç_____ç

@Morwenn别担心，我不会通知女王。我知道这不是代表农，而且我很确定殖民地的人口要多于母国。

@Yann您可以将更新版本发布到某处吗？

看起来像摘自Wikipedia伪代码！

#1 楼

好的，所以这里有一些提示：因此，您应该AABB::contains -qualify这些方法，以确保它们也可以在AABB::intersects上下文中调用。

bool intersects(AABB other) const { /* ... */ }
                            ^^^^^

@glampert在在评论中，一个AABB实例重载了四个const，因此与内置类型相比，它变得非常繁重。因此，当您将其传递给函数时，如果只计划从其读取而不进行修改，则可能希望通过const引用传递它，而不是按值传递它：

bool intersects(const AABB& other) const { /* ... */ }
                ^^^^^     ^

AABB以下划线开头，后跟一个大写字母。因此，它是为实现保留的标识符。要解决此问题，最简单的方法是放下下划线并改用float。
在任何可能的情况下（提示：始终），请使用const代替_QUADTREE_H_以避免细微和棘手的过载问题。
从从C ++ 11开始，您可以编写QUADTREE_H_而不是nullptr来默认初始化NULL。如果您想更改类名，它会更麻烦，并且更改量会减少。 />

Point qSize = { boundary.halfSize.x, boundary.halfSize.y };

请注意，在这种情况下，您实际要写的可能是这样的：

Point qSize = boundary.halfSize;

请注意，如果需要执行更多的Point pos = {} / Point pos = Point()算术运算，则最好实现完整类并重载运算符以提高可读性，并避免每次执行简单运算时都必须逐个坐标地编写所有内容。 />

如果Point绝不打算更改，则可以将其设为Point成员变量。另外，我不会使用Vector作为其名称，这是我们通常用来表示使用宏的情况。

static constexpr int capacity = 4;

可以使用构造函数初始化列表，以便在构造对象之后编译器不必为变量赋值：

template <class T>
Quadtree<T>::Quadtree():
    nw{nullptr},
    ne{nullptr},
    sw{nullptr},
    se{nullptr}
{}

您不必显式默认初始化其他参数，因为如果您不编写任何内容，它们仍将默认初始化。

您有一个旧的C样式CAPACITY循环，此处具有基于索引的迭代：

for(int i = 0; i < objects.size(); i++)
{
    if(range.contains(objects.at(i).pos))
    {
        pInRange.push_back(objects.at(i));
    }
}

我确定您会喜欢基于C ++ 11范围的static constexpr循环：

for(auto&& object: objects)
{
    if(range.contains(object.pos))
    {
        pInRange.push_back(object);
    }
}

嘿，这很麻烦，您不必再担心一次循环的错误了：)

此外，您想知道类初始化器是否为C ++ 14 。好消息，它们在C ++ 11中可用。它们只是稍作升级以涵盖C ++ 14中更晦涩的情况，因此您可以像这样完全编写ALLCAPS_CASE类：

struct Point
{
    float x = 0.0f;
    float y = 0.0f;
};

然后，构造函数将使用类内初始化程序初始化结构。请注意，我将for更改为for，这是Point的正确文字。虽然正确的文字通常无关紧要，但在类型推导的C ++世界中，正确使用它们变得越来越重要。

\ $ \ begingroup \ $
关于第一点，关于函数参数，我建议使用const引用以避免不必要的复制。（每个AABB至少有4个浮点，这有点浪费）。
\ $ \ endgroup \ $
–glampert
2015年3月18日15:57

\ $ \ begingroup \ $
很好的建议，我正在努力进行更新。小笔记；点qSize = {boundary.halfSize.x，boundary.halfSize.y};应该是这种格式，但是因为我是个白痴。它必须是Point qSize = {boundary.halfSize.x / 2，boundary.halfSize.y / 2};。感谢您指出了这一点
\ $ \ endgroup \ $
–颜
15年3月18日在15:58

\ $ \ begingroup \ $
由于性能原因，使用初始化列表更好吗？即使在编译时间？我以为那只是语法糖。
\ $ \ endgroup \ $
–颜
15年3月18日在16:01

\ $ \ begingroup \ $
@Yann如果有的话，性能可能会被忽略，但是无论如何它永远不会变慢。它不会花费更多，因此使用它们就像避免过早的悲观化:)
\ $ \ endgroup \ $
–莫文
15年3月18日在16:03

\ $ \ begingroup \ $
@glampert我无法一次解决所有问题，帖子越来越完整，对延迟x表示歉意）
\ $ \ endgroup \ $
–莫文
15年3月18日在16:03

#2 楼

我认为您正在计算的子树边界中心与成员名称不匹配：例如，nw的中心位置实际上应该是sw的中心位置。

这可能是如果您将根据父级树的中心根据对象和子节点的位置添加用于选择正确子级节点的优化，则会出现问题（我想您应该这样做，例如，如果要使用此四叉树进行存储

同样，但我不确定，我认为quadTree背后的一些逻辑是仅将数据存储在叶节点上。现在，您将部分数据存储在每个节点中，并根据需要扩展树：这将导致在每个节点中执行搜索操作，这会使每个节点的逻辑复杂化，这可能是次优的解决方案。

#3 楼

抱歉，我参加这个聚会很晚，但是您的代码实际上对我有用，所以我将其作为自己的开始。这是我对样式的评论。

无需；后功能。仅声明以分号结尾。
传递较大的ABB对象时，请考虑使用const＆而不是复制来传递参数。复制少于3个字的对象更快。这是4个浮点数，有点过分，但我会检查。当然，如果您使用double，请通过引用传递。
2b。 AABB是一个奇怪的名字。边界会更好。
当代码太短时，请勿将其从类中拉出。构造函数和析构函数各有4行，当保留在类定义中时，代码将变得更易读且更短，这是无论如何都希望内联代码的那种代码。
不要按值传递数据！！！这是巨大的，您不知道T有多大。
迄今为止，我始终发现它是最大的参考。
到目前为止，我发现最大的是在插入中，您正在测试nw，ne，sw，se。您应该比较自己的价值，然后决定不做所有尝试而决定做哪一项！
您可以考虑在顶部仅使用一个边界框，并动态计算每个子四叉树的边界。它可能同样快，并且占用的空间会大大减少。

\ $ \ begingroup \ $
关于您的＃1，在函数定义之后，我看不到他有分号的任何地方。分号在类/结构定义之后，在这些地方是必需的。
\ $ \ endgroup \ $
–科迪·格雷
17年1月6日在9:00