E are within the projection area,thus,they may affect the moving process of A.Because F is outside the projection area,it has no effect on the moving process of A.According to this,the following relative positions are defined for two edges. Definition 5:Let and b be two edges parallel to the X-axis.If and bx satisfy (4).ax top-overlaps b otherwise.ax un-top-overlaps bx.Let a and b be two edges parallel to the Y-axis.If a and y satisfy (5),a right-overlaps b;otherwise, un-right-overlaps bY (a0y)≥bGy)and（am(x)>b(x)）and(a(x)<b(xR) (4) (amx)≥b(x)and(a0)>bm0)）and(a0)<b6y) (5) Fig.3 shows various top-overlaps and right-overlaps.As can be seen,in Fig.3(a),the bottom edge of A top-overlaps the top edges of B,C,D,and E;that is,a top-overlaps b,c,d, and e.Similarly,the right-overlaps are shown in Fig.3(b). X X (a) (b) Fig.3.(a)top-overlaps(b)right-overlaps With the intrinsic properties of rectilinear blocks in mind,the appropriate position where a rectilinear block can slide to is determined as follows:let B be a rectilinear block.When B slides leftward,if the ith left edge of B right-overlaps some placed edges,then,let CoverRightXi be the X-coordinate of the right-most edge right-overlapped by B(LE); otherwise,let CoverRightX;be 0.Thus,the distance that B can slide leftward is the minimum 16
16 E are within the projection area, thus, they may affect the moving process of A. Because F is outside the projection area, it has no effect on the moving process of A. According to this, the following relative positions are defined for two edges. Definition 5: Let a//X and b//X be two edges parallel to the X-axis. If a//X and b//X satisfy (4), a//X top-overlaps b//X; otherwise, a//X un-top-overlaps b//X. Let a//Y and b//Y be two edges parallel to the Y-axis. If a//Y and b//Y satisfy (5), a//Y right-overlaps b//Y; otherwise, a//Y un-right-overlaps b//Y. ( )( ) ( ) //X //X //X //X //X //X ( ) ( ) and ( ) ( ) and ( ) ( ) RL LR ab a b a b yy x x x x ≥> < (4) ( )( ) ( ) //Y //Y //Y //Y //Y //Y ( ) ( ) and ( ) ( ) and ( ) ( ) T B BT ab a b a b x ≥> < x yy yy (5) Fig.3 shows various top-overlaps and right-overlaps. As can be seen, in Fig.3(a), the bottom edge of A top-overlaps the top edges of B, C, D, and E; that is, a top-overlaps b, c, d, and e. Similarly, the right-overlaps are shown in Fig.3(b). Fig.3. (a) top-overlaps (b) right-overlaps With the intrinsic properties of rectilinear blocks in mind, the appropriate position where a rectilinear block can slide to is determined as follows: let B be a rectilinear block. When B slides leftward, if the ith left edge of B right-overlaps some placed edges, then, let CoverRightXi be the X-coordinate of the right-most edge right-overlapped by //Y ( ) B LEi ; otherwise, let CoverRightXi be 0. Thus, the distance that B can slide leftward is the minimum
difference between the X-coordinate of B(LE)and CoverRightXi,where 0si<B(LEY D).The case when B slides downward similarly uses CoverTopY;instead of CoverRightXi.The sets of CoverRightXi and CoverTopY;i are labeled as CoverRightX and CoverTopY,respectively.Algorithm 1 describes the algorithm transforming an MBS to a floorplan. Algorithm 1:Algorithm transforming an MBs to a floorplan Input:MBS:MBS=(,IP)EMBS: Output:F(B),where B={Bo,B1,...,Bn-1); BtoTx and LtoR denote two ordered sets of edges parallel to the X-and Y-axis, respectively.They are used to record the top edges from bottom to top and the right edges from left to right of the blocks that have been placed.(widthg,and heights are the same as those of Definition 1. (x,）←(00) (xBowRT,yBaR←(width.,height方 Add the top edges of into BtoT Add the right edges ofinto LtoR; for(i=1;i<n;i←it1) switch (IPi) case 0: 个
17 difference between the X-coordinate of //Y ( ) B LEi and CoverRightXi, where //Y 0 (| |) ≤ <i B LE . The case when B slides downward similarly uses CoverTopYi instead of CoverRightXi. The sets of CoverRightXi and CoverTopYi are labeled as CoverRightX and CoverTopY, respectively. Algorithm 1 describes the algorithm transforming an MBS to a floorplan. Algorithm 1: Algorithm transforming an MBS to a floorplan Input: MBS: MBS=(π, IP)∈MBS; Output: F(B), where B={B0, B1, …, Bn-1}; BtoT//X and LtoR//Y denote two ordered sets of edges parallel to the X- and Y-axis, respectively. They are used to record the top edges from bottom to top and the right edges from left to right of the blocks that have been placed. ( , ) LB LB x y B B , widthB, and heightB are the same as those of Definition 1. { ( ) ( ) 0 0 , 0, 0 LB LB x y π π ← ; (x BoxRT, y BoxRT) ← ( 0 widthπ , 0 heightπ ); Add the top edges of π0 into BtoT//X; Add the right edges of π0 into LtoR//Y; for (i = 1; i < n; i ← i+1) { switch (IPi) { case 0: