The quarter-state-sequence floorplan representation
The quarter-state-sequence floorplan representation
复制标题
四分之一状态序列布局图表示
DOI：
10.1109/tcsi.2003.809442
复制
发表时间：
2003
影响因子：
5.1
通讯作者：
D. Mehta
中科院分区：
文献类型：
--
作者：
K. Sakanushi;Y. Kajitani;D. Mehta
边界框的平面图是通过水平和垂直的部分将其分割成矩形（房间）。本文提出了一种称为四分之一状态序列（或Q序列）的字符串数据结构来表示平面图。Q序列是沿Abe顺序的房间状态的连接，并且与VH图有关，VH图是垂直约束图和水平约束图的结合。证明了在O(n)时间内，任意n个房间的平面图都是由Q序列唯一编码的，任意Q序列都是唯一解码为平面图的。给出了计算不同平面图的精确公式，并与现有边界进行了比较。定义了一个Q序列到另一个Q序列的线性时间变换。实现了一种基于模拟退火的n房间包装算法，并与现有的包装算法进行了比较。
A floorplan of a bounding box is its dissection into rectangles (rooms) by horizontal and vertical segments. This paper proposes a string data structure called the Quarter-state sequence (or Q sequence) to represent the floorplan. The Q sequence is a concatenation of the states of rooms along the Abe order and is related to the VH graph, which is the union of the vertical-constraint and horizontal-constraint graphs. It is proved that any floorplan of n rooms is uniquely encoded by a Q sequence and any Q sequence is uniquely decoded to a floorplan, both in O(n) time. An exact formula for counting distinct floorplans is given and compared with existing bounds. A linear time transformation of one Q sequence to another is defined. An n-room packing algorithm based on simulated annealing was implemented and found to compare favorably with existing packing algorithms.
Shigetoshi Nakatake：“基于 BSG 结构的模块打包”
DOI：
--
发表时间：
--
期刊：
影响因子：
--
作者：
通讯作者：
--