动态增删kdtree(ikdtree)主要思路

2023-10-27 02:15

本文主要是介绍动态增删kdtree(ikdtree)主要思路,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

ikdtree本质上也是一种kdtree,基本的构造方法和kdtree是一样的,本文主要记录两者不一样的地方,以港大MaRS实验室最新开源的增量式 kd-tree(https://github.com/hku-mars/ikd-Tree)里面的一些代码作为示范。

以下是ikdtree结构体包括的基本变量,在港大开源的代码中结构变量是远远多于这里的,主要是为了利用其他方面(例如多线程)对树进一步优化加速。

{

     // 寻常kdtree也有的:
        uint8_t division_axis;  //以哪一个轴(x,y,z)作为的切分平面法线

        KD_TREE_NODE *left_son_ptr = nullptr; //左孩子节点
        KD_TREE_NODE *right_son_ptr = nullptr;//右孩子节点

        float node_range_x[2], node_range_y[2], node_range_z[2];   //AABB包围盒

 

    // 以下主要是用于增删的变量:

       PointType point; //点坐标
        int TreeSize = 1; //包括它本身和它左右孩子的总数量
        int invalid_point_num = 0; //包括自己在内已经被标记删除点的数量
        bool point_deleted = false; //该节点是否被标记删除
        KD_TREE_NODE *father_ptr = nullptr; //它的父亲节点

}

首先 说一下这里的点坐标,虽然有些kdtree的写法上也在内部节点上保存了点坐标,但更通常的做法是仅在叶子节点上有存储,而在ikdtree中,这个变量内部节点则必须存在,这在动态点插入的时候有很大的作用。

ikdtree节点的删除操作采用的是一种延迟删除操作的做法,这种做法其实并不陌生,c++ 标准库中remove就是这种策略,即仅对节点做删除标记,而不立即更新删除树,在结构体中point_deleted就是起到这个作用,标记完后,AABB盒是要立即更新的,但是要排除已经标记删除的数据。

ikdtree的插入操作是直接将节点插入在树的末尾,当然这也是有规则的,在港大开源的代码中,插入节点满足大于左节点(这里点坐标就有了用处),不满足则直接遍历右节点从而放在右节点末端,全部放在右节点末端是为了人为破坏树的平衡性,这是后面判断树更新的一个重要依据。同删除一样,插入完毕后,AABB盒要立即更新。

6521c3261f704ad691ae02e878afe354.jpeg

 上述做完之后,可以认为已经动态改变了,但是也可以看见,此时的删除和插入操作其实已经破坏了kdtree的特性,例如删除操作破坏了平衡特性,增加了很多无效的节点,增加了遍历,插入操作则破坏了树平衡性和有序性两个特性(这里注明一下,有序性的破坏并不会影响结果,这里让我迷糊了很久,因为寻找最近点即使有序的二叉树仅通过包围盒也是无法排除另一个孩子树的)。在破坏较小时,相比于重新建立树的效率相比,些许的效率损失可以接受,但是当变化太大后,这个tree结构也就几乎没有了加速的效果。因此在ikdtree中,在认为已经破坏过大时,必须更新树结构。ikdtree中提出了两个依据来判断是否树已经破坏过大:

一是被标记删除的个数占整个节点数量的比例,港大源代码中默认是要小于0.5,二是不平衡性,即是单个孩子节点数量占整个节点数量的比例,港大源代码中默认为在0.3~0.7之间为合理的。

当任何一个依据不满足时,树就要立即更新。

e8cb5be632954f699a91c0baf7549908.jpeg

在树更新的过程中,也不是整个树都要更新,仅仅只是不满足两个依据的子树进行自我更新,进一步优化了效率,示例如下图。这里结构体中的父亲节点就有了可用之地。

7726d951aeef47a38fbd00dbeb8ad777.png

d9ac3feff423429e97572874f5641eb1.jpeg 

 

这篇关于动态增删kdtree(ikdtree)主要思路的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/285885

相关文章

MyBatis编写嵌套子查询的动态SQL实践详解

《MyBatis编写嵌套子查询的动态SQL实践详解》在Java生态中,MyBatis作为一款优秀的ORM框架,广泛应用于数据库操作,本文将深入探讨如何在MyBatis中编写嵌套子查询的动态SQL,并结... 目录一、Myhttp://www.chinasem.cnBATis动态SQL的核心优势1. 灵活性与可

Mybatis嵌套子查询动态SQL编写实践

《Mybatis嵌套子查询动态SQL编写实践》:本文主要介绍Mybatis嵌套子查询动态SQL编写方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录前言一、实体类1、主类2、子类二、Mapper三、XML四、详解总结前言MyBATis的xml文件编写动态SQL

SpringBoot实现Kafka动态反序列化的完整代码

《SpringBoot实现Kafka动态反序列化的完整代码》在分布式系统中,Kafka作为高吞吐量的消息队列,常常需要处理来自不同主题(Topic)的异构数据,不同的业务场景可能要求对同一消费者组内的... 目录引言一、问题背景1.1 动态反序列化的需求1.2 常见问题二、动态反序列化的核心方案2.1 ht

MybatisX快速生成增删改查的方法示例

《MybatisX快速生成增删改查的方法示例》MybatisX是基于IDEA的MyBatis/MyBatis-Plus开发插件,本文主要介绍了MybatisX快速生成增删改查的方法示例,文中通过示例代... 目录1 安装2 基本功能2.1 XML跳转2.2 代码生成2.2.1 生成.xml中的sql语句头2

golang实现动态路由的项目实践

《golang实现动态路由的项目实践》本文主要介绍了golang实现动态路由项目实践,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习... 目录一、动态路由1.结构体(数据库的定义)2.预加载preload3.添加关联的方法一、动态路由1

WinForms中主要控件的详细使用教程

《WinForms中主要控件的详细使用教程》WinForms(WindowsForms)是Microsoft提供的用于构建Windows桌面应用程序的框架,它提供了丰富的控件集合,可以满足各种UI设计... 目录一、基础控件1. Button (按钮)2. Label (标签)3. TextBox (文本框

Python Selenium动态渲染页面和抓取的使用指南

《PythonSelenium动态渲染页面和抓取的使用指南》在Web数据采集领域,动态渲染页面已成为现代网站的主流形式,本文将从技术原理,环境配置,核心功能系统讲解Selenium在Python动态... 目录一、Selenium技术架构解析二、环境搭建与基础配置1. 组件安装2. 驱动配置3. 基础操作模

Python MCPInspector调试思路详解

《PythonMCPInspector调试思路详解》:本文主要介绍PythonMCPInspector调试思路详解,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋... 目录python-MCPInspector调试1-核心知识点2-思路整理1-核心思路2-核心代码3-参考网址

慢sql提前分析预警和动态sql替换-Mybatis-SQL

《慢sql提前分析预警和动态sql替换-Mybatis-SQL》为防止慢SQL问题而开发的MyBatis组件,该组件能够在开发、测试阶段自动分析SQL语句,并在出现慢SQL问题时通过Ducc配置实现动... 目录背景解决思路开源方案调研设计方案详细设计使用方法1、引入依赖jar包2、配置组件XML3、核心配

springboot使用Scheduling实现动态增删启停定时任务教程

《springboot使用Scheduling实现动态增删启停定时任务教程》:本文主要介绍springboot使用Scheduling实现动态增删启停定时任务教程,具有很好的参考价值,希望对大家有... 目录1、配置定时任务需要的线程池2、创建ScheduledFuture的包装类3、注册定时任务,增加、删