Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0301· OpenAIAi2 WildChat-4.8M (AI2)

给我一个使用c++ 写的不需要初始化半径,自动处理半径的八叉树

  1. User

    给我一个使用c++ 写的不需要初始化半径,自动处理半径的八叉树

  2. 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() 的参数来自定义每个节点的半径。