% Fitting blocks into a box, planar version % This program appears as Figure 7.4 in I. Bratko, Prolog Programming for AI, 4th edition, Pearson 2011 :- use_module( library(clpr)). % Placing blocks into a rectangular area % Blocks are to be aligned with the sides of the rectangular area, i.e. with x,y axes % block( BlockName, dim(Width, Length)). block( b1, dim( 5.0, 3.0)). % Block b1 has size 5 by 3 block( b2, dim( 2.0, 6.0)). block( b3, dim( 1.0, 2.4)). block( b4, dim( 1.0, 5.0)). box( box1, dim( 6.0, 6.0)). % Box box1 has size 6 by 6 box( box2, dim( 7.0, 5.0)). box( box3, dim( 30.0, 30.0)). % A large box that accomodates all possible distributions of blocks box( box4, dim( 6.0, 5.0)). % Representation of rectangles: % Term rect( pos(X,Y), dim(A,B)) represents a rectangle of size AxB at position pos(X,Y) % rotate( Rectangle, RotatedRectangle): % Rotation of rectangle in X-Y plane , always aligned with X-Y axes % There are just two cases: original orientation, or rotated by 90 degrees rotate( rect( Pos, Dim), rect( Pos, Dim)). % Zero rotation rotate( rect( Pos, dim( A, B)), rect( Pos, dim( B, A))). % Rotated by 90 degrees % block_rectangle( BlockName, Rectangle): % Rectangle is a minimal rectangle in X-Y plane that accommodates block BlockName block_rectangle( BlockName, rect( Pos, Dim)) :- % Rectangle at any position block( BlockName, Dim0), % Dimensions of BlockName rotate( rect( Pos, Dim0), rect( Pos, Dim)). % Block possibly rotated by 90 degrees % inside( Rectangle1, Rectangle2): Rectangle1 completely inside Rectangle2 inside( rect( pos( X1, Y1), dim( Dx1, Dy1)), rect( pos( X2, Y2), dim( Dx2, Dy2))) :- { X1 >= X2, Y1 >= Y2, X1+Dx1 =< X2+Dx2, Y1+Dy1 =< Y2+Dy2}. % no_overlap( Rect1, Rect2): Rectangles Rect1 and Rect2 do not overlap no_overlap( rect( pos(X1,Y1), dim(Dx1,Dy1)), rect( pos(X2,Y2), dim(Dx2,Dy2))) :- { X1 + Dx1 =< X2; X2 + Dx2 =< X1 ; % Rectangles left or right of each other Y1 + Dy1 =< Y2; Y2 + Dy2 =< Y1 }. % Rectangles above or below of each other % fit( Box, Block1, Block2, Block3, Block4): % The 4 blocks fit into Box as rectangles Block1, Block2, ... fit( BoxName, Block1, Block2, Block3, Block4) :- box( BoxName, Dim), Box = rect( pos( 0.0, 0.0), Dim), block_rectangle( b1, Block1), inside( Block1, Box), % Block b1 inside Box block_rectangle( b2, Block2), inside( Block2, Box), % Block b2 inside Box block_rectangle( b3, Block3), inside( Block3, Box), block_rectangle( b4, Block4), inside( Block4, Box), no_overlap( Block1, Block2), % No overlap between blocks b1 and b2 no_overlap( Block1, Block3), % No overlap between b1 and b3 no_overlap( Block1, Block4), no_overlap( Block2, Block3), no_overlap( Block2, Block4), no_overlap( Block3, Block4). % Displaying blocks packed in a box (to be used with the program for fitting blocks in a box) % This uses built-in predicates in SWIProlog that interface Prolog % with object-oriented library XPCE for building GUI's % Note: This program may not be the most elegant use of XPCE! % Blocks are specified as rectangles giving their positions in the box and their dimensions: % E.g.: Block4 = rect(pos(0.0, 5.0), dim(5.0, 1.0)) block of dimensions 5x1 % placed at (0,5) relative to top-left corner of the box % show( BoxDimensions, [ Block1, Block2, ...]) % For example: % ?- show( dim(6,6), [ rect( pos(0,0), dim(5,1)), rect( ...), ...]). % Typical use of this program with packing blocks in box is: % ?- fit( box1, B1, B2, B3, B4), show( box1, [B1,B2,B3,B4]). show( Box, Rects) :- ( object( @pic), !, send( @pic, destroy); true), new( @pic, picture('Box', size( 500,400))), send( @pic, open), box( Box, dim( A, B)), AA is 50*A, BB is 50*B, ( object( @box), !, send( @box, destroy); true), new( @box, box( AA, BB)), send( @pic, display, @box, point(30,30)), show_blocks( Rects, [@block1/blue, @block2/red, @block3/green, @block4/violet, @block5/orange, @block6/turquoise]), !. % Up to 6 blocks % show_blocks( Rects, [BlockName1/Color1, BlockName2/Color2, ...]): % display blocks using list of colors Colors and object names of form @block1, % @block2, ... show_blocks( Rects, Blocks) :- destroy_blocks( Blocks), !, % Destroy objects show_blocks1( Rects, Blocks). show_blocks1( [], _). show_blocks1( [ rect( pos(X,Y), dim(A,B)) | Rest], [Name/Color | NamesColors]) :- middle(X, Xmid), middle(Y, Ymid), % X, Y are constrained vars, compute their mid-values XX is 50*Xmid + 30, YY is 50*Ymid + 30, % Enlarge and translate positions to top-left coner of box AA is 50*A, BB is 50*B, % Enlarge the block to become visible new( Name, box(AA,BB)), send( Name, fill_pattern, colour( Color)), wait( 400), % Wait 600 milisec before displaying next block - doesn't have desired effect send( @pic, display, Name, point(XX,YY)), send( Name, flush), show_blocks1( Rest, NamesColors). destroy_blocks( NamesColors) :- % Clear all blocks in NamesColors from possible previous display member( BlockName/Color, NamesColors), object( BlockName), send( BlockName, destroy),fail ; true. middle( X, Xmid) :- sup( X, Xmax), inf(X,Xmin), Xmid is (Xmax+Xmin)/2. % wait( TimeDelay): wait for time TimeDelay [mili seconds] % Note: this may be problematic for short delays like 10 msec wait( TimeDelay) :- statistics( runtime, [StartTime, _]), repeat, statistics( runtime, [Time, _]), Time - StartTime >= TimeDelay.