根据有限网格中的位置计算单元尺寸

我搜索了之前是否已询问过此问题，但找不到任何类似问题。这更像是一个算法问题，并不局限于任何特定的编程语言。所以，我的问题如下。根据有限网格中的位置计算单元尺寸

给出数据：

矩形网格，固定的宽度和高度的 'G'：（W，H）。
网格中'n'个块的绝对位置的数组'A1'：A1 = [（x1,y0），（x1，y1），...，（xn-1，yn-1 ）]。
数组中的每个块都是一个带有4条边的简单矩形。
数组'A1'中的所有块的面积总和= 网格'G'的总面积，换句话说，数组'A1'具有尽可能多的填充整个网格所需的块'G'。
数组'A1'中的位置未按任何特定顺序排列。
位置值表示块的左上角。
没有块重叠。

问题：计算每个块的大小（宽度和高度）。即计算（w0，h0），（w1，h1），...，（wn-1，hn-1）。

我觉得这个问题可以推广到任何维度的空间。

来源

2014-12-01 FearLeslie

A1中的位置与块的位置有关？ – 2014-12-01 21:32:50

它真的很重要，我的意思是所有的位置值都遵循与它们各自的块相同的关系。 – FearLeslie 2014-12-01 21:38:46

@ FearLeslie如果在A1中的位置是相应块的左下角与块的中心或块的右上角相比是绝对有差别的...... – twalberg 2014-12-01 22:06:21

我现在看到你正在寻找一种方法来将分区网格划分成具有给定左上角的矩形块。但是，总的来说，还有不止一种方法可以做到这一点。例如。给出的3左上拐角A，B和C在下面的左，4x4网格或者两组块其右侧的解决了这个问题：

A.B. AaBb AaBb 
.... aabb aabb 
C... Ccbb Cccc 
.... ccbb cccc

可以从作为使一个较大网格只要你喜欢这个网格的许多副本。由k个副本构成的网格（因此使用3k个块）将有2^k个不同的解决方案。

此外，一个特定的问题实例不需要任何解决方案。例如，至少有一个网格正方形左侧没有被问题实例覆盖：

A.  Aa  A. 
.B  .B  aB

来源

2014-12-02 02:24:32

这是我以前的评论的编辑：我没有考虑过您在回复的第一部分中指出的内容的可能性。这部分是非常真实的。像你在回复的第二部分提到的情况不会出现，因为总是有足够的块的总面积总和等于总的网格面积。鉴于您答复的第一部分，问题定义现在需要更多信息才能有独特的解决方案。所以我现在的问题是这些信息可能是什么？ – FearLeslie 2014-12-02 05:39:28

什么都没有想到我害怕。部分原因在于，在这个例子中，（2，2）（基于0的合作）可以从B中“向下”或从A向右“填充”。但是当存在多于一个这样的“决定“，然后做出一个选择可能会影响电网其他部分的选择，这就是困难的原因。 – 2014-12-02 08:15:08

如果我们给出每个块的宽度或高度，这个问题可以有一个独特的解决方案，但是这种方式会破坏问题的目的。无论如何，我会接受你的答复作为有效答案。谢谢你的时间，真的很感激:) – FearLeslie 2014-12-02 18:52:26

根据有限网格中的位置计算单元尺寸

回答

相关问题