Quadtree 是一棵空间四叉树，用于将二维平面递归地四等分，每个树结点对应一块矩形区域，每个树结点的四个子结点就是该矩形区域的四个子区域，根结点表示整块大的区域，叶子结点表示不再细分的区域。
Quadtree 可用于在二维平面中进行快速的碰撞检测，可以将时间复杂度由 O(n) 降至 Θ(log4n)。
譬如下图中，需要找出可能会与绿色线段交叉的线段，只需去检测那些标记为湛蓝色的线段即可：
完整的由 C++ 实现的 Quadtree 模板类如下，其中 Boundary 表示矩形边界，该实现要求存储在其中的 object 对象含有一个 Boundary 类型的数据成员 bounds，而 bounds 表示的矩形是 object 的外接矩形：
#ifndef __QUADTREE_H__
#define __QUADTREE_H__
#include <stdint.h>
#include <stdio.h>
#include <list>
class Boundary
{
public:
Boundary() : x(0.0), y(0.0), width(0.0), height(0.0) {}
Boundary(double X, double Y, double W, double H) : x(X), y(Y), width(W), height(H) {}
Boundary(const Boundary& rhs) : x(rhs.x), y(rhs.y), width(rhs.width), height(rhs.height) {}
~Boundary() {}
public:
double x;
double y;
double width;
double height;
};
template<typename ObjectType>
class Quadtree
{
public:
Quadtree(double X, double Y, double W, double H, uint8_t _level) : boundary(X, Y, W, H), level(_level), northWest(NULL), northEast(NULL), southWest(NULL), southEast(NULL) {}
Quadtree(Boundary& bounds, uint8_t _level) : boundary(bounds), level(_level), northWest(NULL), northEast(NULL), southWest(NULL), southEast(NULL) {}
~Quadtree() { objects.clear(); }
void split(); // Split the node into 4 subnodes
Quadtree* getSub(Boundary& bounds);
void insert(ObjectType *object);
void erase(ObjectType *object);
void retrieve(ObjectType *object, std::list<ObjectType*>& returnObjects);
void clear();
public:
Boundary boundary;
// Children
Quadtree<ObjectType> *northWest;
Quadtree<ObjectType> *northEast;
Quadtree<ObjectType> *southWest;
Quadtree<ObjectType> *southEast;
uint8_t level;
uint8_t padding;
std::list<ObjectType*> objects;
static uint8_t max_objects; // max objects a node can hold before splitting into 4 subnodes (default: 10)
static uint8_t max_levels; // total max levels inside root Quadtree (default: 4)
};
template<typename ObjectType>
uint8_t Quadtree<ObjectType>::max_objects = 10;
template<typename ObjectType>
uint8_t Quadtree<ObjectType>::max_levels = 4;
/*
* Split the node into 4 subnodes
*/
template<typename ObjectType>
void Quadtree<ObjectType>::split()
{
uint8_t nextLevel = level + 1;
double X = boundary.x, Y = boundary.y, subWidth = boundary.width/2, subHeight = boundary.height/2;
northWest = new Quadtree<ObjectType>(X, Y+subHeight, subWidth, subHeight, nextLevel);
northEast = new Quadtree<ObjectType>(X+subWidth, Y+subHeight, subWidth, subHeight, nextLevel);
southWest = new Quadtree<ObjectType>(X, Y, subWidth, subHeight, nextLevel);
southEast = new Quadtree<ObjectType>(X+subWidth, Y, subWidth, subHeight, nextLevel);
}
/*
* Determine which node the object belongs to
* @param bounds bounds of the area to be checked, with x, y, width, height
* @return Quadtree* point to the subnode, or NULL if bounds cannot completely fit within a subnode and is part of the parent node
*/
template<typename ObjectType>
Quadtree<ObjectType>* Quadtree<ObjectType>::getSub(Boundary& bounds)
{
double horizontalMidpoint = boundary.x + (boundary.width / 2);
double verticalMidpoint = boundary.y + (boundary.height / 2);
// bounds can completely fit within the top quadrants
bool topQuadrant = (bounds.y > verticalMidpoint && bounds.y + bounds.height < boundary.y + boundary.height);
// bounds can completely fit within the bottom quadrants
bool bottomQuadrant = (bounds.y > boundary.y && bounds.y + bounds.height < verticalMidpoint);
// bounds can completely fit within the left quadrants
bool leftQuadrant = (bounds.x > boundary.x && bounds.x + bounds.width < horizontalMidpoint);
// bounds can completely fit within the right quadrants
bool rightQuadrant = (bounds.x > horizontalMidpoint && bounds.x + bounds.width < boundary.x + boundary.width);
if (topQuadrant && leftQuadrant)
return northWest;
else if (topQuadrant && rightQuadrant)
return northEast;
else if (bottomQuadrant && leftQuadrant)
return southWest;
else if (bottomQuadrant && rightQuadrant)
return southEast;
else
return NULL;
}
/*
* Insert the object into the node. If the node exceeds the capacity, it will split and add all
* objects to their corresponding subnodes.
* @param ObjectType *object bounds of the object to be added, with x, y, width, height
*/
template<typename ObjectType>
void Quadtree<ObjectType>::insert(ObjectType *object)
{
Quadtree<ObjectType> *subNode;
if (northWest != NULL) // if we have subnodes ...
{
if ((subNode = getSub(object->bounds)) != NULL)
{
subNode->insert(object);
return;
}
}
objects.push_back(object);
if (objects.size() > max_objects && level < max_levels)
{
if (northWest == NULL) // split if we don't already have subnodes
split();
for (typename std::list<ObjectType*>::iterator it = objects.begin(); it != objects.end();) // add all objects to there corresponding subnodes
{
subNode = getSub((*it)->bounds);
if (subNode != NULL)
{
subNode->insert(*it);
it = objects.erase(it);
}
else
++it;
}
}
}
/*
* Erase the object in the Quadtree.
* @param ObjectType *object bounds of the object to be added, with x, y, width, height
*/
template<typename ObjectType>
void Quadtree<ObjectType>::erase(ObjectType *object)
{
Quadtree<ObjectType> *subNode;
if (northWest != NULL) // if we have subnodes ...
{
if ((subNode = getSub(object->bounds)) != NULL)
{
subNode->erase(object);
return;
}
}
for (typename std::list<ObjectType*>::iterator it = objects.begin(); it != objects.end();)
{
if (*it == object)
{
it = objects.erase(it);
break;
}
else
++it;
}
}
/*
* Return all objects that could collide with the given object
* @param ObjectType *object bounds of the object to be checked, with x, y, width, height
* @return list<ObjectType*>& returnObjects list with all detected objects
*/
template<typename ObjectType>
void Quadtree<ObjectType>::retrieve(ObjectType *object, std::list<ObjectType*>& returnObjects)
{
Quadtree<ObjectType> *subNode = getSub(object->bounds);
returnObjects.insert(returnObjects.end(), objects.begin(), objects.end());
if (northWest != NULL) // if we have subnodes ...
{
if (subNode != NULL) // if bounds fits into a subnode ..
subNode->retrieve(object, returnObjects);
else // if bounds does not fit into a subnode, check it against all subnodes
{
northWest->retrieve(object, returnObjects);
northEast->retrieve(object, returnObjects);
southWest->retrieve(object, returnObjects);
southEast->retrieve(object, returnObjects);
}
}
}
/*
* Clear the quadtree
*/
template<typename ObjectType>
void Quadtree<ObjectType>::clear()
{
if (northWest != NULL)
{
northWest->clear();
delete northWest;
northWest = NULL;
}
if (northEast != NULL)
{
northEast->clear();
delete northEast;
northEast = NULL;
}
if (southWest != NULL)
{
southWest->clear();
delete southWest;
southWest = NULL;
}
if (southEast != NULL)
{
southEast->clear();
delete southEast;
southEast = NULL;
}
}
#endif