基础篇-数据结构:四叉树+空间哈希网格+跳表点集

你有种再说一遍

查看本文前,你需要懂得hashmap和四叉树原理.
还记得四叉树原理吗?插入图元时候,当四个孩子节点都无法独立拥有它时(节点矩形全包含),这个图元就属于它们父亲,表现则是十字压着.
这个是一种朴素四叉树的概念,因为它太朴素了,以至于还有很多细节.


[细节一]
插入:一个节点图元数量满足阈值n,才需要分裂到四个孩子,减少节点创建,从而减少递归爆栈.
也可以加多一个树深度阈值m,控制(acad八叉树系统变量是TreeMax,我们甚至可以复用它).这个时候聪明人肯定想,有没有自适应的呢?嘿嘿就是R树,而不是四叉树.


因为有阈值n存在,所以Point这种无面积类型也能加入四叉树.但是仔细想想,会发生一个阈值穿透问题,上层满了,分配到下层,下层又满了,又分配到下下层...
有序点集或者K树更小更快,Point3d三个值和Rect四个值内存占用代价有差异,所以单独存放一个结构更好.这个结构甚至可以利用一个叫做跳表的功能进行索引,这就是另一个话题了,我们跳过它.


而在四叉树节点内排序节点图元,查找的时候可以二分法或者SIMD遍历?那包围盒根据什么排序呢?
答案是不要这样做.阈值n存在,那么表示某些子节点能完全包含图元,因此有象限序,在超阈值之后能够非遍历父节点,存在break...似乎可以,不然通过阈值n控制分裂本身就是一种分类了,分类就是排序的一种,因此不需要这个设计,并且排序也会增加插入时间.


搜索:不需要判断是否超过阈值,没有的话超出自然没有子节点.


[细节二]
我在IFox上面实现过一个四叉树,发现了十字位置其实会退化成遍历,也就是当图元聚集在十字上面,超过了分裂阈值,四个孩子也无法分到图元.
此时怎么办呢?这就需要把节点内容给下面这个散列结构了,也就是我们要结构a套结构b了,皮裤套棉裤必是有缘故,不是棉裤太薄就是皮裤没毛.


一种叫空间哈希网格(SpaceHashGrid)结构能解决这个问题,它相当于把空间均匀分割成m*m网格,拉直成一条线.
通过图元AABB包围盒的"中点"转为HashCode命中数组索引,从而插入hashmap上,以此散列了十字位置的图元们.当然,你会发现"中点"被散列其实难以被矩形选择(腰部选择),反正你知道能被散列就行,下面计算会更详细.
然后此时你会发现,网格中除了十字位置被图元散列,大量的网格是空的,因此还得引入稀疏数组来实现这个鬼东西...(真是一环套一环,为了不更深入解释,我就跳过这个)


搜索:同样计算索引,然后就可以遍历节点内图元集合了.和细节一不同,需要判断超出阈值n,四叉树节点上面必然是空的,直接转入网格结构搜索.


缺点就是网格结构无法像四叉树八叉树一样反向扩容,那么做到四叉树节点内也不需要它反向扩容,逻辑完美...


插入:
hash的计算:
假设我们把网格结构的横轴坐标1-100切割成十份,那么插入包围盒中点x=23.4,怎么知道它在哪一个网格呢?
100.0/10=10.0(单位间距)
23.4/10=2.34(向上取整)=3(网格索引)
这样就得到了X轴的,Y轴同理.


查询:
在map中获取就只需要key是("X"+","+"Y")就能获取value了,可谓是简单极了.不过字符串拼接再转为hashcode,这个对于GC不友好,那么这个map为何使用hashmap呢?同时我们还存在一个问题,一个大图元跨几个空间,那么仅包围盒中点的节点记录图元id,是会存在缺失选择的,所以我们需要根据选择调整插入.(为什么缺失选择,想象一个圆形被栅格化,然后只有中点记录了图元id,边缘怎么也选中不了)


有两种做法插入图元id:
方法一:AABB包围盒四个Point节点加入图元id.
方法二:AABB包围盒围着的节点都加入图元id.


作为内存节约,肯定会觉得方案一更好,因此,我们就不能用hashmap["x,y"]方式获取了.
我们需要构造X值数组和Y值数组,搜索时候排除选框矩形左边不是范围,和右边不是范围,在中间就是选择范围,留下一个Xmin和Xmax.Y轴同理.
于是乎这个代码会变成SIMD+并行,然后在不支持SIMD的时候退化成二分法搜索xArray和yArray,这样就无敌了.


[完整的节点分裂流程]
加入图元到四叉树节点时,先判断是否超出阈值n,否就直接加入,是就判断四个儿子有没有一个能加入图元,能就进行分裂和分配.
剩下没能分配出去的,就是父节点拥有的,检查是否还超出阈值,如果超出了,就构建哈希网格.


[完整的搜索]
同细节二


参考:在地图上面就不一样了,他甚至用了希尔伯特曲线实现节点分裂.
https://halfrost.com/go_spatial_search


[SimonDev]
https://b23.tv/SfkCJKN


就此ssget完全可以代替掉了.之前还觉得怎么屏蔽关键字,觉得键盘钩子先抓输入,然后转为对应事件就好了.后来发现了,自己构造索引基本上无敌.




[点的有序数据结构]
为了SIMD这碗醋包的一碗饺子,使它能够使用并行/SIMD/CPU预读/跳跃索引/减少内存OOM和碎片.


我要设计一个点集,这个点集能够容纳上百亿的点,它不能单纯用一个数组完成,因为数组在扩容的时候是采取全量复制,此时内存OOM了,因此需要用节点断开,并且节点内保证一定连续性不分裂.
选择跳表+三值数组(XYZ),似乎不错的选择.跳表是通过数组头实现有序,节点则是数组内经过插入实现有序.


搜索:我先说它怎么用先,想要获取矩形范围,那么跳表的索引就能快速找到这个xmin和xmax范围的节点,在这些节点内搜索ymin和ymax,此时你会发现Y字段没有索引,因此得并行SIMD进行穷举搜索.
为了并行计算,每个节点都允许一个线程进入,所以要有读写锁实现线程安全的跳表,然后节点内用SIMD,例如大规模平移/旋转等矩阵变换,或者搜索Y和Z,因为这两字段无序.
用xArray区间记录为例子[1,100][201,250]...跳表是只会记录头元素作为hashcode[1,201...]这样的形式很方便可以通过节点hashcode判断是否存在这个点,从而获取区间.
它是非平衡的,内存友好的,没有过多的节点旋转,但是怎么能设计出中间是断开的呢?
节点满了1024之后怎么拒绝?其实不是拒绝,而是分裂,新建一个key,然后移动一半过去,也就是跳表是接受有序数组作为参数输入,然后能够自动分裂这个数据(保证有序的检验参数,似乎仍然需要SIMD去实现).


插入分裂:
A:先插入1,再插入100,再插入1-100之间...再201,发现前面区间是间距太大100-1=99<201-100=101,并且数组满75%(泊松分布)就独立一个节点(直接在short).视为中间大概率存在一个空节点[101,200],即使不存在也不要紧,跳表也不记录,实现跳表版稀疏数组.
B:阈值数组长度1024,满员75%,直接在插入时候分裂一半出去新节点.


缩容合并:
因为是多线程并行,所以我们不能在读时候锁,否则最快的读取功能就没有了.
A:删除时候,如果当前节点只有25%,并且前面容量有25%,我们就向前合并.
B:时间也是一个美好的法则,异步只读需要整理的,并且每2秒整理一次.在并行读取时候可以停止整理,跟GC似的.
C:内存不足,因为win允许虚拟内存和硬盘Swap,此处没有实验.通常来说不足时候,序列化跳表末尾成员到磁盘,并且在跳表标记省略部分,需要时候再读取磁盘.


struct Node{
  double Start,
  double End,
  int Count,
  double[1024] XArray,
  double[1024] YArray,
  double[1024] ZArray,
  bool 满足75%=>Count>1024*0.75=768
}


c#自带没有线程安全有序哈希结构的,没有类似java的跳表结构ConcurrentSkipListMap,因此需要自己拷贝一个
https://github.com/pknam/skiplis ... rrentSkipListMap.cs


SIMD的三角函数,以此实现并行矩阵旋转
https://blog.ladeak.net/posts/math-sin-simd
(完)

hubeiwdlue

虽然看不懂，必须要点赞。