当前位置：首页 > news >正文

几何数据结构之四叉树与八叉树

news 来源：原创 2025/6/8 16:28:43

几何数据结构之四叉树与八叉树

- 四叉树的定义
- 四叉树深度的计算公式推导
- - 假设：
  - 计算过程：
  - - 1. 划分空间：
    - 2. 节点容纳的最小距离：
    - 3. 解出深度：
    - 4. 考虑常数项：
  - 总结：
- 八叉树

四叉树的定义

四叉树（Quadtree）：是一颗包含树根（Root）的树，每个节点包含四个子节点。我们常见用于描述四叉树的形式如下图：

在这里插入图片描述
它一个节点可以存储四个子节点的数据。当然，我们还可以采用其他形式来描述四叉树。

如下图所示：

在这里插入图片描述
树中每个节点有四个子节点，我们可以把每个节点看作一个正方形，最外围的正方形，包含四个第二大的正方形，同样的，第二大的也包含四个第三大正方形。
当然，我们可以以象限来描述它，一个正方形，被十字叉分为了四个象限，一个象限就代表了一个节点，我们可以不断的递归的去取正方形的边长中点，直到正方形中只存在一个点的。

四叉树是一种空间划分数据结构，通常用于存储二维平面中的点。四叉树将空间递归地划分为四个象限（子区域），并将点插入到对应的子区域中。

插入过程：
每个节点表示一个矩形区域，如果该区域可以容纳更多的点，它就会插入点；如果已经达到阈值（例如最多只能容纳 4 个点），则会进行分割，将区域划分为 4 个子区域。
子区域的插入：每当点超出当前节点的边界时，应该递归到下一个合适的子区域中。如果某个点仍然位于当前节点的范围内，则将其插入到当前节点。
子节点的划分：当节点满了（即点数量超过设定阈值），它将自己分割成 4 个子节点，每个子节点管理一个象限的区域。

四叉树深度的计算公式推导

假设：

初始区域的边长是 ( S )。
每个节点容纳的最小距离是 ( C )，即空间中任意两个点之间的最小距离为 ( C )，所以每个子区域将尽可能容纳这种最小距离的点。

计算过程：

1. 划分空间：

四叉树的每一层将空间分为四个象限（子区域）。如果在深度为 ( d ) 的层次，空间被划分为 ( 4^d ) 个子区域，那么每个子区域的大小将是：

$\text{子区域边长} = \frac{S}{2^d}$

2. 节点容纳的最小距离：

每个子区域容纳的最小点间距是 ( C )，所以在每个子区域中，至少应该有足够的空间容纳这种最小距离的点。为了确保每个子区域中有两个点之间的最小距离不小于 ( C )，我们有以下条件：

$\frac{S}{2^d} \geq C$

这意味着每个子区域的边长必须大于等于最小点距离 ( C )，否则就需要进一步划分。

3. 解出深度：

根据上面的不等式，求得最小深度 ( d )：

$\frac{S}{2^d} \geq C \quad \Rightarrow \quad 2^d \leq \frac{S}{C} \quad \Rightarrow \quad d \leq \log_2 \left( \frac{S}{C} \right)$

4. 考虑常数项：

实际应用中，可能还需要考虑额外的调整常数项，通常为 $\frac{3}{2}$ ，用于补偿一些实现中的空间管理开销或其他实际细节。因此，四叉树的深度可以表示为：

$\text{深度} = \log_2 \left( \frac{S}{C} \right) + \frac{3}{2}$

总结：

( S ) 是初始区域的边长。
( C ) 是任意两个点之间的最小距离，即每个子区域内元素间的最小间距。
最终的四叉树深度大致为：

$\text{深度} = \log_2 \left( \frac{S}{C} \right) + \frac{3}{2}$

四叉树大量使用与碰撞检测上面。

下面是简单实现四叉树的代码：

#include <iostream>
#include <vector>
#include <memory>using namespace std;// 定义一个点（Point）类，表示一个二维空间中的点
class Point
{
public:int x, y;  // 点的 x 和 y 坐标// 构造函数，初始化 x 和 y 坐标Point(int x, int y) : x(x), y(y) {}
};// 定义一个边界（Boundary）类，表示一个矩形区域
class Boundary
{
public:int x, y, width, height;  // 矩形的中心坐标 (x, y)，宽度和高度// 构造函数，初始化矩形的中心坐标、宽度和高度Boundary(int x, int y, int width, int height): x(x), y(y), width(width), height(height) {}// 判断一个点是否在矩形区域内bool contains(const Point& point) const{return point.x >= x - width / 2 && point.x <= x + width / 2 &&point.y >= y - height / 2 && point.y <= y + height / 2;}// 判断一个矩形区域是否与当前矩形区域相交bool intersects(const Boundary& range) const{return !(range.x - range.width / 2 > x + width / 2 ||range.x + range.width / 2 < x - width / 2 ||range.y - range.height / 2 > y + height / 2 ||range.y + range.height / 2 < y - height / 2);}
};// 定义四叉树（QuadTree）类，用于存储二维空间中的点
class QuadTree
{
private:Boundary boundary;  // 当前节点的矩形区域int capacity;  // 当前节点的最大容量（每个节点最多存储多少个点）vector<Point> points;  // 当前节点存储的点unique_ptr<QuadTree> northeast;  // 东北子节点unique_ptr<QuadTree> northwest;  // 西北子节点unique_ptr<QuadTree> southeast;  // 东南子节点unique_ptr<QuadTree> southwest;  // 西南子节点public:// 构造函数，初始化边界和容量QuadTree(const Boundary& boundary, int capacity): boundary(boundary), capacity(capacity) {}// 将当前节点划分为四个子节点void subdivide(){int subWidth = boundary.width / 2;  // 子节点的宽度int subHeight = boundary.height / 2;  // 子节点的高度int x = boundary.x;  // 父节点的 x 坐标int y = boundary.y;  // 父节点的 y 坐标// 创建四个子节点，分别对应东北、西北、东南、西南northeast = make_unique<QuadTree>(Boundary(x + subWidth / 2, y - subHeight / 2, subWidth, subHeight), capacity);northwest = make_unique<QuadTree>(Boundary(x - subWidth / 2, y - subHeight / 2, subWidth, subHeight), capacity);southeast = make_unique<QuadTree>(Boundary(x + subWidth / 2, y + subHeight / 2, subWidth, subHeight), capacity);southwest = make_unique<QuadTree>(Boundary(x - subWidth / 2, y + subHeight / 2, subWidth, subHeight), capacity);}// 插入一个点到四叉树中bool insert(const Point& point){// 如果点超出了当前节点的边界，返回 falseif (!boundary.contains(point)){cout << "Point (" << point.x << ", " << point.y << ") is out of bounds." << endl;return false;}// 如果当前节点的点数未超出容量，则直接插入点if (points.size() < capacity){points.push_back(point);  // 将点加入当前节点的点集合中cout << "Point (" << point.x << ", " << point.y << ") inserted in current node." << endl;return true;}// 如果当前节点已超出容量，进行分割if (northeast == nullptr){cout << "Subdividing node at (" << boundary.x << ", " << boundary.y << ")" << endl;subdivide();  // 划分子节点}// 递归地将点插入到四个子节点中if (northeast->insert(point)) return true;if (northwest->insert(point)) return true;if (southeast->insert(point)) return true;if (southwest->insert(point)) return true;return false;}// 打印当前节点及其所有子节点中的点void printPoints() const{// 打印当前节点存储的点for (const auto& point : points){cout << "(" << point.x << ", " << point.y << ")" << endl;}// 递归地打印四个子节点中的点if (northeast != nullptr) northeast->printPoints();if (northwest != nullptr) northwest->printPoints();if (southeast != nullptr) southeast->printPoints();if (southwest != nullptr) southwest->printPoints();}
};int main()
{// 扩大根节点的边界为 20x20Boundary boundary(0, 0, 20, 20); // 创建一个四叉树，根节点的容量为 4QuadTree qt(boundary, 4);// 插入一些点到四叉树qt.insert(Point(2, 3));qt.insert(Point(3, 5));qt.insert(Point(6, 7));qt.insert(Point(8, 1));qt.insert(Point(1, 1));qt.insert(Point(4, 4));// 打印树中的所有点cout << "Points in the tree:" << endl;qt.printPoints();return 0;
}

八叉树

八叉树原理与四叉树类似，它可以理解为一个下图：
在这里插入图片描述
一个立方体被三个平面分成了八块，它的实现与原理与四叉树类似，在此不过多赘述。

几何数据结构之四叉树与八叉树

四叉树的定义

四叉树深度的计算公式推导

假设：

计算过程：

1. 划分空间：

2. 节点容纳的最小距离：

3. 解出深度：

4. 考虑常数项：

总结：

八叉树

相关文章：