用于表示二维网格的高效数据结构

Question

有一个任意大小的二维网格（例如1000 * 1000）。

图案如下：

给定的输入是四个整数：x y w h，表示每个矩形左下角的坐标（x，y）及其宽度和高度。

具有共享边缘或重叠的矩形被定义为连接的。

一组连接的矩形被定义为群集。

每个单元格上的矩形数量被定义为其厚度。

因此，问题要求计算： 1.最大厚度 2.集群数 3.单个集群中集群元素的最大数量 4.单个集群的最大面积

例如，在上面的图片中，最大厚度为3，有2个集群。一个集群由3个矩形组成，其面积为44。另一个集群中的元素数量为4，面积为30。因此，具有最大集群元素数量的集群为4，最大集群面积为44。

我的解决方案相当幼稚。我使用了一个二维int数组来表示网格。在读取输入时，我只需增加相应单元格中的数字即可。读完所有输入后，我使用深度优先搜索来确定群集。

问题是我的算法非常慢，当给出大型输入时很快变得无法使用（例如，当网格大小超过1000 * 1000时）。

因此，我想知道是否有任何有效的数据结构和算法来解决这个问题？

- Nate Zhang

---

有多少个矩形可以存在？ - kraskevich

可能会有很多。它没有任何限制。 - Nate Zhang

关于矩形数量和网格大小，期望的时间复杂度是多少？没有性能要求，无法确定算法是否可行。 - kraskevich

列举的四个问题都是集合问题。你在思考一个好的“二维数据结构”时遇到了困难（它可以允许查询类似于“这个点位于哪些矩形中”）。看看解决二维问题的策略，比如“线性扫描”或“分治法”。（噢，我可能先读了IVlads的回答。） - greybeard

Answer 1

我认为您刚刚描述了使用2D AABB结构的空间分区。

输入网格被投入树中并以任意方向定位。树的目的是排序。

您可能需要扩展树的功能以适应您的需求（例如连接、跟踪集群、层/厚度）。

用于包含2D AABB的空间分区树可以被扩展、展开或叶子缓存，以有效地减少访问时间。

视频游戏中的2D物理引擎使用这种方法，在任意大（大约无限）的网格大小上轻松有效地管理数百到数千个任意形状的对象碰撞。它们的处理可以通过OpenCL（用于CPU和GPU）或其他GPGPU技术加速。

请参阅维基百科关于AABBs的文章。

请参阅维基百科关于BSPs的文章，了解使用（二进制）树进行空间分区的一般思想。

请参阅维基百科关于四叉树的文章，作为更高级别的树概念，可能更易于实现，如果所有内容都是AABB，则甚至可能更快，因为它的宽度是4倍。您还可以展开更高级别的树，尽管好处似乎主要在于二维空间的四叉树。

请参阅维基百科关于碰撞检测的文章，以确定连接和集群。

请参阅维基百科关于伸展树的文章，了解扩展和展开树的好处。

- TylerY86

Answer 2

读取完所有输入后，我使用深度优先搜索来确定聚类。你不需要这样做 - 你可以在读取输入时决定聚类，就像你决定厚度一样。对于每个单元格，跟踪它属于哪个聚类。当迭代与读取矩形相对应的网格单元格时，跟踪它们所属的聚类。将此遍历期间发现的所有聚类合并为一个聚类。您可以使用Disjoint-set数据结构以非常接近常数时间高效地完成此操作。但是，您的整个问题可能更好地通过sweep line algorithm解决。

- IVlad

Answer 3

我的建议是结合当前给出的两个答案：使用空间数据结构，如AABB树或四叉树，来存储你已经处理过的所有矩形，以便快速找到相邻的矩形；然后将连接的集群存储在并查集或不相交集数据结构中。

一旦你处理完所有矩形，就可以以线性时间回答问题2和3。问题1（最大厚度）有点棘手；如果不小心，如果所有矩形重叠，可能会进行平方级别的重叠测试。类似地，对于答案4也是如此。

因此，当您输入一个重叠到空间数据结构中的矩形时，最好将其拆分为常数厚度的不相交部分。然后，问题1和4也可以相对较快地回答。

- Erik P.