Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0301· openaiHugging Face Suzhen/CodeChat

给我一个基于vector3的点对象的八叉树数据结构,需要可以快速查询距离相近的点

  1. User

    给我一个基于vector3的点对象的八叉树数据结构,需要可以快速查询距离相近的点

  2. Assistant

    以下是一个基于Vector3的点对象的八叉树数据结构的示例代码:

    struct Point3D {
        Vector3 position;
    
        Point3D() {}
    
        Point3D(Vector3 pos) {
            position = pos;
        }
    };
    
    struct OctreeNode {
        Vector3 center;
        float radius;
        vector<Point3D> points;
        OctreeNode* children[8];
    
        OctreeNode(Vector3 c, float r) {
            center = c;
            radius = r;
            for (int i = 0; i < 8; i++) {
                children[i] = NULL;
            }
        }
    
        ~OctreeNode() {
            for (OctreeNode* child : children) {
                if (child != NULL) {
                    delete child;
                }
            }
        }
    
        bool IsLeafNode() {
            for (OctreeNode* child : children) {
                if (child != NULL) {
                    return false;
                }
            }
            return true;
        }
    
        void Subdivide() {
            float halfRadius = radius / 2.0f;
            Vector3 childCenters[8];
            childCenters[0] = center + Vector3(-halfRadius, halfRadius, -halfRadius);
            childCenters[1] = center + Vector3(halfRadius, halfRadius, -halfRadius);
            childCenters[2] = center + Vector3(-halfRadius, halfRadius, halfRadius);
            childCenters[3] = center + Vector3(halfRadius, halfRadius, halfRadius);
            childCenters[4] = center + Vector3(-halfRadius, -halfRadius, -halfRadius);
            childCenters[5] = center + Vector3(halfRadius, -halfRadius, -halfRadius);
            childCenters[6] = center + Vector3(-halfRadius, -halfRadius, halfRadius);
            childCenters[7] = center + Vector3(halfRadius, -halfRadius, halfRadius);
    
            for (int i = 0; i < 8; i++) {
                children[i] = new OctreeNode(childCenters[i], halfRadius);
            }
    
            for (Point3D point : points) {
                int octantIndex = GetOctantIndex(point.position);
                children[octantIndex]->AddPoint(point);
            }
    
            points.clear();
        }
    
        void AddPoint(Point3D point) {
            if (IsLeafNode()) {
                points.push_back(point);
                if (points.size() > 8) {
                    Subdivide();
                }
            }
            else {
                int octantIndex = GetOctantIndex(point.position);
                children[octantIndex]->AddPoint(point);
            }
        }
    
        int GetOctantIndex(Vector3 pos) {
            int oct = 0;
            if (pos.x > center.x) {
                oct |= 4;
            }
            if (pos.y > center.y) {
                oct |= 2;
            }
            if (pos.z > center.z) {
                oct |= 1;
            }
            return oct;
        }
    
        vector<Point3D> GetPointsNearby(Vector3 pos, float radius) {
            vector<Point3D> nearbyPoints;
            float distance = (pos - center).Magnitude();
            if (distance < radius + this->radius) {
                for (Point3D point : points) {
                    float distanceToPoint = (pos - point.position).Magnitude();
                    if (distanceToPoint < radius) {
                        nearbyPoints.push_back(point);
                    }
                }
                if (!IsLeafNode()) {
                    for (OctreeNode* child : children) {
                        vector<Point3D> childPoints = child->GetPointsNearby(pos, radius);
                        nearbyPoints.insert(nearbyPoints.end(), childPoints.begin(), childPoints.end());
                    }
                }
            }
            return nearbyPoints;
        }
    };
    
    class Octree {
    private:
        OctreeNode* root;
    
    public:
        Octree(Vector3 center, float radius) {
            root = new OctreeNode(center, radius);
        }
    
        ~Octree() {
            delete root;
        }
    
        void AddPoint(Point3D point) {
            root->AddPoint(point);
        }
    
        vector<Point3D> GetPointsNearby(Vector3 pos, float radius) {
            return root->GetPointsNearby(pos, radius);
        }
    };
    

    在该八叉树数据结构中,每个节点代表一个立方体区域,其中心点为该节点的中心点,半径为该节点代表的立方体的半边长。每个节点最多保存8个点,如果节点内的点超过8个,则对该节点进行子节点的细分,将每个点分配到对应的子节点中。

    该八叉树支持添加点和查询距离相近的点的操作。GetPointsNearby方法返回与指定点在指定半径内距离小于等于半径的点集合。在查询时,先判断当前节点是否与查询点有交集(即当前节点的中心点与查询点的距离小于等于半径和当前节点所代表的立方体半边长之和),如果有,则将当前节点内所有距离小于等于半径的点加入结果集。如果该节点不是叶子节点,则递归调用其子节点进行查询,并将查询结果合并到结果集中。

    使用该八叉树数据结构时,可以将需要进行查询的点添加到该数据结构中,然后使用GetPointsNearby方法查询,并处理返回的结果集。

  3. User

    给我一个c++加法重载的样例

  4. Assistant

    以下是一个C++中加法重载的样例:

    #include <iostream>
    
    using namespace std;
    
    class Complex {
    private:
        double real;
        double imag;
    
    public:
        Complex(double r = 0, double i = 0) {
            real = r;
            imag = i;
        }
    
        Complex operator + (const Complex& c) const {
            Complex result;
            result.real = real + c.real;
            result.imag = imag + c.imag;
            return result;
        }
    
        void Print() const {
            cout << "(" << real << ", " << imag << ")" << endl;
        }
    };
    
    int main() {
        Complex c1(1, 2);
        Complex c2(3, 4);
        Complex c3 = c1 + c2;
        c3.Print();
        return 0;
    }
    

    在上面的样例中,我们定义了一个名为Complex的类,其代表一个复数类型,包含实部和虚部两个成员变量。我们需要对Complex类进行加法重载,以实现复数的加法操作。

    我们定义了一个名为operator+的成员函数,该函数的参数为另一个Complex类型的引用,返回一个新的Complex类型,表示两个复数的和。在该函数中,我们将实部和虚部分别相加,并将结果储存在一个新的Complex对象中返回。

    在主函数中,我们创建了三个Complex对象,分别初始化为(1, 2)、(3, 4)、(0, 0),然后将前两个复数相加,并将结果储存在第三个对象中。最后,我们调用了Print函数打印第三个复数对象的值。

  5. User

    给我一个可以快速删除或者添加的八叉树数据结构c++的

  6. Assistant

    以下是一个基于C++的可以快速删除和添加的八叉树数据结构的示例代码:

    #include <vector>
    #include <memory>
    
    class Vector3 {
    public:
        double x, y, z;
    
        Vector3(double x, double y, double z)
            : x(x), y(y), z(z) {}
    
        Vector3 operator + (const Vector3& v) const {
            return Vector3(x + v.x, y + v.y, z + v.z);
        }
    
        Vector3 operator - (const Vector3& v) const {
            return Vector3(x - v.x, y - v.y, z - v.z);
        }
    
        double Magnitude() const {
            return sqrt(x * x + y * y + z * z);
        }
    };
    
    class OctreeNode {
    public:
        Vector3 center;
        double radius;
        std::vector<Vector3> points;
    
    private:
        std::unique_ptr<OctreeNode> children[8];
    
    public:
        OctreeNode(const Vector3& center, double radius) {
            this->center = center;
            this->radius = radius;
        }
    
        void AddPoint(const Vector3& point) {
            // If the point is outside of our boundaries, don't add it.
            if ((point - center).Magnitude() > radius) {
                return;
            }
    
            // If we don't have any children, add the point to our list
            if (IsLeafNode()) {
                points.push_back(point);
    
                // If we have too many points, subdivide
                if (points.size() > 8) {
                    Subdivide();
                }
            } 
            else {
                int childIndex = GetChildIndex(point);
                children[childIndex]->AddPoint(point);
            }
        }
    
        void RemovePoint(const Vector3& point) {
            // If the point is outside of our boundaries, don't remove it.
            if ((point - center).Magnitude() > radius) {
                return;
            }
    
            // If we don't have any children, remove the point from our list
            if (IsLeafNode()) {
                for (auto it = points.begin(); it != points.end(); ++it) {
                    if (*it == point) {
                        points.erase(it);
                        break;
                    }
                }
            } 
            else {
                int childIndex = GetChildIndex(point);
                children[childIndex]->RemovePoint(point);
            }
        }
    
        void GetPointsNearby(const Vector3& point, double radius, std::vector<Vector3>& pointsInRange) const {
            // If the point is outside of our boundaries, don't look for nearby points.
            if ((point - center).Magnitude() > radius + this->radius) {
                return;
            }
    
            // Check all points in this node for the specified radius
            for (const auto& p : points) {
                if ((p - point).Magnitude() <= radius) {
                    pointsInRange.push_back(p);
                }
            }
    
            // If we're not a leaf node, recurse
            if (!IsLeafNode()) {
                for (const auto& child : children) {
                    child->GetPointsNearby(point, radius, pointsInRange);
                }
            }
        }
    
    private:
        void Subdivide() {
            double halfRadius = radius / 2.0;
            Vector3 childCenter = center;
    
            // Create children nodes
            for (int i = 0; i < 8; i++) {
                int x = i % 2 ? 1 : -1;
                int y = i > 3 ? 1 : -1;
                int z = (i == 1 || i == 3 || i == 5 || i == 7) ? 1 : -1;
                Vector3 offset(x * halfRadius, y * halfRadius, z * halfRadius);
                childCenter = center + offset;
                children[i] = std::make_unique<OctreeNode>(childCenter, halfRadius);
            }
    
            // Move points into children nodes
            for (const auto& p : points) {
                int childIndex = GetChildIndex(p);
                children[childIndex]->AddPoint(p);
            }
    
            points.clear();
        }
    
        int GetChildIndex(const Vector3& point) const {
            int index = 0;
            if (point.z > center.z) index |= 1;
            if (point.y > center.y) index |= 2;
            if (point.x > center.x) index |= 4;
            return index;
        }
    
        bool IsLeafNode() const {
            return children[0] == nullptr;
        }
    };
    
    class Octree {
    public:
        Octree(const Vector3& center, double radius)
            : root(std::make_unique<OctreeNode>(center, radius)) {}
    
        void AddPoint(const Vector3& point) {
            root->AddPoint(point);
        }
    
        void RemovePoint(const Vector3& point) {
            root->RemovePoint(point);
        }
    
        std::vector<Vector3> GetPointsNearby(const Vector3& point, double radius) const {
            std::vector<Vector3> pointsInRange;
            root->GetPointsNearby(point, radius, pointsInRange);
            return pointsInRange;
        }
    
    private:
        std::unique_ptr<OctreeNode> root;
    };
    

    上述代码中,我们定义了一个 OctreeNode 类,表示八叉树的节点;和一个 Octree 类用于管理树的顶层节点。

    OctreeNode 中使用了智能指针成员数组来存储子节点,并不断对节点进行细分。AddPoint 特化方法可将点添加到八叉树中。RemovePoint 特化方法可将点从八叉树中删除。GetPointsNearby 特化方法可查找指定半径内的相邻点。

    在 Octree 中,我们使用 AddPoint 和 RemovePoint 特化方法可以将点直接加入或移除树中;同时,通过调用 GetPointsNearby 方法,可以返回树中指定点附近指定半径内的所有相邻点。

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.