Proposed Procedure for Building a Polyomino

A Procedure for Generating Floor Plans - Computer Aided Design

NEW PROPOSED PROCEDURE FOR BUILDING A POLYOMINO

I shall now describe a modified and improved method for construction of a polyomino pattern conforming with a set of preferences. The order in which elements will be considered in our construction of the pattern is established from the R matrix. The first couple of elements to be picked will be the ones with lowest R(i,;) value. (referred to hereafter as Link Value) Then the next low link value is chosen etc. The value of R(i,j) for couple i j will only determine which new element is to be added. But, this new element does not have to remain attached the element with which it forms the lowest link value. It can be moved away and, although, in most cases it will remain attached to the element with which it has the lowest link value it might end up at a position which may produce a better pattern.
The table below (Fig. 14) shows such a link value list corresponding to the preferences of the client mentioned and derived from the R matrix.

  k	I	j	R(i,j)		B(i,j)	       Order	Added		Built
-------------------------------------------------------------------------------------------------
 1	1	2	 7.40		1.00		a	1,2		1,2
 2	2	4	 7.40		1.00		b	4		1,2,4
 3	3	5	 8.80		1.00		  d	5		1,2,3,4,5
 4	1	4	10.00		1.40
 5	3	6	11.20		1.40		  e	6		1,2,3,4,5,6
 6	1	3	11.80		1.40		c	3		1,2,3,4
 7	1	6	14.60		2.00	
 8	4	6	14.60		2.00
 9	2	3	15.60		2.00
10	1	5	15.80		2.00
11	2	6	16.40		2.20
12	3	4	16.60		2.20
13	2	5	17.60		2.20
14	5	6	18.00		2.80
15	4	6	20.60		2.80

Fig.14 - Link Value List

The order in which elements will be placed are obvious from the Link Value List.

The couple for which k-1 is in our case ,2.
The next lowest tie which will include either element 1 or 2 (but not both) then is searched. It is found to be 2-4. So far the order in which elements will be added is 1-2-4.
We now look for the lowest link which includes any of the elements 1,2,4(but only one of them). The link 1-3 is thus chosen, therefore, element 3 is next to be added. The order of adding elements so far is 1-2-4-3.
Similarly following this procedure and criteria we see that the next element to be added is 5 and finally 6 is added.

From the above it should become clear that the only thing that the R matrix and the Link Value List establish is the order in which elements will be built into the pattern, but, not to which element will each added element be attached to and how. For our case then, the following order will be used in constructing the pattern. a. 1&2 b. 4 c. 3 d. 5 e. 6

Building the Polyomino.

Since elements 1 and 2 are now considered equal cells there is only one distinct way of connecting them.

To elements 1 and 2 element 4 is to be added. It can assume any of the 6 available positions a to f. Since a=e and b=f, e and f will not be examined. In the Behavioral Matrix the desired distances 4 to 1 and 4 to 2 are as follow:

The best position a through d is found by comparison:

The minimum difference is found to be is position 'b', which happens to be in no conflict with the desired B matrix. The step's selected pattern becomes:

To 1,2,4 element 3 is added. Positions a' through g' are checked in the same way as described before. The desired Behavioral matrix gives the following 'distances' for the elements 1,2,3,4 as shown .

The following is a comparison of the different arrangements which it yields.

The lowest "total of absolute differences'' is obtained in position 'd' and is 1.4. The step's selected pattern is shown in figure 22.

Element 5 is added and checked with the same procedure in positions 'a' through(figure 23) 'f'. Here 'g' is found to be the best position and the step's selected pattern is depicted in figure 24. The final pattern for the six elements is shown in figure 25.

Where to?

[ Next | or | Article Index | or | Publications List | or | Hanna Shapira's Home Page ]