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