数据结构——八叉树

这篇具有很好参考价值的文章主要介绍了数据结构——八叉树。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

八叉树(Octree)是一种用于表示和管理三维空间的树状数据结构。它将三维空间递归地分割成八个八分体(octant),每个八分体可以继续分割,以实现对三维空间的更精细的划分。八叉树通常用于解决空间搜索和查询问题,例如三维物体碰撞检测、体素化(Voxelization)、地理信息系统等领域。

八叉树,数据结构,数据结构,服务器,数据库文章来源地址https://www.toymoban.com/news/detail-732638.html

#include <iostream>
#include <vector>

// 定义三维点的结构体
struct Point3D {
    float x;
    float y;
    float z;
    Point3D(float _x, float _y, float _z) : x(_x), y(_y), z(_z) {}
};

// 定义八叉树节点
struct OctreeNode {
    Point3D center;
    float size;
    OctreeNode* children[8];

    OctreeNode(Point3D _center, float _size) : center(_center), size(_size) {
        for (int i = 0; i < 8; i++) {
            children[i] = nullptr;
        }
    }
};

class Octree {
private:
    OctreeNode* root;
    float rootSize;

    // 在指定深度下递归插入节点
    OctreeNode* insert(OctreeNode* node, Point3D point, float size) {
        if (node == nullptr) {
            return new OctreeNode(point, size);
        }

        // 确定点位于八分体的哪个子节点
        int index = 0;
        if (point.x >= node->center.x) index |= 1;
        if (point.y >= node->center.y) index |= 2;
        if (point.z >= node->center.z) index |= 4;

        // 递归插入到相应的子节点
        float newSize = node->size / 2.0f;
        node->children[index] = insert(node->children[index], point, newSize);

        return node;
    }

    // 在指定深度下递归搜索节点
    bool search(OctreeNode* node, Point3D point, float size) {
        if (node == nullptr) {
            return false;
        }

        if (node->center.x == point.x && node->center.y == point.y && node->center.z == point.z) {
            return true;
        }

        // 确定点位于八分体的哪个子节点
        int index = 0;
        if (point.x >= node->center.x) index |= 1;
        if (point.y >= node->center.y) index |= 2;
        if (point.z >= node->center.z) index |= 4;

        // 递归搜索相应的子节点
        float newSize = node->size / 2.0f;
        return search(node->children[index], point, newSize);
    }

public:
    Octree(float size) : root(nullptr), rootSize(size) {}

    // 插入一个点
    void insert(Point3D point) {
        root = insert(root, point, rootSize);
    }

    // 搜索一个点是否存在
    bool search(Point3D point) {
        return search(root, point, rootSize);
    }
};

int main() {
    Octree octree(100.0f); // 创建八叉树,定义根节点的大小

    Point3D point1(10.0f, 20.0f, 30.0f);
    Point3D point2(80.0f, 90.0f, 110.0f);

    octree.insert(point1); // 插入点1
    octree.insert(point2); // 插入点2

    Point3D searchPoint(80.0f, 90.0f, 110.0f);
    bool found = octree.search(searchPoint); // 搜索点2
    if (found) {
        std::cout << "Point found in the octree." << std::endl;
    } else {
        std::cout << "Point not found in the octree." << std::endl;
    }

    return 0;
}

到了这里,关于数据结构——八叉树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】二叉树——链式结构

    目录  一、前置声明 二、二叉树的遍历 2.1 前序、中序以及后序遍历 2.2 层序遍历 三、节点个数以及高度 3.1 节点个数 3.2 叶子节点个数 3.3 第k层节点个数 3.4 二叉树的高度/深度 3.5 查找值为x的节点 四、二叉树的创建和销毁 4.1 构建二叉树 4.2 二叉树销毁 4.3 判断二叉树

    2024年02月16日
    浏览(44)
  • 【数据结构】二叉树——顺序结构

    由于每个节点都 只有一个父节点 ,所以我们可通过双亲来表示一棵树。具体方式通过 数组的形式 实现。 根节点的下标为0 按照层序从上到下排序 每层从左向右递增 表示形式: 二维数组 数据的列标为0 ,只需确定行标,即可锁定位置 根节点的父节点下标为 -1 列标为1存父节

    2024年02月02日
    浏览(54)
  • 【数据结构】二叉树链式结构

    🚀write in front🚀 📜所属专栏:初阶数据结构 🛰️博客主页:睿睿的博客主页 🛰️代码仓库:🎉VS2022_C语言仓库 🎡您的点赞、关注、收藏、评论,是对我最大的激励和支持!!! 关注我,关注我,关注我 , 你们将会看到更多的优质内容!!   在之前的二叉树的顺序结

    2024年02月03日
    浏览(39)
  • 【数据结构和算法】--- 二叉树(3)--二叉树链式结构的实现(1)

    在学习二叉树的基本操作前,需先要创建一棵二叉树,然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入,且为了方便后面的介绍,此处手动快速创建一棵简单的二叉树,快速进入二叉树操作学习,等二叉树结构了解的差不多时,我们反过头再来研

    2024年01月25日
    浏览(59)
  • 【数据结构】非线性结构——二叉树

    🧧🧧🧧🧧🧧个人主页🎈🎈🎈🎈🎈 🧧🧧🧧🧧🧧数据结构专栏🎈🎈🎈🎈🎈 🧧🧧🧧🧧🧧【数据结构】受限制的线性表——队列🎈🎈🎈🎈🎈 前面我们都是学的线性结构的数据结构,接下来我们就需要来学习非线性的数据结构,我们先来学第一个非线性的数据结

    2024年03月28日
    浏览(49)
  • 【数据结构】二叉树之链式结构

    🔥 博客主页 : 小羊失眠啦. 🎥 系列专栏 : 《C语言》 《数据结构》 《Linux》 《Cpolar》 ❤️ 感谢大家点赞👍收藏⭐评论✍️ 在学习二叉树各种各样的操作前,我们先来回顾一下二叉树的概念: 二叉树是度不超过2的树,由根结点和左右2个子树组成,每个子树也可以看作

    2024年02月04日
    浏览(43)
  • 【数据结构】二叉树的链式结构

    学习链式二叉树要知道三种遍历方式,便于对二叉树的节点以及左子树和右子树进行操作。 前序遍历:根、左子树、右子树 中序遍历:左子树、根、右子树 后序遍历:左子树、右子树、根 以下图为例: 得到的结果: 前序遍历:1 2 3 4 5 6 中序遍历:3 2 1 5 4 6 后序遍历:3 2

    2024年02月08日
    浏览(52)
  • 数据结构:二叉树的链式结构

    朋友们、伙计们,我们又见面了,本期来给大家解读一下链式二叉树的相关知识点,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成! 数据结构与算法专栏 :数据结构与算法 个  人  主  页 :stackY、 C 语 言 专 栏 :C语言:从入门到精通 目录 前言

    2024年02月07日
    浏览(56)
  • 数据结构——二叉树的链式结构

      个人主页 : 日刷百题 系列专栏 : 〖C语言小游戏〗〖Linux〗〖数据结构〗  〖C语言〗 🌎 欢迎各位 → 点赞 👍+ 收藏 ⭐️+ 留言 📝  ​ 这里我们使用先序遍历的思想来创建二叉树,这里的内容对于刚接触二叉树的朋友可能有些难理解,不妨先看完下面的二叉树各种遍历

    2024年02月05日
    浏览(43)
  • 【数据结构】二叉树 链式结构的相关问题

     本篇文章来详细介绍一下二叉树链式结构经常使用的相关函数,以及相关的的OJ题。 目录 1.前置说明 2.二叉树的遍历 2.1 前序、中序以及后序遍历 2.2 层次遍历 3.节点个数相关函数实现 3.1 二叉树节点个数 3.2 二叉树叶子节点个数 3.3 二叉树第k层节点个数 3.4 在二叉树中查找值

    2024年02月14日
    浏览(57)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包