c++ - 如何有效地存储矩形网格？

Question

所以我想用不同形状的矩形而不是正方形来制作一个建筑游戏，但我想不出一种有效的方法来做到这一点。例如，我不想让每个形状都像俄罗斯方块这样的瓷砖网格。我希望每一块都是一个具有宽度和高度的对象。例如，2*3 块不会占用 6 个瓷砖，它只是一个矩形。我必须能够有效地组织作品，并能够在某个坐标处获得作品。如果我只使用二维图块数组，它将使用我不需要的内存。

Answer 1

无论您如何做，在任何给定坐标处获取矩形都非常昂贵，但可能最有效的方法是创建一个不限于矩形的松散网格。每当一块移动时，它将更新一个二维数组，并在其全部或部分包含的所有方格中使用其引用。每当给定坐标时，计算坐标在网格中的哪个正方形，然后您可以进行更广泛的计算以检查坐标是否实际上在矩形内。

Answer 2

本来打算早点发布的，我知道您已经接受了答案，但您可能需要考虑以下内容。

我想我明白你在问什么。您想通过检查矩形边界来检查图块属于哪个矩形（如果有）。因此，要检查该正方形中的右上图块是否属于任何矩形，其中 any-是不属于任何矩形的图块

a a a -
a a a b
a a a b
a a a b

你会检查矩形a和矩形b的瓷砖(0,3)，看看它不属于任何一个。

您试图避免的替代方法是将每个图块设置为属于一个矩形：

(0, 0).parent = 'a'

(0, 1).parent = 'a'

...

(2, 2).parent = 'a'

ETC

或类似的东西。

每种解决方案的权衡取舍不同”

在第一个中，每次您想找到一个图块属于哪个矩形时，您都必须进行大量比较。O(n)比较，您将比较n最坏情况下的时间，1最好的情况下，以及n/2平均比较（如果每个图块都有相同的机会属于一个矩形，这在类似俄罗斯方块的游戏中是不正确的）。

在第二种解决方案中，您必须为每个图块存储一个父变量。这增加了内存使用，但时间复杂度始终保持不变O(1)。

每个可能会更好，具体取决于您的网格可能是如何设置的：

a a a a a a a a a a a b d d d d d d d d
a a a a a a a a a a a b d d d d d d d d
a a a a a a a a a a a b d d d d d d d d
a a a a a a a a a a a b d d d d d d d d
a a a a a a a a a a a b d d d d d d d d
a a a a a a a a a a a b d d d d d d d d
a a a a a a a a a a a - e e e e e e e e
a a a a a a a a a a a c e e e e e e e e
a a a a a a a a a a a c e e e e e e e e
a a a a a a a a a a a c e e e e e e e e

检查特定瓦片的父级非常快：您只需检查 5 个矩形，如果瓦片不在任何矩形中，则它没有父级。

检查一个 tile 是否有父级同样快。

但是，当您开始拥有越来越多的矩形时...

a b c d e f g h i j k l m n o p q r s t
A B C D E F G H I J K L M N O P Q R S T
u v w x y z U V W X Y Z 1 2 3 4 5 6 7 8
9 0 ...
...

您必须进行大量比较才能确定特定图块是否有父图块。您不必精确定位坐标并检查其父值，而是必须检查每个矩形以查看图块是否在其中任何一个中。

---

我建议你简单地使用 NxN 网格并为每个图块存储一个父矩形值（第一个解决方案），除非你知道你不会使用那么多矩形或者网格将主要用空白空间填充。

Answer 3

我只需创建一个具有Width和Height的类Rectangle，然后我将使用此类实例的数组。

Answer 4

矩形是否重叠？如果没有，您可以在此处使用 RectangleGrid 类：https ://github.com/eyal0/OctoPrint-Slicer/blob/master/src/RectanglePacker.js#L10

添加矩形可能会很慢，但对于您的用例可能会起作用。查询给定位置的矩形是 O(nlogn)。