A slicing floorplan is a decomposition of a rectangle with horizontal and vertical sides using horizontal and vertical cuts (see Figure 7.24(a)). A slicing floorplan can be represented by a binary tree, called a slicing tree, whose internal nodes represent the cuts, and whose external nodes represent the basic rectangles into which the floorplan is decomposed by the cuts (see Figure 7.24(b)). The compaction problem is defined as follows. Assume that each basic rectangle of a slicing floorplan is assigned a minimum width w and a minimum height h. The compaction problem is to find the smallest possible height and width for each rectangle of the slicing floorplan that is compatible with the minimum dimensions of the basic rectangles. Namely, this problem requires the assignment of values h(v) and w(v) to each node v of the slicing tree, such that

Design a data structure for slicing floorplans that supports the following operations:
• Create a floorplan consisting of a single basic rectangle
• Decompose a basic rectangle by means of a horizontal cut
• Decompose a basic rectangle by means of a vertical cut
• Assign minimum height and width to a basic rectangle
• Draw the slicing tree associated with the floorplan
• Compact the floorplan
• Draw the compacted floorplan

Data from in Figure 7.24

Transcribed Image Text:

w(v) = h(v) = W if v is an internal node associated with a max (w(w), w(z)) horizontal cut with left child w and right child z w(w) +w(z) h if v is an external node whose basic rect- angle has minimum width w h(w) +h(z) if v is an internal node associated with a vertical cut with left child w and right child z if v is an external node whose basic rect- angle has minimum height h if v is an internal node associated with a horizontal cut with left child w and right child z if v is an internal node associated with max(h(w),h(z)) a vertical cut with left child w and right child z