求一个自动排版算法

小幽的马甲

这如果作为算法题的话绝对是IOI水平的…我也像过枚举、贪心、搜索、动态规划但无一例外存在反例。或许把元件作为凸包用计算几何＋floodfill可以实现吧？但这不是我擅长的…另外我越看这个越觉得像NP完全问题…

胖达达人

这如果作为算法题的话绝对是IOI水平的…我也像过枚举、贪心、搜索、动态规划但无一例外存在反例。或许把元件作为凸包用计算几何＋floodfill可以实现吧？但这不是我擅长的…另外我越看这个越觉得像NP完全问题… ...
小幽的马甲 发表于 2009-10-5 11:57

NOIP做多了吧……= =

zh99998

如果，可能描绘的框框的长宽是固定的几种，而不是随意的，会不会简单一些

link006007

伪代码。。
不知道如何用语言表达。。。。
效率很低的循环嵌套 - -。。。
效率应该在功能实现后在考虑。
def collisionDetect2D (obj1, obj2)
end

# objList 你所有要安放的控件的列表
def sort (objList, maxX, maxY)
    i = 0;
   while (i < objList.length)
        x = y = j = 0;
        # 和前面的进行碰撞检测
     while (j < i)
            # 假设当前的有效位置
        objList.setRect(x, y, objList.w, objList.h)
            if (collisionDetect2D(objList[j], objList))
                 #重设x，y  这里就是你排版的规则 如按y
                y = objList[j].y + objList[j].h + 间隙
           if (y > maxY)
                     y = 0；
                     #y满了就设置x坐标
              x = 。。。 。。。
           end
           else
                 j++;
           end
        end
        i++;
    end
end

小幽的马甲

目的不是要尽可能拼成矩形么，所以元件之间的间距也是很重要的…

link006007

尽量排成矩形
你可以计算剩余间隙然后来平分间距
不过这样的话。。 你的间距就是一个不固定的有大有小  很难看 = =
除非你已开始就能预计出整体布局

这个应该去看看Java Swig的源代码
那里面有很多的控件布局方式 哈哈。。

zh99998

如果，可能描绘的框框的长宽是固定的几种，而不是随意的，会不会简单一些
zh99998 发表于 2009-10-5 12:07

使用固定的这一条件，能否先安排一些大的，比如截图中那竖着的两条先摆在右边，也算是一种预计整体布局？

九夜神尊

我倒是有一个好的不能再好的办法了

ＬＺ是不是可以参考一下HTML语言呢？

小幽的马甲

感觉固定大小其实没有什么实质作用…比如宽限定5，元件分别是[1,3]、[1,4]就排不了…能否排好关键是看最大公约数。剩下要看的就是如何尽可能拼成长方…元素之间的间隔是一个要好好利用的。其次也可以考虑把几个小的元件拼成一个大的元件，这样可能会方便些…

zh99998

关于【固定大小】的意思是说，指定确定下几个长宽
[130,20]
[60,20]
[12,12]
[108,280]
[32,32]
这就是所有可能的框框的长宽，也就是说框框的长宽只能在这里面取值，这样是不是能简便一些

---

然后，小的拼大的在楼顶的问题中其实就有的
仔细看的话有这么一部分

"能力值变化" =>{"攻击力"=>[60,20],"防御力"=>[60,20],"精神力"=>[60,20],"敏捷性"=>[60,20]},"属性"=>[106,285]}

这四项数据是弄在一起的，那么只能有四种情况，横排四个，竖排四个，横2竖2