平铺地图

2011-08-27 120 views 1 likes

数据结构，我想打一个无限拼接地图，从(-max_int,-max_int)直到(max_int,max_int)，所以我会做一个基本结构：chunk，每个chunk包含char tiles[w][h]并且还int x, y坐标，因此，例如h=w=10所以tile(15,5)在chunk(1,0)上(5,5) coordinate，并tile(-25,-17)是chunk(-3,-2)上(5,3)等。现在可以有任何数量的块，我需要将它们存储起来，并且在O(logn)或更好的情况下（O(1)如果可能的话，但它不是..）很容易访问它们。应该很容易：添加，删除（不必）和查找。那么我应该使用什么数据结构？平铺地图

来源

2011-08-27 Vladp

这很难遵循。也许你可以提供一个结构/类和一个公式来转换块，以瓷砖协调。 – 2011-08-27 18:41:49

它只是一堆用X对象，y坐标（块），现在我需要存储它们方便地访问他们 – Vladp

回答

读入KD树或四叉树（八叉树的2D变体）。这两方面都可能是一个很大的帮助。

来源

2011-08-27 18:34:38 Mranz

四叉树 - 应该是一个常量的大小广场......不适合。 kd-tree - 如果我只有10个块，并且全都具有相同的x ??，该怎么办？ – Vladp

取决于你构建算法kd树，但常见的是分裂的最大尺寸，所以在所有箱子是在同一x平面的情况下，你总是劈在Y，这应该仍然保持你的访问时间低。换句话说，如果你不强迫kd-tree旋转分裂平面并保持适应性，这就是它试图解决的确切问题。 – Mranz

如果全部彼此靠近，那么有没有更好的解决方案？ – Vladp

所以所有的空间splited成块（矩形集群）。通常问题是将数据存储为稀疏（由于已经实现了集群）矩阵。为什么不使用两级字典式的容器？ rb-tree by row index其中value是按列索引的rb-tree。或者如果你很幸运，你可以使用散列来获得你的O（1）。在这两种情况下，如果找不到行，则将其分配到容器中，然后创建新容器作为值，但最初仅使用单个块。当然，在现有的行上分配新的块会比新的更快，我想这是这种方法唯一的问题。

来源

2011-08-27 19:13:29 ony

这会工作，但内存成本可能很大。对于这些类型的问题，它们是更好的空间数据结构。 – Mranz

平铺地图

回答

相关问题