这是一个创建于 2950 天前的主题，其中的信息可能已经有所发展或是发生改变。
题目：
已知一个矩形容器[(0,0), (W,H)]，其中已经容纳（摆放）了 m 个小矩形，
这些矩形均满足以下条件：
1. 当然都比容器小，且摆放位置未超出容器范围；
2. 所有小矩形的边均与容器的某一边平行或者重叠；
3. 所有小矩形不重叠；
4. 所有小矩形至少有两条相邻边与容器或者其他小矩形的边重叠（其实就是指
小矩形向某角落挤紧，在保持不重叠的情况下只有 0 个或 1 一个自由度可滑动）
问题算法：
取另一个小矩形 (w,h)摆放到容器中，使其满足所有上述 1~4 的条件，
求所有可能的摆法。
想了很久没有思路。请教诸位了。
已知一个矩形容器[(0,0), (W,H)]，其中已经容纳（摆放）了 m 个小矩形，
这些矩形均满足以下条件：
1. 当然都比容器小，且摆放位置未超出容器范围；
2. 所有小矩形的边均与容器的某一边平行或者重叠；
3. 所有小矩形不重叠；
4. 所有小矩形至少有两条相邻边与容器或者其他小矩形的边重叠（其实就是指
小矩形向某角落挤紧，在保持不重叠的情况下只有 0 个或 1 一个自由度可滑动）
问题算法：
取另一个小矩形 (w,h)摆放到容器中，使其满足所有上述 1~4 的条件，
求所有可能的摆法。
想了很久没有思路。请教诸位了。
第 1 条附言 · 2016-12-03 20:34:48 +08:00
补充一下：
a) 矩形尺寸为整数;
b) 条件 4 括号里的解释更严格，不过条件 4 也够了
a) 矩形尺寸为整数;
b) 条件 4 括号里的解释更严格，不过条件 4 也够了
 |
1
sherlocktheplant 2016-12-03 18:31:06 +08:00
你这是要压缩贴图吗？
|
 |
2
suspended OP @sherlocktheplant 不是，工业需求。
|
 |
3
Kilerd 2016-12-03 19:24:38 +08:00
这算是动态规划的题目把。
|
|
4
sherlocktheplant 2016-12-03 19:40:59 +08:00
你可以看看 uv 压缩相关的算法 虽然是图形学的东西 但是实际是一样的
|
 |
5
9hills 2016-12-03 19:54:20 +08:00 via iPhone
4 并不能得出 向某角落挤紧
举个例子，小矩形绕内壁一周。 |
 |
6
SCaffrey 2016-12-03 20:03:44 +08:00 via iPad
数据范围大该怎样呢
|
|
7
suspended OP @sherlocktheplant 那个方面的算法不太符合要求，因为不会考虑是否方便切割之类的工业要求。
|
|
8
suspended OP @9hills 虽然我括号里的这个解释其实有点多余。。。不过你说的小矩形绕内壁一周没问题啊，只有在往四个角落挤紧是符合条件 4 的，因为要求至少两条相邻边重叠。
|
|
9
9hills 2016-12-03 20:21:37 +08:00
@suspended 某角落指的四个角落中任意一个么。。
就算你这么解释也不对，比如容器 10X10 的，然后放入一个 5X10 的在中间，四个角落都不沾 另外题目里也没有说矩形是不是有最小单位，如果没有的话，那解肯定是无穷多个 |
|
11
suspended OP @9hills
"比如容器 10X10 的，然后放入一个 5X10 的在中间，四个角落都不沾 " 所以这种情况不符合要求 4 ，因为没有任何边与其他矩形重合。 “某角落”是指任意角落，我表达得有些含糊了。 另外，矩形肯定最小 1x1 ， 0x0 不能称为矩形吧？ |
|
12
suspended OP @9hills
"在 5X10 靠边放一个 1X1 的就好了，还是四个角落都不沾" 这个不矛盾啊，我是指往某一个角落挤紧，不是说位于某个角落。当然，其实不看括号里的解释就好了，如果觉得解释反而更不好理解的话。 |
|
13
9hills 2016-12-03 20:29:27 +08:00
@suspended 看我补充，你找两个 1x1 的方块，靠紧。放到任意一个边上，依然满足你的 1-4 的全部要求
0.5x0.5 就不是矩形了？ |
|
14
suspended OP |
|
16
suspended OP @9hills 是做切割。我找了好些论文，比较了各种算法，挑出来一个最符合需求的来实现。论文嘛，限于篇幅，都语焉不详的，实现的时候发现其中的一个子算法（就是我的问题所述）论文里并没有交代，所以放上来请教一下大家。
"你把矩形改成从第一个小矩形开始，必须一个一个添加就行了。"，的确就是这么一个过程，不过会有本质区别吗？ |
|
17
9hills 2016-12-03 20:40:44 +08:00
其实我看了下，用轮询的方法，时间复杂度也不高。 M 和 N 不大的话轮询就好了。。。
|
 |
19
binux 2016-12-03 21:15:00 +08:00
工业算法和竞赛算法是不同的，很多时候，竞赛算法就是在「求所有可能的摆法」以及「最佳」中纠结。
但是在工业中，贪婪次优都是是可行的。 一边给出「求所有可能的摆法」，一边又要「考虑是否方便切割」，先搞清楚到底要什么比较好。 |
|
20
suspended OP @binux 是从所有可能摆法中选优。题目的这个算法，即便穷举的话，时间复杂度大约是 O(n^2)？(不好意思，不懂算法啦）所以「求所有可能的摆法」完全可行吧，「考虑是否方便切割」就是如何选优（选优还有其他要求）的问题，这个条件以目前的计算能力是达不到最优的，只能在可接受的时间内找到个较优的算法。
现在就是「求所有可能的摆法」这个步骤希望找到比穷举更好的办法喽。 |
|
22
suspended OP @binux 添一个能搞定之后，添多个不就是一个一个添喽。:D
局部最优当然不保证全局最优。全局最优根本不可能实现，因为是个 N-P 问题啦。全局较优是外围算法来负责的，我这个问题里的算法只是全局算法里的一个步骤而已。因为论文里面这个步骤的算法没有交代，自己琢磨了几个小时也只有穷举的办法，所以才拿上来请教一下诸位同仁。 |
 |
24
yangyaofei 2016-12-03 23:10:32 +08:00 via Android
这个……是为了更省料的切割方法？
|
|
25
suspended OP @yangyaofei 是滴是滴，除了省料，还要好切
|
|
26
SCaffrey 2016-12-03 23:51:21 +08:00 via iPad
既然 1000 那么枚举放的位置不就是很妙了吗 XD
如果每次查询的小矩形规格是定值的话似乎可以预处理一波吧 |
Select Language