李治江，崔广勋，王嵩

1.武汉大学印刷与包装系，湖北武汉430079

2.高德软件有限公司数据研发中心，北京102200

基于矩形Packing问题求解的页面自动排版方法

李治江1，崔广勋1，王嵩2

1.武汉大学印刷与包装系，湖北武汉430079

2.高德软件有限公司数据研发中心，北京102200

为了较好地实现页面的自动排版，本文提出了基于矩形Packing问题求解的页面自动排版方法。该方法采用结构化描述语言来分析描述版面的图文内容及排版样式，通过构建页面模型把页面自动排版问题抽象为关于图文混排矩形块的版面布局自动规划问题，根据矩形块面积排序，判断约束信息，定位步骤和回溯步骤，得到最终的页面自动排版效果。通过页面数据排版实验进行测试，实验验证该方法能较好地符合条件要求。

自动排版；矩形Packing

1　引言

随着互联网的发展，信息量的膨胀，电子设备的普及和环保无纸化观念的推广，网络出版以其效率更高、价位更低、检索快捷、避免绝版等优点不断冲击着传统出版市场，传统出版向网络出版转型是出版行业发展的趋势［1-3］，自动排版的实现将缩短排版工序用时，为出版行业带来产业化的效益提升。

近年来不少学者对排版问题进行了研究，取得了一些成绩［4-11］。如张金美介绍了CorelDRAW12在排版中的应用和技巧［4］；王勇等分析比较了LaTeX和方正书版2种软件排版数学论文的特点［5］；李金城等利用JavaScript在Indesign中实现基于XML结构化文档的自动排版［6］；肖建国等关注XML技术在跨媒体领域的应用［7-9］；苏勇的专利根据给定的固定栏数、栏距、页面区域面积等信息进行自动图文排版，不适用于页面含有多个信息块的复杂情况［10］；……