叉树Octree原理及简单实现（C++版）

叉树Octree是一种用于空间分割的数据结构，常用于计算机图形学、物理模拟等领域。其原理是将空间递归地分割成八个子空间，每个子空间又可以继续递归地分割成八个子空间，直到最小空间达到一定的大小。

C++中可以通过定义节点类和递归函数来实现叉树Octree。以下是一个简单的实现：

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

class Node {
public:
    double x, y, z; // 三维坐标
    double size; // 此节点所代表的空间大小
    vector<Node*> children; // 子节点指针数组
    Node(double x_, double y_, double z_, double size_) {
        x = x_;
        y = y_;
        z = z_;
        size = size_;
        children.resize(8, nullptr);
    }
};

void insert(Node* node, double x, double y, double z, double size) {
    if (size <= node->size) { // 如果此节点的大小大于等于当前空间大小，则将此空间添加到此节点的子节点中
        if (node->children[0] == nullptr) { // 如果当前节点还没有子节点，则创建
            node->children[0] = new Node(node->x - node->size / 4, node->y - node->size / 4, node->z - node->size / 4, node->size / 2);
            node->children[1] = new Node(node->x + node->size / 4, node->y - node->size / 4, node->z - node->size / 4, node->size / 2);
            node->children[2] = new Node(node->x - node->size / 4, node->y + node->size / 4, node->z - node->size / 4, node->size / 2);
            node->children[3] = new Node(node->x + node->size / 4, node->y + node->size / 4, node->z - node->size / 4, node->size / 2);
            node->children[4] = new Node(node->x - node->size / 4, node->y - node->size / 4, node->z + node->size / 4, node->size / 2);
            node->children[5] = new Node(node->x + node->size / 4, node->y - node->size / 4, node->z + node->size / 4, node->size / 2);
            node->children[6] = new Node(node->x - node->size / 4, node->y + node->size / 4, node->z + node->size / 4, node->size / 2);
            node->children[7] = new Node(node->x + node->size / 4, node->y + node->size / 4, node->z + node->size / 4, node->size / 2);
        }
        for (int i = 0; i < 8; i++) { // 递归插入
            insert(node->children[i], x, y, z, size / 2);
        }
    }
}

int main() {
    Node* root = new Node(0, 0, 0, 1); // 创建根节点
    insert(root, 0.5, 0.5, 0.5, 0.1); // 插入一个大小为0.1的空间，其坐标为(0.5,0.5,0.5)
    return 0;
}

在这个简单的实现中，我们定义了一个节点类Node，包含了三维坐标和空间大小等属性，同时还有一个指向子节点的数组。我们通过递归函数insert来递归地插入新的空间，如果当前节点的大小大于等于要插入的空间大小，则将此空间插入到当前节点的子节点中，否则递归进入子节点。在main函数中，我们创建了一个根节点，并插入了一个大小为0.1的空间。

需要注意的是，此实现仅是一个简单的示例，实际应用中可能需要更复杂的节点类和插入函数。