代表室内地图的数据结构

Question

假设我有一张表示室内地图的图像。在这张地图上，某些区域是“允许的”，其他的则不是。然后我会定期获得一组坐标(x,y)，并且需要检查它们是否在“允许”区域中。

目前，我用boolean[][] map变量表示此地图，其中true表示允许。要检查，我只是检查值map[x][y]

但是，我代表的图像可能会变得相当大，比方说最大5000x5000像素。因此，我的map变量在内存中变得过大（在这种情况下，假设boolean需要大约1个字节，则为25MB）

是否有更好的数据结构，用于解决我的问题？我现在想了一会儿，但看不到任何需要更少空间的东西。

在此先感谢！

Answer 1

这种情况的常见情况是使用Rect结构的数组/ List。然后你定义这样一个矩形定义了一个“允许”的区域。

然后，给定一个点(x, y)您只需遍历数组/列表并检查该点是否位于集合中的任何矩形内。你可以简单地使用Rect.contains(x,y)。如果有任何Rect包含该问题，则回答true，否则回答false。

这应该会给你一个非常不错的性能/内存消耗比。假设“区域”是矩形的（或者每个区域可以表示为 - 理想情况下 - 少量的矩形）的联合体，它通常用于您的应用程序中。

另一种选择（假设矩形不是选项）将使用谨慎的多边形来表示区域。如果这是可行的，你可以使用这里提供的一个简单的算法：http://alienryderflex.com/polygon/它可以让你测试一个给定的点是否在时间内（甚至是非常复杂的）多边形O(n)其中n是定义你的区域的所有多边形的所有顶点的数量地图。

如果您的区域是非常散（即很难使用他们甚至多边形的矩形来表示），那么你可能没有其他简单的选择。你可以做的是（例如）创建一个包含行允许信息的数组。对于每一行，您将拥有一个数组int[]，其中每个int将包含32位，每个代表连续列的boolean值。这与您已经拥有的非常相似，但是您的内存占用空间会缩小8倍，因为每个值只会占用一位而不是整个字节。