找到二维网格上效果重叠的最大面积

Question

我希望编写一个程序来帮助我在二维网格上进行优化。在这个网格中，有一些“块”，其范围决定了其作用范围。网格上可以放置许多块。每个方块可能占据超过 1 个方块，但始终是正方形。我想找出效果区域可以重叠单个 XY 位置的最大次数。

我需要计算出 36 种组合（4 种块类型 - 1x1、2x2、3x3 和 4x4，以及范围 1-9）的效果。

效果区域始终呈方形图案。在下面的示例中，字母是块，数字是效果区域所在的位置。 A 是一个 1x1 块，其影响区域为 1。B 是一个 1x1 块，其影响区域为 2。C 是一个 2x2 块，其影响区域为 1。

X X X X X
X 1 1 1 X
X 1 A 1 X
X 1 1 1 X
X X X X X

X X X X X X X
X 2 2 2 2 2 X
X 2 2 2 2 2 X
X 2 2 B 2 2 X
X 2 2 2 2 2 X
X 2 2 2 2 2 X
X X X X X X X

X X X X X X
X 1 1 1 1 X
X 1 C C 1 X
X 1 C C 1 X
X 1 1 1 1 X
X X X X X X

我可以在网格上放置尽可能多的块如我所愿，我想找出效果区域与目标图块重叠的次数。例如，如果我有一个 A 图块（1x1，范围为 1），我会通过包围目标 T 来最大化效果区域。所以这里的答案是 8。

X X X X X
X A A A X
X A T A X
X A A A X
X X X X X

有人知道我如何为其他组合计算出这个值吗？谢谢！

Answer 1

您需要的是某种形式的空间分区，以便轻松找到影响特定位置的块。谷歌搜索“树算法”应该会让您了解划分空间的各种方法，但总体思路是：

for each block
  addblock (root, block)

addblock (node, block)
  if block fits inside node
    if there are child nodes
      for each child
        addblock (child, block)
    else
      add block to node by dividing into area occupied by block and areas not occupied by block, moving any blocks at this node into all new child nodes
  else
    if there are child nodes
      for each child
        addblock (child, block)
    else
      add block to node block list

然后，要找到覆盖一个正方形的块的数量，在树中搜索覆盖给定正方形的节点，然后查看该节点中有多少个块。

Answer 2

您想要的是像 Z 曲线或希尔伯特曲线这样的空间填充曲线，然后计算索引，将其转换为每个图块的四叉树键。 sfc 将 2D 问题简化为 1D 问题。然后使用新密钥执行 DFS 或 BFS 来查找重叠的图块。我在 phpclasses.org ( hilbert-curve ) 的 php 中为 sfc 编写了一个类。欢迎您下载。