在2d网格上找到效果重叠的最大面积

我希望编写一个程序来帮助我优化2D网格。在这个网格中，有“块”的范围决定了它的效果区域。网格上可以放置很多块。每个块可能占用超过1个瓷砖，但总是正方形。我想找出效果区域可以重叠单个XY位置的最大次数。在2d网格上找到效果重叠的最大面积

我需要算出这个36点的组合（4块类型 - 的1x1，2×2，3×3和4×4，以及范围1-9）

的效果的区域是总是以正方形图案。在下面的例子中，字母是块，数字是效果区域的位置。 A是具有1 B的效果的区域是1x1块是具有的效果2的区域是1x1块和C是具有的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

我能作用的区域中的2×2块在网格上放置尽可能多的块，并且我想知道效果区域与目标块重叠的次数。举例来说，如果我有一个瓷砖（1×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

任何人都知道我怎么可以算为其他组合？谢谢！

来源

2011-03-21 Andrew

您需要的是某种形式的空间分区，以便很容易找到影响特定位置的块。谷歌搜索“树算法”应该给你的各种方式来划分空间的想法，但总体思路是：

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

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

来源

2011-03-21 10:32:36 Skizz

你想要的是像Z曲线或Hilbert曲线那样的空间填充曲线，然后改为计算索引将其转换为每个瓦片的四叉树键。一个sfc将二维问题简化为一维问题。然后使用新密钥您想要执行DFS或BFS查找重叠的磁贴。我已经用phpclasses.org（hilbert-curve）在php中为sfc写了一个类。欢迎下载。

来源

2011-03-21 10:46:19 Bytemain

在2d网格上找到效果重叠的最大面积

回答

相关问题