The quarter-state-sequence floorplan representation

Abstract

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.