四叉树模板的使用

技术

四叉树索引的基本思想是将空间递归划分为不同层次的树结构。它将已知范围的空间等分成四个相等的子空间，如此递归下去，直至树的层次达到一定深度或者满足某种要求后停止分割。四叉树的结构比较简单，并且当空间数据对象分布比较均匀时，具有比较高的空间数据插入和查询效率。

因为项目的需要，我选择使用四叉树为二维平面上的物体建立索引。我在github上找到了一个优秀的C++四叉树模板https://github.com/pvigier/Quadtree ，针对自己的项目特点进行了一些改进，并且，还基于该模板的思路制作了其它的数据结构，你可以访问我的github仓库查看相关代码。四叉树的原理比较简单，并且这个模板也很完善了，关于四叉树的原理，我不想将其作为本篇文章的重点（也没什么好提的，四叉树很好理解，如果有必要的话再来完善）。接下来，我会直接讲解以下我是怎样使用这个四叉树模板的，为了方便在工程中使用，我将模板的实例化和常用操作封装成了一个类。

模板实例化

Quadtree 模板的构造函数如下：

template<typename T, typename GetBox, typename Equal = std::equal_to<T>, typename Float = float>
class Quadtree
{
public:
    Quadtree(const Box<Float>& box, const GetBox& getBox = GetBox(),
        const Equal& equal = Equal()) :
        mBox(box), mRoot(std::make_unique<Node>()), mGetBox(getBox), mEqual(equal){}
    ...
private:
    Quadtree<myItem*, decltype(&getBox), std::equal_to<myItem*>, double> quadtree;
}

可以看到，在模板实例化时，我们需要定义4个typename，其参数分别为：

放入树中的对象类型
获取该对象所在区域(Box)的方法
比较对象类型是否相等的方法
四叉树的底层数据类型(Box等对象的数据类型)

模板名比较长，我们可以使用using对该类型进行定义：

using myQuadtree = Quadtree<myItem*, decltype(&getBox), std::equal_to<myItem*>, double>;

using 和 typedef 都可以定义类型的别名，它们的作用大致相同，但写法顺序略有不同。它们之间最大的区别再于，using可以在模板别名中使用，但是typedef不可以，在C++11以前的代码中，会使用这样的方法定义模板别名：
template <typename Val>
struct str_map
{
 typedef std::map<std::string, Val> type;
};
str_map<int>::type map1;
//  这样的处理有点丑陋，而更糟糕的是，如果你想要把这样的类型用在模板类或者进行参数传递的时候
//  你需要使用typename强制指定这样的成员为类型，如：
template <typename T>
class Widget
{
 typename str_map<T>::type map;
}
在定义诸如函数指针等类型时，typedef 也更加拗口：
typedef void (*FP) (int, const std::string&); // 等价于
using FP = void (*) (int, const std::string&);
总的来说，using 的适用范围更广并且更为易用，因此，在C++11后的代码中，尽量使用 using 而非 typedef

getBox() 函数

如果需要使用函数作为模板参数，那么这个函数需要在类外进行定义。这是因为模板参数在编译期进行类型检查，因此需要在类外声明函数，以便在编译期能够正确推导函数类型。如果函数的声明和定义都在类的内部，编译器无法在编译期正确推导函数的类型，因此会报错。所以，我们需要在class MyQuadtree外部进行定义：

static Box<double> getBox(myItem* item) {
    QRectF rect = item->relativeBoundRect();
    return Box<double>(rect.x(), rect.y(), rect.width(), rect.height());
}
// 然后，这样进行使用
class MyQuadtree {
public:
    MyQuadtree(QRectF region) :
    quadtree(Box<double>(region.x(), region.y(), region.width(), region.height()), getBox) {}
}

当然，你也可以使用lambda表达式进行函数类型的传递，但是同样需要在外部进行定义

/**
 *  对于使用Lambda表达式作为模板参数的情况，在成员变量声明中可能会出现 "Lambda expression
 *  in an unevaluated operand" 的错误。这是因为在模板参数列表中，编译器对模板参数进行类型
 *  检查，而Lambda表达式是一种运行时的实体，无法在编译期进行类型检查。
 *  为了解决这个问题，可以将Lambda表达式包装成一个函数对象类型，并将该函数对象类型作为模板参数。
 *  */
class GetBoxFunctor {
public:
    Box<double> operator()(myItem* item) {
        QRectF rect = item->relativeBoundRect();
        return Box<double>(rect.x(), rect.y(), rect.width(), rect.height());
    }
};

四叉树拓展的功能

为了方便使用，我在这个类中对四叉树进行了一些拓展：

快速查询

原本的查询使用vector作为返回值，这需要消耗一定的时间，考虑到查找的频率可能会非常高，因此我添加了新的方法effectiveQuery，以尽可能提高查询速度，它预先分配一段空间并将其数组指针p作为参数传入，将查找到的结果写入数组p中。然后，提供一个方法queryCacheSpace(int index) 来访问这段缓冲区，这样的做法减少了vector进行扩容操作的时间，具有更好的空间局部性，这样的写法能将原本耗时4ms的查询时间减少到2ms，效果还是比较显著的。自建缓冲区的做法也有缺点，它总会消耗掉等同于四叉树元素总数的内存，并且，这样的写法不支持多线程查询。

自动重建

四叉树有一个致命的缺陷，它具有范围限制，放入的元素必须处于其边界内部，在实际使用中，我希望能屏蔽这个缺点，因此，当试图放入超出四叉树边界范围的元素时，会对四叉树自动进行重建，将所有元素放入一个更大范围的四叉树。这部分的实现在add和rebuild方法中，你可以查看后面的代码查看它的实现。

边界查询

出于某些原因，我需要获取四叉树内所有元素所占区域的边界（不同于四叉树的边界），此处，我使用了懒更新的方法，提供一个元素边界缓存 elementRegionCache，并提供一个标记位regionNeedUpdate，当加入或删除元素时，将重置此标记位，当进行查询时，根据标记位的值直接返回缓存的边界或者重新计算边界。

封装的类内容如下：

class MyQuadtree {
public:
    MyQuadtree(QRectF region) :
    quadtree(Box<double>(region.x(), region.y(), region.width(), region.height()), getBox) {
        m_queryCacheSpace = (myItem**)malloc(sizeof(myItem*));
    }
    ~MyQuadtree() {
        free(m_queryCacheSpace);
    }
    void add(myItem* item) {
        if(!quadtree.getBox().contains(getBox(item))) {
            Box<double> oldBox = quadtree.getBox();
            Box<double> newBox;
            for(int i = 0; i < 5; ++i) {
                newBox = Box<double>(oldBox.left-oldBox.width, oldBox.top-oldBox.height, oldBox.width*3, oldBox.height*3);
                if(newBox.contains(getBox(item))) break;
                oldBox = newBox;
            }
            if(!newBox.contains(getBox(item))) {
                qCritical() << QIODevice::tr("quadtree: Wrong item range");
            }
            rebuild(newBox);
        }

        quadtree.add(item);
        regionNeedUpdate = true;
        ++elementNum;
    }
    void remove(myItem* item) {
        quadtree.remove(item);
        regionNeedUpdate = true;
        --elementNum;
    }
    void remallocQueryCacheSpace() {
        if(m_queryCacheSpaceCapacity >= elementNum) return ;
        free(m_queryCacheSpace);

        m_queryCacheSpace = (myItem**)malloc(sizeof(myItem*) * elementNum);

        m_queryCacheSpaceCapacity = elementNum;
    }
    QList<myItem*> query(QRectF area) const {
        if(area.intersects(elementRegion())) {
            area = area.intersected(elementRegion());
            std::vector<myItem*> values = quadtree.query(Box<double>(area.x(), area.y(), area.width(), area.height()));
            return QList<myItem*>(values.begin(), values.end());
        }
        else return QList<myItem*>();
    }
    /**
     * 将查询结果写入指针数组中，以减少构造数组的时间开销。
     * 在调用该函数会调用 remallocQueryCacheSpace() 为指针数组分配空间。
     * 调用 queryCacheSpace(int index) 获取查询的结果。
     * 对比QList，对于5万大小的数组，该方法可以减少约2ms的时间
     * 由于只有一个cacheSpace，该方法并不适用多线程查询的场景
     * */
    void effectiveQuery(QRectF area) {
        remallocQueryCacheSpace();
        m_queryCacheSpaceSize = 0;
        if(area.intersects(elementRegion())) {
            area = area.intersected(elementRegion());
            quadtree.effectiveQuery(Box<double>(area.x(), area.y(), area.width(), area.height()), m_queryCacheSpace, m_queryCacheSpaceSize, m_queryCacheSpaceCapacity);
        }
    }
    myItem* queryCacheSpace(int index) {
        assert(index < m_queryCacheSpaceSize);
        return m_queryCacheSpace[index];
    }
    int queryCacheSpaceSize() {
        return m_queryCacheSpaceSize;
    }
    QList<myItem*> query(QPointF pos) const {
        if(elementRegion().contains(pos)) {
            std::vector<myItem*> values = quadtree.query(Box<double>(pos.x(), pos.y(), 1, 1));
            return QList<myItem*>(values.begin(), values.end());
        }
        else return QList<myItem*>();
    }
    QList<myItem*> itemsList() {
        return query(QRectF(quadtree.getBox().left, quadtree.getBox().top, quadtree.getBox().width, quadtree.getBox().height));
    }

    /**
     * Returns the smallest rectangular area where all elements are located.
     * In extreme cases, efficiency can be very low, so don't call it frequently.
     **/
    QRectF elementRegion() const {
        Box<double> boxRegion;
        if(regionNeedUpdate) {
            boxRegion = quadtree.getElementRegion();
            elementRegionCache = boxRegion;
            regionNeedUpdate = false;
        } else {
            boxRegion = elementRegionCache;
        }

        return QRect(boxRegion.left, boxRegion.top, boxRegion.width, boxRegion.height);
    }

    QRect maxRegion() const {
        Box<double> box =  quadtree.getBox();
        return QRect(box.left, box.top, box.width, box.height);
    }
private:
    void rebuild(Box<double> newBox) {
        assert(newBox.contains(quadtree.getBox()));
        remallocQueryCacheSpace();
        effectiveQuery(maxRegion());
        quadtree = Quadtree<myItem*, decltype(&getBox), std::equal_to<myItem*>, double>(newBox, getBox);
        for(int i = 0; i < m_queryCacheSpaceSize; ++i) {
            quadtree.add(m_queryCacheSpace[i]);
        }
    }
private:
    Quadtree<myItem*, decltype(&getBox), std::equal_to<myItem*>, double> quadtree;
    mutable Box<double> elementRegionCache;
    mutable bool regionNeedUpdate = true;
    int elementNum = 0;
    int m_queryCacheSpaceSize = 0;
    int m_queryCacheSpaceCapacity = 1;
    myItem** m_queryCacheSpace;
};
}

如果觉得文章对你有用，请随意赞赏

C++

四叉树模板的使用

http://zhjiao.cn/archives/use-quadtree

作者

hang

发布于

2023-06-20

更新于

2025-03-21

许可协议

CC BY 4.0

四叉树模板的使用

模板实例化

getBox() 函数

四叉树拓展的功能

快速查询

自动重建

边界查询

作者

发布于

更新于

许可协议

评论