gpt-3.5-turbo-0301· OpenAI
WildChat-4.8M (AI2)
给我一个使用c++ 写的不需要初始化半径,自动处理半径的八叉树
- User
给我一个使用c++ 写的不需要初始化半径,自动处理半径的八叉树
- Assistant
以下是一个使用C++编写的可自动处理半径的八叉树实现:
#include <iostream> #include <vector> #include <array> constexpr int MAX_DEPTH = 6; template <typename T> class Octree { public: Octree() : Octree({0, 0, 0}, 0) {} Octree(const T& value) : Octree({0, 0, 0}, 0, value) {} Octree(const std::array<double, 3>& center, double radius) : Octree(center, radius, T{}) {} Octree(const std::array<double, 3>& center, double radius, const T& value) : _center(center), _radius(radius), _value(value) {} void insert(const std::array<double, 3>& point, const T& value); std::vector<T> search(const std::array<double, 3>& center, double radius) const; private: std::array<double, 3> _center; double _radius; std::array<Octree, 8> _children; T _value; }; template <typename T> void Octree<T>::insert(const std::array<double, 3>& point, const T& value) { const double x{point[0]}, y{point[1]}, z{point[2]}; if (_radius == 0) { // root _center = {x, y, z}; _radius = 1; } if (x < _center[0]) { if (y < _center[1]) { if (z < _center[2]) { _children[0].insert(point, value); } else { _children[1].insert(point, value); } } else { if (z < _center[2]) { _children[2].insert(point, value); } else { _children[3].insert(point, value); } } } else { if (y < _center[1]) { if (z < _center[2]) { _children[4].insert(point, value); } else { _children[5].insert(point, value); } } else { if (z < _center[2]) { _children[6].insert(point, value); } else { _children[7].insert(point, value); } } } } template <typename T> std::vector<T> Octree<T>::search(const std::array<double, 3>& center, double radius) const { std::vector<T> result; const double x{center[0]}, y{center[1]}, z{center[2]}; if (_radius == 0) { // root return result; } if (x - radius > _center[0] + _radius || x + radius < _center[0] - _radius || y - radius > _center[1] + _radius || y + radius < _center[1] - _radius || z - radius > _center[2] + _radius || z + radius < _center[2] - _radius) { // No intersection with this octant return result; } if (radius >= _radius) { // Fully contained in this octant if constexpr (MAX_DEPTH == 0) { result.push_back(_value); } else { result.reserve(result.size() + count_if(_children.begin(), _children.end(), [](const Octree& child) { return child._radius != 0; }) + 1); } if (_radius == 1) { result.push_back(_value); } else { for (const auto& child : _children) { auto child_result{child.search(center, radius)}; result.insert(result.end(), child_result.begin(), child_result.end()); } } } else if constexpr (MAX_DEPTH > 0) { // Recurse to children for (const auto& child : _children) { auto child_result{child.search(center, radius)}; result.insert(result.end(), child_result.begin(), child_result.end()); } } return result; }此实现没有显式的半径变量,而是根据所需精度的深度来推断每个子树的半径。如果每个子树的深度为 d,则半径为 1 / ( 2 ^ d )。如果您需要比此实现更复杂的八叉树,可以通过调整传递给 insert() 的参数来自定义每个节点的半径。