Project1

标题: 求一个自动排版算法 [打印本页]

---

作者: zh99998    时间: 2009-10-4 21:15
标题: 求一个自动排版算法
所谓自动排版，就是描绘一个界面，它的里面的内容不是固定的，而是放在一个变量里
为了说明方便，以下拿RM的界面来举例，事实上只要能获取到那些坐标就行，先不用考虑描绘

比如现在有这么一段数据
data={"名称" => [130,20] "图标" => [32,32], "说明"=>[276,20], "动画"=>[130,20], "售价" => [60,20], 命中率=>[60,20],"能力值变化" =>{"攻击力"=>[60,20],"防御力"=>[60,20],"精神力"=>[60,20],"敏捷性"=>[60,20]},"属性"=>[106,285]},"状态变化"=>[106,285],"备注"=>[228,218]}

range_width=524 #这个是总描绘区域的宽度，高度不限

嗯……就是求一段脚本或者思路，提交上面那种的数据，返回每个元件的xy值
[line]1[/line]如果，可能描绘的框框的长宽是固定的几种，而不是随意的，会不会简单一些

---

作者: 小幽的马甲    时间: 2009-10-4 21:26
这个Hash的value是啥- -

---

作者: 沉影不器    时间: 2009-10-4 23:22
提示: 作者被禁止或删除 内容自动屏蔽

---

作者: zh99998    时间: 2009-10-5 06:46
hash的值是尺寸

单行的当然是没什么算法，按间距排起来就行了
不过像这种只是限定总宽度的多行并且不规则的排版- -完全想不到什么算法

---

作者: 123955763    时间: 2009-10-5 07:39
提示: 作者被禁止或删除 内容自动屏蔽

---

作者: zh99998    时间: 2009-10-5 10:55
我是想做可变的界面

---

作者: 胖达达人    时间: 2009-10-5 11:19
先排第一行，无法完成一个系列则排第一列，完成一个系列后立即换行，或者排满后换到第二行，依次类推

---

作者: zh99998    时间: 2009-10-5 11:25
没有固定的一行一行的，比如右侧那两个纵栏
用这个图也许更能说明问题

---

作者: link006007    时间: 2009-10-5 11:34


习惯按tab键缩进了，，， 结果回帖了- -
还是说下吧 - -
这种排版有点向2D矩形的碰撞检测一样。。。
所有的矩形都停在不会与其他任何一个矩形接触的地方
白痴点的方法就是
这个就先要生成一个矩形序列。然后按行或列或者其他的方法顺序安放矩形，
然后下一个要安放的矩形和前面已经安放的矩形逐一进行碰撞检测。直到找到一个不会与前面矩形碰撞的地方
不知道是不是这个样子。。

---

作者: zh99998    时间: 2009-10-5 11:50

这个就先要生成一个矩形序列。然后按行或列或者其他的方法顺序安放矩形

这一句不是很明白0.0

---

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

---

作者: 胖达达人    时间: 2009-10-5 12:02

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

NOIP做多了吧……= =

---

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

---

作者: link006007    时间: 2009-10-5 12:11


伪代码。。
不知道如何用语言表达。。。。
效率很低的循环嵌套 - -。。。
效率应该在功能实现后在考虑。
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

---

作者: 小幽的马甲    时间: 2009-10-5 12:14
目的不是要尽可能拼成矩形么，所以元件之间的间距也是很重要的…

---

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

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

---

作者: zh99998    时间: 2009-10-5 12:23

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

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

---

作者: 九夜神尊    时间: 2009-10-5 13:01
我倒是有一个好的不能再好的办法了

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

---

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

---

作者: zh99998    时间: 2009-10-5 13:48
关于【固定大小】的意思是说，指定确定下几个长宽
[130,20]
[60,20]
[12,12]
[108,280]
[32,32]
这就是所有可能的框框的长宽，也就是说框框的长宽只能在这里面取值，这样是不是能简便一些
[line]1[/line]
然后，小的拼大的在楼顶的问题中其实就有的
仔细看的话有这么一部分

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

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

---

作者: 小幽的马甲    时间: 2009-10-5 14:09
那么…一开始对同一大小的元件计数，然后分解成两个数的积，枚举，这样只剩五个元件了，然后再排…缺点是所有相同大小的元件都会聚在一起…这样真的可以么？

---

作者: zh99998    时间: 2009-10-5 14:10
貌似这样会严重不美观，空间利用率也比较低- -

---

作者: 小幽的马甲    时间: 2009-10-5 14:16
对于某个状态，把它和当前状态下完整的矩形的补集分成几个小矩形，元件能往里塞就塞…

---

作者: zh99998    时间: 2009-10-5 15:04
貌似是个好主意，先把几个大的确定好，然后找空塞小的[line]1[/line]原理虽然找到了- -不过要写算法依然没什么思路0.0

---

作者: 九夜神尊    时间: 2009-10-5 19:06
八神都不会的，我九神就更别说了

---

作者: 小幽的马甲    时间: 2009-10-5 19:24
最开始的时候整个矩形是0，0，544，MaxH
然后新加一个元件w,h……这样就分成[w，0，544-w，MaxH]及[0,h,544-w，MaxH]两个了
我这是竖着切……当然你要横着切也行
然后用队列递归调用，分别遍历所有矩形，直到队列为空。

---

作者: 九夜神尊    时间: 2009-10-5 19:37
想到一个有趣的

LZ知道吧一大堆杂物，放在一个箱子里面
刚开始体积会很大。你把那个箱子抖几下
空间利用率就会有一定的提升
体积就会缩小。

提出一个新的词吧：可配元

假设窗体宽是 100
一个窗口的宽如果是 60
，那么所有宽小于40的都可以和这个窗体成为可配元。
高也一样。
可配元评分
两个可配元都放入窗体以后，剩下的空间越接近矩形，那评分越高
当然也不排除是3个或更多

组合元
组合元是分级的。两个窗体之间，如果长宽其中一项相近
那么着两个窗口就可以组成新矩形。

先拼入可配评分高的组合元。如果评分时满分，那么以后就不用考虑这两个窗口了
再同样的方法考虑剩下的矩形！

当然实际上的核心，就是你写怎么样吧多个窗口组合成一个新的近似的矩形。

---

作者: x387804363    时间: 2009-10-5 20:07
LS好强

---

作者: zh99998    时间: 2009-10-5 20:18
能看懂一些了，矩形评分这倒是很好的思路
不过又有个问题，这些控件大部分都是很小的，并不是一个控件占%60，然后挑小的往里塞的那种
随便拿出一个控件，可能所有其他控件都会成为他的可配元
然后我就就不会评分了……

---

作者: link006007    时间: 2009-10-5 20:54


汗。 越来越专业了啊。。。
还是当成矩形碰撞检查比较简单=  =， 这是在做游戏还是做GUI库啊
可配元什么的  是不是要把较小矩形按照较大矩形为界限对齐拼凑。。
差不多就是要‘预知整体布局’。。。
这里有很多布局方式。。 lz可以参考
http://java.sun.com/docs/books/t ... /layout/visual.html
这里是一种布局的源代码。。 一个通用的布局代码还是很长的-  -
http://sourceforge.net/projects/pagelayout/files/
坦白的说。。。。 好像很复杂- -

---

作者: zh99998    时间: 2009-10-5 21:01
是在做GUI库

LS的链接是Java语吗- -求能看懂的

---

作者: 沉影不器    时间: 2009-10-5 21:56
提示: 作者被禁止或删除 内容自动屏蔽

---

作者: link006007    时间: 2009-10-5 23:20
算法的话差不多把 （当然里面残渣了很多UI类）
布局最多的就是Java的了。。
其他。net的ms本身几乎不开源

---

作者: zh99998    时间: 2009-10-6 06:06

如果间距固定值就很可能无结果...如果在一定范围内取间距值,那就用极大值深度优先搜索了
沉影不器 发表于 2009-10-5 21:56

间距吗……就设个最小间距10，大了不限

---

作者: 小幽的马甲    时间: 2009-10-6 09:45
最后在某一行放不下时，把总宽减元件宽和，再除以元件数减一就是列间距了…

---

作者: zh99998    时间: 2009-10-6 12:40
还是固定值会比较整齐一些吧
[line]1[/line]
另外还有一个难题就是，怎么保证界面尽量的稳定，也就是尽量不要改动一点点数据就让整个界面布局大改变

---

作者: 九夜神尊    时间: 2009-10-6 14:12


我有一个新的想法，就是试排（适用于窗口较少）
按照数学组合的方式。按不同顺序依次试着排入窗口
（如果有10个窗口就可能要排1*2*3*4*5*6*7*8*9*10次）
然后再算总的面积！

虽然以上方法似乎乱扯，但是加入一些人工智能可以智能去除一些显然
不和逻辑的排法！
好！
以下写算法步骤
假设10个窗口
获取第一个排入顺序 顺序为 1 2 3 4 5 6 7 8 9  10
排入第一个 1
在第一个的右边排入第二个     ←-------------------------------                                   
分歧 如果可以放进去            |                                    |         
       在往右边排第三个 ————                        |   
    如果放不进去                                        |
       计算空出来的面积                                 |
          case 面积                                    |
           when  太大                                 |
              直接否认 前两位为 1 2 的窗体组合         |
           when  不算太大                             |
              在下方排入 下一个窗口（接着返回前面的步骤计算）              end   
排版结束
   计算空间使用率。（使用面积，和窗口面积之比）
        if  若还有很大的残留空间
            均匀分布每个窗体
          else
                 记录下使用率
            进行新的排版
          end
够智能化吧
只不过算的真的有一点点慢

---

作者: 小幽的马甲    时间: 2009-10-6 14:16
阶乘级的算法...这不就是枚举么= =

---

作者: 九夜神尊    时间: 2009-10-6 14:32
当然可以根据需求调节
比如有的需求是，放进去就行。
  那样成功排入一次就结束运算
有的要限制空间使用率
  这样要多算一些
还有的呢要最佳使用率
  那就是要算完对比

---

作者: zh99998    时间: 2009-10-6 18:18
关于那个预知整体布局，可以这么来弄
首先，固定几个特定的控件，比如【名称】一定在左上角，【备注】一定在右下角，【属性】和【状态】一定在右上角，并且它们的大小也固定，那么，一旦出现带这些特定名字的，就直接安放上不用动了
然后，比较大的靠右靠下，小的靠左靠上，然后难点就是像截图里的那种【能力值变化】那种组合框怎么办，可能有两种排列，即2*2和四个排成一纵行(为了减小一些可能性，四个以上的时候禁用单行横向排)

---

作者: link006007    时间: 2009-10-6 19:22
ms很复杂哦... ...  
我看了很多布局... ms没有什么可以直接表明算法的(能力不够吧 - -),
n种布局,m中算法 -  -!

我觉得还是简单点就用水平对齐和垂直对齐的自动布局比较好...
首先由一个容器类, 它可以把它里面的控件在一个矩形类简单的进行诸如水平或垂直的布局
然后复杂的布局有这些简单的布局混合而成...
这样lz要写的代码就会简单而且少很多, 然后用户自己组合这些布局(也就是整体布局是用户自己给定的,而不需要我们在代码中里面判定...)或者你可以给定几个布局模板同样有水平或垂直布局的矩形块组成

如果要让一个矩形容器里面空间利用率高的话,lz可以参考 数据结构 中的 装箱问题
不过会比实际的装箱问题复杂的多(自己尝试写了下...个人感觉).. 因为控件的w,h都是未知的... 如能确定其一那就简单多了(我的意见是垂直布局时忽略水平..水平时忽略垂直)= =
这样虽然不会有智能的布局... 但是其实大多数布局都是如此.. 你可以尝试自己在Java的swing或者C#里面拖控件感受下

---

作者: zh99998    时间: 2009-10-6 19:29
控件的w,h都是已知的啊
还有我不太明白【垂直布局时忽略水平..水平时忽略垂直】是什么意思
需要的是水平有一定限度，比如600，垂直无限大(一根滚动条)，但是为了美观，垂直尽量不要占用太大空间，不知道这是不是【忽略垂直】

---

作者: link006007    时间: 2009-10-6 19:38


我说的未知的意识是... 可变的 - -
也就是.. 如果在同一个容器中所有控件的w,h其中一个是一样的值,那么装箱问题就会简单很多
忽略是:
如果只是依照水平也就是w来布局,那就不要管h...等到在水平上的空间利用率达到最高,在看看如何处理h

装箱问题的代码多的是, 你可以吧每一行看做一个箱子,然后控件的w作为装入箱子的元素, 依照装箱的算法,那么你在水平上的空间利用率就会很高(最高可能没有...  ms主流的装箱算法都不能保证最优装载)
如果同时考虑垂直.. 那会很复杂..水平得到的控件排序基本不可用

---

作者: zh99998    时间: 2009-10-6 19:48
是这个意思啊……那貌似就就不上装箱算法了
那个已知的的意思是，虽然可变，但是只能在几个固定的长宽中取值

然后优先安排好几个大的之后，也许就能用27楼那个可配元·组合元·矩形评分法了？

---

作者: link006007    时间: 2009-10-6 23:27
不知道呃。。。
可配元什么的 还是问27楼的同学吧

---

作者: 九夜神尊    时间: 2009-10-7 09:18


电脑的智能是建立在人工智能只上的。
先考虑一下如果给你一大堆方块，在给你一个大的桌子
让你把这些方块摆进去
你会怎么摆？

通常我想方法的时候，就是在想，如果是叫我自己去做
而不是用电脑算的话，我会怎么做，这样得到的可以说是最简练的

好吧，就你这个叫我去做我会怎么做呢 ？

首先，面对一大堆的方块，我会首先把他们拼成一个较大的，再拼成更大的
再往里面放，如果放不进去，就考虑吧某一个组合好的方块换一个
组合方式，减少一点大小。再放进去。

如果叫你来摆，你觉得你会一看就知道怎么摆么。一个一个摆
的话人的智能会被加进去么　？　

---

作者: 小幽的马甲    时间: 2009-10-7 10:08
根据图灵某理论，越高级的AI，空间复杂度越高，也就是代码很难写

---

作者: zh99998    时间: 2009-10-7 11:12
如果让我来摆呢，首先像上面说的固定好特定名字的和很大的在右下方之后，就拿那些小的往里塞，以美观为标准进行尝试，区别在于人类是一看就能知道美不美的，而电脑不知道……

---

作者: IamI    时间: 2009-10-7 11:17
路过悄悄地说……难道你一定要算出(Math.sqrt(5) - 1)/2的结果到小数点后20位吗(⊙_⊙)？

---

作者: zh99998    时间: 2009-10-7 11:21
什么意思？

---

作者: 小幽的马甲    时间: 2009-10-7 12:22
那个是黄金分割吧=v=

---

作者: zh99998    时间: 2009-10-7 12:59
………………………………………………
II，我说的界面的美观不是黄金分割啊……………………

---

作者: 九夜神尊    时间: 2009-10-7 13:15
怎么说电脑不知道美不美呢？

只要你会写，电脑就能知道美不美！
或者说电脑不知道哪一个美，但是可以大致判断出来哪一个明显不美
（这个还是有规律可询的，就好比我们都知道红色配绿色，或者红色配蓝色没有什么修饰）
然后嘛！
还不知道美不美的话，生成多个版面，让用户选择！

---

作者: zh99998    时间: 2009-10-7 13:19
嗯，这个判断美就是这个算法的核心了吧，可以再详细的说一下那个矩形评分规则吗
现在的情况是，已经可以预知部分布局，即有一部分已经可以有确定的位置给他安放了，另外的小矩形跟这些安放好了的进行评分

---

作者: 小幽的马甲    时间: 2009-10-7 16:31
我还是觉得这是NP完全问题，不存在时间复杂度为多项式的算法。阶乘级的算法再怎么优化还是慢，就算按每秒一亿次来排16个元件，也要2.42天才能完成…

---

作者: 九夜神尊    时间: 2009-10-7 18:06

---

作者: zh99998    时间: 2009-10-7 18:08
很……强大……

---

作者: 九夜神尊    时间: 2009-10-7 18:10


计算过程就是不断地拆分，组合以尽量让剩下的空间接近矩形。
以求得更高的评价分数
根据你现有的，某些窗口有的固定的排法那
就把那个窗口独立不进行组合。
实际上组合完了也就2-3个窗口了
再加上不组合的。也不会很多
那2-3个窗口就不断地组合拆分。
可以知道已经放进去的矩形的空间利用率是相当高的。
如果从美观方面考虑，就要考虑在组合的时候禁止什么样的组合

---

作者: link006007    时间: 2009-10-7 21:50

我还是觉得这是NP完全问题
小幽的马甲 发表于 2009-10-7 16:31

对对
就是类似装箱问题

lz考虑的这么复杂然道会有诺贝尔奖= =

---

作者: 小幽的马甲    时间: 2009-10-7 22:41
诺贝尔没有计算机奖…不过给出NP完全的多项式复杂度解拿图灵奖应该没问题吧？

---

作者: zh99998    时间: 2009-10-8 07:00
谢谢各位的帮助，基本上明白了，结帖

---

欢迎光临 Project1 (https://rpg.blue/)

Powered by Discuz! X3.1