使用c++写出八叉树数据结构
时间: 2023-11-26 09:43:40 浏览: 62
八叉树是一种树形数据结构,每个节点最多有八个子节点。它通常用于三维空间的划分和搜索,可以有效地提高搜索效率。以下是使用C++实现八叉树的代码:
```cpp
struct Point {
double x, y, z;
};
struct OctreeNode {
Point center;
double length;
vector<Point> points;
OctreeNode* children[8];
};
class Octree {
public:
Octree(Point center, double length);
void insert(Point p);
vector<Point> search(Point center, double radius);
private:
OctreeNode* root;
void insertHelper(OctreeNode* node, Point p);
void searchHelper(OctreeNode* node, Point center, double radius, vector<Point>& result);
};
Octree::Octree(Point center, double length) {
root = new OctreeNode;
root->center = center;
root->length = length;
for (int i = 0; i < 8; i++) {
root->children[i] = nullptr;
}
}
void Octree::insert(Point p) {
insertHelper(root, p);
}
void Octree::insertHelper(OctreeNode* node, Point p) {
if (node->children[0] == nullptr) {
node->points.push_back(p);
return;
}
int index = 0;
if (p.x >= node->center.x) index |= 4;
if (p.y >= node->center.y) index |= 2;
if (p.z >= node->center.z) index |= 1;
if (node->children[index] == nullptr) {
double len = node->length / 2;
Point center;
center.x = node->center.x + (index & 4 ? len : -len);
center.y = node->center.y + (index & 2 ? len : -len);
center.z = node->center.z + (index & 1 ? len : -len);
node->children[index] = new OctreeNode;
node->children[index]->center = center;
node->children[index]->length = len;
for (int i = 0; i < 8; i++) {
node->children[index]->children[i] = nullptr;
}
}
insertHelper(node->children[index], p);
}
vector<Point> Octree::search(Point center, double radius) {
vector<Point> result;
searchHelper(root, center, radius, result);
return result;
}
void Octree::searchHelper(OctreeNode* node, Point center, double radius, vector<Point>& result) {
if (node == nullptr) return;
double dx = abs(node->center.x - center.x);
double dy = abs(node->center.y - center.y);
double dz = abs(node->center.z - center.z);
if (dx > radius + node->length || dy > radius + node->length || dz > radius + node->length) {
return;
}
if (dx <= radius && dy <= radius && dz <= radius) {
for (auto p : node->points) {
double dist = sqrt(pow(p.x - center.x, 2) + pow(p.y - center.y, 2) + pow(p.z - center.z, 2));
if (dist <= radius) {
result.push_back(p);
}
}
}
for (int i = 0; i < 8; i++) {
searchHelper(node->children[i], center, radius, result);
}
}
```