造四叉树|峰峰的小窝

本来打算好好过高三，程序停一停，谁知道又有疫情了呢。

我做的天马行空的项目需要在超大的二维平面里进行超多物体的碰撞检测，就像是物理引擎，但比物理引擎是简单多了，需要一些办法优化一下。

超大平面的话，均匀的切片就不好使了，内存啊。而且这些物体分布可能很不均匀，大多数切的片都浪费了。

经过查资料，我发现四叉树这个东西很合适。

于是github找了两个四叉树，然后就遇到了c++的坑和这些库的这两个库的问题。

这俩库都用了c++里一个我不懂的语法，好像和泛型的基本类型的值域或者什么的有关系。用到了min和max，而我用的csv库引用了windows.h头文件，这个头文件定义了min和max的宏，很巧我在一个cpp文件里先引用了csv库，又引用了项目各个cpp都用的一个头文件，阴差阳错地min和max就编译不过。最终被我找到了。

而这两个库，一个四叉树不支持改和删，一个查有BUG，经调试大概是智能指针的问题，但是我完全不会用智能指针。对于我的项目来说可能效率有点底。

于是，我要写一个四叉树。

目标

有几类不同的东西要存在同一个平面中，而且希望查询的时候可以分类查。这些数据可以分成两类，一类是矩形，基本不会动、一类是点，几乎一直在动。

因此，我准备写一个分层四叉树，有矩形层和点层两类层。
会根据矩形层建树结构，点仅仅是存在树上。

为了保证矩形的插入和删除不要很麻烦，只会根据矩形的大小绝对它在树中的深度（深度保证这个大小的矩形任何位置最多占据4个节点），建树的深度是那一片的存的矩形最深到多少。（防止太小的矩形溢出内存，断言了最小尺寸）。
点的存储总数尽可能往深的存，因为单个树节点存储的信息是线性的，深了的话能把点尽可能分给不同的节点。

为了能让几乎一直动的点修改位置时快一点，和让占据4个节点的矩形好删除，数据单独存在一个线性容器中（同时保存了物体所处的节点），树上节点指向数据，插入元素时返回线性容器的索引。这样通过线性容器的索引能够常数时间找到节点，而不是从树根找下去。

现在不跨节点的点移动是常数时间，其余操作都和树深度线性相关（可以简单理解成对数时间？不过似乎树深度和节点数量没关系）

查询很多情况不是想把所有东西都查出来，而是想看一看有没有，或者是找其中一个，因此，查询函数不是返回对象数组，而是一个迭代器，查询相关的代码几乎都写迭代器里了。其实现就是让枝剪的深度搜索算法找到一个东西就返回，可惜我不会协程（不知道这算是协程吗），写这玩意可比深度搜索算法麻烦多了。

存数据的线性容器

上面提到的线性容器应该能有这些功能：

能够随机访问（这点list做不到）
能够随机删除（这点deque和vector做不到）

等等...为何这个容器得是线性的?

set就挺好吧！set的存取都是对数时间，树上的数据都存这个容器里了，几乎所有树上的操作都要用到这个东西，往简单来说，它把我优化成常数的操作也变成对数了...

于是...我写了这样一个容器：

一个deque来存数据
一个deque来存已经被删掉的数据，解决deque不能随机删除的问题。
用的时候先用第二个deque标记的空位，像内存池一样。

但其实还是有个问题的，从内存池的角度看，它不能释放内存，不合格。

没关系啦。这样！大功告成。

（不要问我为什么不能定期整理，删掉标记数据，因为索引已经向上返回了，整理了索引就变了。总不会有谁写内存池会去重新排列内存吧...）

.h声明

我发现把头文件和cpp文件分开写很舒服，不仅是条理，也避免循环引用。

写这个四叉树本来想用泛类，不过代码不想内联写，所以没有用泛类。

Object这个类，我让它作为所有类的基类，所以不用泛类也能存（就算没这个Object，也能用void*是吧...）

以前写东西都是写一步想一步，一边声明一边定义，这次因为数据结构太复杂了，决定先把所有的声明写好，再去实现。

四叉树的类提供了这样的公开方法。

QuadTree(const rect2&, vector<LayerTpye> le);
~QuadTree();

size_t insert(const vec2f& point, Object* data, const LayerID& layer);
size_t insert(const rect2& rect, Object* data, const LayerID& layer);
void remove(const size_t& index, const LayerID& layer);
void move(const vec2f& point, const size_t& index, const LayerID& layer);// 点移动是高效的
void move(const rect2& rect, const size_t& index, const LayerID& layer);
QuadTreeQuery queryNear(const vec2f& point, const LayerID& layer) const&;// 所有可能相关的对象
QuadTreeQuery queryNear(const rect2& rect, const LayerID& layer) const&;
QuadTreeQuery queryInclude(const rect2& rect, const LayerID& layer)const&;
QuadTreeQuery queryBeInclude(const vec2f& point, const LayerID& layer)const&;
QuadTreeQuery queryBeInclude(const rect2& rect, const LayerID& layer)const&;
QuadTreeQuery queryIntersect(const rect2& rect, const LayerID& layer)const&;

有增删改查。

查询对象QuadTreeQuery公开方法声明是这样：

bool next();
bool is_end()const&;
vector<Object*> getAll();
Object* operator*()const&;

.cpp定义

现在回头看代码，不知道为什么写代码的时候把保存节点子节点的四个指针用四个变量存的，而不是数组，然后不能循环遍历四个子节点，代码都要写四份，面对这种又无聊又增大工作量的东西，当时写的时候用了宏：

#define forABCD(node,code){ \
Nodep child = (node)->a;code \
child = (node)->b;code \
child = (node)->c;code \
child = (node)->d;code}

矩形的插入

矩形插入的深度是根据它的大小进行计算的，为了保证它插入那一层后最多只是占了四个矩形，应该保证那一层节点的大小不论是长和宽都大于矩形的大小。这样矩形在四个节点中间时是占了4个，在两个节点中间占两个，还有只占一个。（不存在占三个这种情况，所以我断言不会出现占三个的情况，防止代码有错的地方）。

先算深度，这个很简单，循环，四叉树大小循环对半切，停止条件是切完之后的四叉树大小小于矩形大小（写代码时用的矩形大小二倍增，大于四叉树大小时停止）。

有了最多占四个的前提，插入就好写了，如果占据了不同的节点，那么矩形的四个顶点一定在不同的节点（各不相同就是4个，两两相同就是2个，都相同就是1个），如果顶点在相同的节点，那么这个矩形一定没有跨节点。

出现跨了2个和4个的情况的话，对角顶点一定不在同一个矩形中，所以先让两个顶点从树根往下找指定深度（深度不够就创节点）。这样说没问题，但是这样写代码可能存在效率问题，因为每次插入至少从根往下找两次，最多找四次（占四个），因此此处我只往下找了一个顶点，而另一个是在找的同时算了最近公共祖先，如果还需要进一步找节点，那么就从公共祖先开始找。

点的插入

这个简单，直接复用了矩形找顶点对应的节点的代码，不过这个不是固定深度，是尽量往深的找，而且不会创建新节点。

创建节点和删除节点

最初的树上只有一个根节点，叶节点可以一分为四，并不是只有叶节点才能存数据（矩形的存储不是固定深度的嘛），只有叶节点才能存点数据（减小线性容器的开销嘛）。

一分为四的时候会把点数据按照位置分发给子节点（同时改一下点数据记录的节点对象）。

合适非叶节点可以合四为一，同时汇总点数据，不过合四为一的条件很苛刻，需要四个子节点都是没存矩形的叶节点，成功的话会向上递归。

矩形和点的删除

线性容器那边的数据保存了数据对应的矩形和点的节点对象指针，所以删除的时候开销为常数（如果忽略节点上线性容器开销的话）。

不过矩形的话还要检查一下存矩形的节点是不是已经空了，如果空了就试图让父节点合四为一。

矩形和点的移动

矩形就是删除+插入。

点会先判断有没有跨节点，没有就改了数据直接返回。否则就删除+插入。

查询

最重要的东西，查询。

查询分了4种：

可能与参数有关的对象，查出来是什么和树结构有关。参数是矩形或点
被参数包裹的对象。参数是矩形
把参数包裹的对象。参数是矩形或点
与参数相交的对象。参数是矩形

虽然代码很多，但核心思想就一个，搜索，为了好写，用了深度优先搜索，先序遍历。

根据要查询的矩形（或点）与子节点的相交情况进行枝剪。

代码过于复杂，这是伪代码：

存信息的 栈<节点, 模式> 初始存了根节点，模式为遍历。
存遍历信息的整数 索引，初始-1

bool next(){
    while (栈不为空) {
		switch (栈顶元素模式)
		{
		case 遍历:
			索引 += 1;
			if (索引 < 栈顶节点的元素数量) {
                if (通过索引取出的元素有效){
                    return true;
                }
				break;
			}
			
			// 到此说明遍历对象结束了，需要切换节点
			if (栈顶节点没有子节点) {// 没有子节点，向上返回
				出栈;
				break;
			}
			// 有子节点，遍历四个
			栈顶元素模式 = 1;
			
            if(子节点1与查询有交集){
                子节点入栈;
                索引 = -1;
                break;
            }
		case 1:
			栈顶元素模式 = 2;
            if(子节点2与查询有交集){
                子节点入栈;
                索引 = -1;
                break;
            }
		case 2:
			栈顶元素模式 = 3;
            if(子节点3与查询有交集){
                子节点入栈;
                索引 = -1;
                break;
            }
		case 3:
			栈顶元素模式 = 4;
            if(子节点4与查询有交集){
                子节点入栈;
                索引 = -1;
                break;
            }
		case 4:
			出栈;
			break;
		}
	}
	已结束 = true;
	return false;

}