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

- 四叉树的定义
- 四叉树深度的计算公式推导
- - 假设：
  - 计算过程：
  - - 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)
    {
        // 如果点超出了当前节点的边界，返回 false
        if (!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()
{
    // 扩大根节点的边界为 20x20
    Boundary boundary(0, 0, 20, 20); 

    // 创建一个四叉树，根节点的容量为 4
    QuadTree 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;
}