详解C语言实现空间索引四叉树

前言

作为程序员,应该都对二叉树都不陌生,我们都知道二叉树的变体二叉查找树,非常适合用来进行对一维数列的存储和查找,可以达到 O(logn) 的效率;我们在用二叉查找树进行插入数据时,根据一个数据的值和树结点值的对比,选择二叉树的两个叉之一向下,直到叶子结点,查找时使用二分法也可以迅速找到需要的数据。

但二叉树只支持一维数据,如一个标量数值,对地图上的位置点这种有xy两个方向上的信息却无能为力,那么是否有一种树能够支持二维数据的快速查询呢?

四叉树

介绍

四元树又称四叉树是一种树状数据结构,在每一个节点上会有四个子区块。四元树常应用于二维空间数据的分析与分类。它将数据区分成为四个象限。

今天要介绍的四叉树可以认为是二叉查找树的高维变体,它适合对有二维属性的数据进行存储和查询,当然四叉树存储的也不一定是二维数据,而是有着二维属性的数据,如有着 x,y 信息的点,用它还可以用来存储线和面数据。它有四个,在数据插入时,我们通过其二维属性(一般是 x,y)选择四个叉之一继续向下,直至叶子结点,同样使用“四分法”来迅速查找数据。四叉树的一般图形结构如下:

聪明的小伙伴一定想到了适合存储和查询三维数据的八叉树,它们原理是一致的,不过我们暂不讨论。

分类

四叉树常见的应用有图像处理、空间数据索引、2D中的快速碰撞检测、稀疏数据等,今天我们很纯粹地只介绍它在空间索引方面的应用。

根据其存储内容,四叉树可以分为点四叉树、边四叉树和块四叉树,今天我们实现的是点四叉树。

根据其结构,四叉树分为满四叉树和非满四叉树。

对于满四叉树,每个节点都有四个子结点,它有着固定的深度,数据全都存在最底层的子结点中,进行数据插入时不需要分裂。

满四叉树在确定好深度后,进行插入操作很快,可是如果用它来存储下图所示数据,我们会发现,四叉树的好多叉都是空的,当然它们会造成内存空间的大量浪费。

非满四叉树解决了此问题,它为每个结点添加一个“容量”的属性,在四叉树初始化时只有一个根结点,在插入数据时,如果一个结点内的数据量大于了结点“容量”,再将结点进行分裂。如此,可以保证每个结点内都存储着数据,避免了内存空间的浪费。

在查询时,只有找到了位置对应的结点,那么结点下的所有点都会是此位置的附近点,更小的“容量”意味着每个结点内点越少,也就意味着查询的精度会越高。

代码实现

首先是数据结构的定义:

树结点:

struct QuadTreeNode {
    int depth; // 结点深度
    int is_leaf; // 是否是叶子结点
    struct Region region; // 区域范围
    struct QuadTreeNode *LU; // 左上子结点指针
    struct QuadTreeNode *LB; // 左下子结点指针
    struct QuadTreeNode *RU; // 右上子结点指针
    struct QuadTreeNode *RB; // 右下子结点指针
    int ele_num; // 位置点数
    struct ElePoint *ele_list[MAX_ELE_NUM]; // 位置点列表
};

为了加快插入和查询速度,数据结构设计稍微冗余了一些;

四叉树位置点的插入流程如下图所示:

结点的分裂是重点,这里介绍一下:

void splitNode(struct QuadTreeNode *node) {
    // 获取xy方向上的中间点,用来初始化子结点的范围
    double mid_vertical = (node->region.up + node->region.bottom) / 2;
    double mid_horizontal = (node->region.left + node->region.right) / 2;

    node->is_leaf = 0; // 将是否为叶子结点置为否
    // 填充四个子结点
    node->RU = createChildNode(node, mid_vertical, node->region.up, mid_horizontal, node->region.right);
    node->LU = createChildNode(node, mid_vertical, node->region.up, node->region.left, mid_horizontal);
    node->RB = createChildNode(node, node->region.bottom, mid_vertical, mid_horizontal, node->region.right);
    node->LB = createChildNode(node, node->region.bottom, mid_vertical, node->region.left, mid_horizontal);

    // 遍历结点下的位置点,将其插入到子结点中
    for (int i = 0; i < node->ele_num; i++) {
        insertEle(node, *node->ele_list[i]);
        free(node->ele_list[i]);
        node->ele_num--;
    }
}

问题和优化

边界点问题

四叉树还是面临着边界点问题,每个结点内的点必然是相邻的,但相邻的点越不一定在同一个结点内,如下图,A点和B点相邻的很近,如果A点是我们查找的目标点,那么仅仅取出A点所在结点内的所有位置点是不够的,我们还需要查找它的周边结点。

这里我们要介绍四叉树的另一个特性。

字典树

字典树,又称前缀树或trie树,是一种有序树,用于保存关联数组,其中的键通常是字符串。与二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。

我们可以类比字典的特性:我们在字典里通过拼音查找晃(huang)这个字的时候,我们会发现它的附近都是读音为huang的,可能是声调有区别,再往前翻,我们会看到读音前缀为huan的字,再往前,是读音前缀为hua的字... 取它们的读音前缀分别为 h qu hua huan huang。我们在查找时,根据 abc...xyz 的顺序找到h前缀的部分,再根据 ha he hu 找到 hu 前缀的部分...最后找到 huang,我们会发现,越往后其读音前缀越长,查找也越精确,这种类似于字典的树结构就是字典树,也是前缀树。

四叉树也有此特性,我们给每一个子结点都编号,那么每个子结点会继承父结点的编号为前缀,并在此基础上有相对其兄弟结点的独特编号。

与 GeoHash 的相似之处

如果我们给右上、左上、左下、右下四个子结点分别编号为00 01 10 11,那么生成的四叉树就会像:

我们在查找到目标结点时,根据其编码获取到其周边八个结点的编码,再获取各个周边结点内的位置点。

嗯,这种通过编码来确定周边格子的方式确实跟 GeoHash 是相同的,但不要混淆了他们查找原理上的截然不同:

  • GeoHash 本质上是通过格子编码将二维信息用一维来表示,其查找原理从根本上来说是二叉树(B树),在查找时会根据格子编码选择两个方向之一继续精确,查询效率准确来说是 log2N;
  • 四叉树保留了其二维查找的特性,其查找会根据其 x,y 选择四个方向之一继续查找,忽略方向选择时的计算,其查询效率应该是 log4N;

我们可以使用此方法来继续优化四叉树,给结点添加一个“编号”属性即可,由于时(bo)间(zhu)关(fan)系(lan),这里不再实现了。

小结

由于 C 语言的高效率,由它实现的四叉树效率极高。 进行十万数据的插入和一次查询总操作为 7毫秒。在数据量更大的插入时,因为要进行结点的多次分裂,效率会有所下降,进行了8百万数据的测试插入需要两分钟多一些(16年的 mac pro),至于查询,都是一些内存寻址操作,时间可以忽略不计了。 更大量级的测试就不跑了,跑的时候散热风扇速转系统温度迅速上升

不过这么高的效率是因为这些都是内存操作,真正的数据库中数据肯定是要落地的,那时候更多的就是些磁盘和 IO 操作了,效率也会有所下降,但最终的效率和结点数据的扩展能力,与 GeoHash 相比,还是四叉树更好一些。

以上就是详解C语言实现空间索引四叉树的详细内容,更多关于C语言实现空间索引四叉树的资料请关注我们其它相关文章!

(0)

相关推荐

  • C语言实现抢红包算法

    本文实例为大家分享了C语言实现抢红包的具体代码,供大家参考,具体内容如下 1.算法背景: 大家知道,微信拼手气红包和普通红包两种.普通红包每个人抢到的金额是固定的(总额的平均数),拼手气红包是随机金额(每个人抢到的是随机的,差别可能非常大,有的人抢到的是1分,有的抢到的可能是几元.十几元.几十元),目前的抢红包算法只能输入两个参数,即总金额.总人数. 2.算法要求: 现要求同学们设计一个改进的抢红包算法,可以设定总金额(total).总人数(num).抢到的最低金额(min)和最高金额(max)

  • C++实现四叉树效果(附源码下载)

    什么是四叉树? 如图,设想, 红框表示地图,星星表示单位,黄框表现范围, 要处理地图中范围内的单位,最直接的做法是筛选所有单位. 通过上图可以看到一个显而易见的问题,大部分单位都不需要被处理. 如果把地图分成块,只筛选范围覆盖的块中的单位,这样就可以减少很多不必要的筛选. 四叉树可以有效解决这个问题. 树的每一层都把地图划分四块,根据地图尺寸来决定树的层数,层数越大划分越细. 当需要对某一范围的单位筛选时,只需要定位到与范围相交的树区域,再对其区域内的对象筛选即可. 四叉树的实现 #pragma

  • C++实现PatchMatch图像修复算法

    PatchMatch算法出自Barnes的论文 PatchMatch: A Randomized Correspondence Algorithm for Structural Image Editing PatchMatch 算法就是一个找近似最近邻(Approximate Nearest neigbhor)的方法,要比其他ANN算法快上10倍+. 将下面的图理解了,就基本理解了整个算法. 看上图时,我们以蓝色为主颜色.A代表原图像,矩形框代表待修复的patch块,要修复patch_A块就需要

  • c++ STL常用遍历算法

    需要引入头文件#include<algorithm> 1.for_each #include<iostream> using namespace std; #include <vector> #include <algorithm> class MyPrint { public: void operator()(int val) const{ cout << val << " "; } }; void printV

  • C语言实现页面置换算法

    本文实例为大家分享了C语言实现页面置换算法的具体代码,供大家参考,具体内容如下 操作系统实验 页面置换算法(FIFO.LRU.OPT) 概念: 1.最佳置换算法(OPT)(理想置换算法):从主存中移出永远不再需要的页面:如无这样的页面存在,则选择最长时间不需要访问的页面.于所选择的被淘汰页面将是以后永不使用的,或者是在最长时间内不再被访问的页面,这样可以保证获得最低的缺页率. 2.先进先出置换算法(FIFO):是最简单的页面置换算法.这种算法的基本思想是:当需要淘汰一个页面时,总是选择驻留主存时

  • C++迷宫问题的求解算法

    本文实例为大家分享了C++实现迷宫的具体代码,供大家参考,具体内容如下 一. 实验目的: (1) 熟练掌握链栈的基本操作及应用. (2) 利用链表作为栈的存储结构,设计实现一个求解迷宫的非递归程序. 二.实验内容: [问题描述] 以一个m×n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍.设计一个程序,对信任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论. [基本要求] 首先实现一个链表作存储结构的栈类型,然后编写一个求解迷宫的非递归程序.求得的通路以三元组(i,j,d)的形

  • c++如何实现Base64算法

    Base64用途 1.用于对SOHO级路由器(网关设备)管理员帐户密码的加密 2.流媒体网站对于播放的流媒体文件的路径的加密 3.迅雷等下载软件对下载链接地址的加密 Base64算法 Base64编码要求把3个8位字节(3*8=24)转化为4个6位的字节(4*6=24),之后在6位的前面补两个0,形成8位一个字节的形式. Base64类 函数: unsigned int CreateMatchingEncodingBuffer (unsigned int p_InputByteCount, ch

  • C语言实现九大排序算法的实例代码

    直接插入排序 将数组分为两个部分,一个是有序部分,一个是无序部分.从无序部分中依次取出元素插入到有序部分中.过程就是遍历有序部分,实现起来比较简单. #include <stdio.h> void insertion_sort(int arr[], int array_length) { for (int i = 0; i < array_length; ++i) { int data = arr[i]; int j = 0; while (arr[j] < arr[i]) { j

  • C/C++实现快速排序算法的思路及原理解析

    快速排序 1. 算法思想 快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序. 2. 实现原理 2.1.设置两个变量 low.high,排序开始时:low=0,high=size-1. 2.2.整个数组找基准正确位置,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面 默认数组的第一个数为基准数据,赋值给key,即key=array[low]. 因为默认数组的第一个

  • 详解C语言实现空间索引四叉树

    前言 作为程序员,应该都对二叉树都不陌生,我们都知道二叉树的变体二叉查找树,非常适合用来进行对一维数列的存储和查找,可以达到 O(logn) 的效率:我们在用二叉查找树进行插入数据时,根据一个数据的值和树结点值的对比,选择二叉树的两个叉之一向下,直到叶子结点,查找时使用二分法也可以迅速找到需要的数据. 但二叉树只支持一维数据,如一个标量数值,对地图上的位置点这种有xy两个方向上的信息却无能为力,那么是否有一种树能够支持二维数据的快速查询呢? 四叉树 介绍 四元树又称四叉树是一种树状数据结构,在每

  • 详解C语言函数返回值解析

    详解C语言函数返回值解析 程序一: int main() { int *p; int i; int*fun(void); p=fun(); for(i=0;i<3;i++) { printf("%d\n",*p); p++; } return 0; }; int* fun(void) { static int str[]={1,2,3,4,5}; int*q=str; return q; } //不能正确返回 虽然str是在动态变量区,而该动态变量是局部的,函数结束时不保留的.

  • 详解C语言 三大循环 四大跳转 和判断语句

    三大循环for while 和 do{ }while; 四大跳转 : 无条件跳转语句 go to; 跳出循环语句 break; 继续跳出循环语句 continue; 返回值语句 return 判断语句 if,if else,if else if else if...else ifelse 组合 if(0 == x) if(0 == y) error(): else{ //program code } else到底与那个if配对 C语言有这样的规定: else 始终与同一括号内最近的未匹配的if语

  • 详解C语言gets()函数与它的替代者fgets()函数

    在c语言中读取字符串有多种方法,比如scanf() 配合%s使用,但是这种方法只能获取一个单词,即遇到空格等空字符就会返回.如果要读取一行字符串,比如: I love BIT 这种情况,scanf()就无能为力了.这时我们最先想到的是用gets()读取. gets()函数从标准输入(键盘)读入一行数据,所谓读取一行,就是遇到换行符就返回.gets()函数并不读取换行符'\n',它会吧换行符替换成空字符'\0',作为c语言字符串结束的标志. gets()函数经常和puts()函数配对使用,puts

  • 详解C 语言项目中.h文件和.c文件的关系

    详解C 语言项目中.h文件和.c文件的关系 在编译器只认识.c(.cpp))文件,而不知道.h是何物的年代,那时的人们写了很多的.c(.cpp)文件,渐渐地,人们发现在很多.c(.cpp)文件中的声明语句就是相同的,但他们却不得不一个字一个字地重复地将这些内容敲入每个.c(.cpp)文件.但更为恐怖的是,当其中一个声明有变更时,就需要检查所有的.c(.cpp)文件. 于是人们将重复的部分提取出来,放在一个新文件里,然后在需要的.c(.cpp)文件中敲入#include XXXX这样的语句.这样即

  • 详解C语言用malloc函数申请二维动态数组的实例

    详解C语言用malloc函数申请二维动态数组的实例 C语言在程序运行中动态的申请及释放内存十分方便,一维数组的申请及释放比较简单. Sample one #include <stdio.h> int main() { char * p=(char *)malloc(sizeof(char)*5);//申请包含5个字符型的数组 free(p); return 0; } 是否申请二维动态内存也如此简单呢?答案是否定的.申请二维数组有一下几种方法 Sample two /* 申请一个5行3列的字符型

  • 详解易语言的程序的输入方法概念

    为了便于输入程序,易语言内置四种名称输入法:首拼.全拼.双拼.英文.三种拼音输入法均支持南方音及多音字.首拼输入法及全拼输入法在系统中被合并为"首拼及全拼输入法",系统自动判别所输入的拼音是首拼方式还是全拼方式.双拼输入法的编码规则与 Windows 系统所提供的双拼输入法一致.例如:欲输入"取整 (1.23)"语句,各种输入法的输入文本为: ・ 首拼及全拼输入法: qz(1.23) 或者 quzheng(1.23) ・ 双拼输入法: quvg(1.23) ・ 英文

  • 详解go语言 make(chan int, 1) 和 make (chan int) 的区别

    遇到golang channel 的一个问题:发现go 协程读取channel 数据 并没有按照预期进行协作执行. 经过查资料: 使用channel 操作不当导致,channel分 有缓冲区 和 无缓冲区 , 以下是两者的区别. 无缓冲区channel 用make(chan int) 创建的chan, 是无缓冲区的, send 数据到chan 时,在没有协程取出数据的情况下, 会阻塞当前协程的运行.ch <- 后面的代码就不会再运行,直到channel 的数据被接收,当前协程才会继续往下执行.

  • 详解C语言-二级指针三种内存模型

    二级指针相对于一级指针,显得更难,难在于指针和数组的混合,定义不同类型的二级指针,在使用的时候有着很大的区别 第一种内存模型char *arr[] 若有如下定义 char *arr[] = {"abc", "def", "ghi"}; 这种模型为二级指针的第一种内存模型,在理解的时候应该这样理解:定义了一个指针数组(char * []),数组的每个元素都是一个地址. 在使用的时候,若要使用中间量操作元素,那么此时中间量应该定义为 char *tm

  • 详解C语言进程同步机制

    本文是对进程同步机制的一个大总结(9000+字吐血总结),涵盖面非常的全,包括了进程同步的一些概念.软件同步机制.硬件同步机制.信号量机制和管程机制,对每种机制结合代码做了详细的介绍,并且对琐碎的知识点和概念解释的非常清晰. ​ 在前面的博客中讲述了进程的状态及其状态的转换,每种状态的含义和转换的原因.同样我们也知道,在OS引入了进程后,可以使系统中的多道程序可以并发的执行,进程的并发执行一方面极大的提高了系统的资源利用率和吞吐量,但是另一方面却使系统变得更加复杂,如果不能采取有效的措施,对多个

随机推荐