怎么将零散的图元尽可能小占面积的集中在一起

风树

希望能有基本lsp语言实现的代码出现，好通用

llsheng_73

风树 发表于 2013-11-8 10:34
想到的思路就是上面说的，假设先模拟缩小一半的情况去算一下有没有碰撞，没有再缩小一半，直到发现碰撞， ...

好象这样有个问题就是最终明明有能放下一些图元的地方却没图元放那去

风树

llsheng_73 发表于 2013-11-8 11:53
好象这样有个问题就是最终明明有能放下一些图元的地方却没图元放那去

那就换个思维，可以局部改善这种情况
近似解法：
1、人为的给所有图元按其在y方向上的高度分组
2、人为的指定你要排布在某个矩形范围内的x方向上的长度（要试算）
3、把要排布在某个矩形范围内y方向上按分组高度分行
4、对分行参考背包问题的思路，求出每行的最优排布(或规模不大，暴力算法也性）
5、为排除出现特定的分组高度可能占用多行，且最后一行只有一两个图元的情况，也就是说第二步要试算
6、相对结果能接近你的要求，但可能存在在你试算的过程中，不同分组高度之间会交叉出现第五步的情况，所以最后要人为的修正。
补充：
或者在第五步时对剩余空间再进行第三步，直到剩余空间内不能再分行时，转入下个分行进行计算，这样合理一些。

llsheng_73

风树 发表于 2013-11-8 12:24
那就换个思维，可以局部改善这种情况
近似解法：
1、人为的给所有图元按其在y方向上的高度分组

这个思路有点意思了，谢谢风树兄弟
同时也希望大家多支下招，谢谢了！！！

langjs

一个排料软件要万八元钱，算法很多也相当复杂，靠lisp基本没辙，还是省省吧

风树

楼主也没有说要求最优解，应用要求也低，可想规模也不大；
应用范围不涉及到效益问题，多点少点也没有多大问题；
近似得能接受就行
所以也谈不上真正意义的排料问题吧

风树

楼主要处理的地理要素含相对位置关系，处理后的图应该体现出这种关系吧？

如果一点也不考虑位置关系，就把各图元看成一个个矩形，要求它们排布得整整有齐，总占用面积最优，那就是上面说得布料问题，要考虑的特殊情况很多。

如果只是想让它们相对规整的排一下，那13楼的思路应该还是合适的。
13楼的思路来源于：
HDU 2795 Billboard
/*
题意：在一块公告板上贴公告，公告的高为一个单位值（设为1），宽自己输入；规定每次贴公告，满足贴在第一：最上面，第二：最左边。然后输出每一次贴公告，公告贴在第几行。（行数：从高到底）；
*/

但不能直接套用，数据要预处理。

感觉做示意图还是按第一个思路考虑合适，不同的用途，不同的处理。

soly2006

期望有解。
就是图形方向不变排料。

haoryh

帮顶，争取顶出解决方案来！

haoryh

langjs 发表于 2013-11-9 13:25
一个排料软件要万八元钱，算法很多也相当复杂，靠lisp基本没辙，还是省省吧

确实有专门的排料软件！