文章基本信息

标题：Free Space Modeling for Placing Rectangles without Overlapping
本地全文：下载
作者：Marc Bernard ; François Jacquenet
期刊名称：Journal of Universal Computer Science
印刷版ISSN：0948-6968
出版年度：1997
卷号：3
期号：6
页码：703-720
出版社：Graz University of Technology and Know-Center
摘要：The placement of rectangular objects without overlapping on a bounded surface is a generic problem that may have many applications. Space planning, chipset placement, cutting-stock problems, point-feature label placement, or the placement of articles on a newspaper page, are all instances of this more abstract problem. All these applications are concerned with the insertion of rectangular objects on a part of a bounded free surface. It is therefore important to be able to efficiently model the free space of the bounded surface. In this article we present a method to compute free space. The method is based on an iterative insertion process. Our algorithm neither depends on the size of the object to insert, nor on the method of placement. The first feature improves efficiency, while the second allows us to compare different placement methods, and to parameterize the placement system using resolution heuristics.