在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網格上找到效果重疊的最大面積

回答

相關問題