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

山东农业大学学报(自然科学版),2016,47(2):264-268 VOL.47 NO.2 2016 Journal of Shandong Agricultural University ( Natural Science Edition ) doi:10.3969/j.issn.1000-2324.2016.02.020 基于矩形 Packing 问题求解的页面自动排版方法 李治江 1,崔广勋 1,王 嵩 2 1. 武汉大学 印刷与包装系, 湖北 武汉 430079 2. 高德软件有限公司 数据研发中心, 北京 102200 摘 要: 为了较好地实现页面的自动排版，本文提出了基于矩形 Packing 问题求解的页面自动排版方法。该方法采用 结构化描述语言来分析描述版面的图文内容及排版样式，通过构建页面模型把页面自动排版问题抽象为关于图文混 排矩形块的版面布局自动规划问题，根据矩形块面积排序，判断约束信息，定位步骤和回溯步骤，得到最终的页面 自动排版效果。通过页面数据排版实验进行测试，实验验证该方法能较好地符合条件要求。 关键词: 自动排版;矩形 Packing 中图法分类号: TS812+.2 文献标识码: A 文章编号: 1000-2324(2016)02-0264-05 AutomaticPageLayoutBasedonSolutionforRectangularPackingProblem LI Zhi-jiang1, CUI Guang-xun1, WANG Song2 1. Department of Printing and Packaging/Wuhan University, Wuhan 430079, China 2. Data Research and Development Center/AutoNavi Software Co. Ltd., Beijing 102200, China Abstract: In order to realize automatic page layout, a method based on rectangular packing problem was proposed. It was described the graphics, texts and layout style of pages through the Structural language. The automatic page layout problem was formalized as a rectangle packing blocks with image-text contents to obtain the final automatic page layout effect according to sorting the areas of rectangles, judging constraint information, positioning each rectangles and backtracking algorithm. Experiment was carried out by using the page layout data and the result was able to well match the requirements. Keywords: Automatic page layout; rectangle Packing 1 引 言 随着互联网的发展，信息量的膨胀，电子设备的??及和环保无纸化观念的推广，网络出 版以其效率更高、价位更低、检索快捷、避免绝版等优点不断冲击着传统出版市场，传统出版 向网络出版转型是出版行业发展的趋势[1-3]，自动排版的实现将缩短排版工序用时，为出版行 业带来产业化的效益提升。 近年来不少学者对排版问题进