Approximation Method for Workplace Layout Using Convex Polygon Envelope

This patent application is co-pending with a related patent application entitled Workplace Layout Method Using Convex Polygon Envelope (U.S. patent application Ser. No. 08/708,008) by the same inventor as this patent application.

(1) Field of the Invention

This invention relates to a method for providing layouts of workplaces and more particularly to a generalized layout method for a workplace containing any number of spatial objects, the method being based on an approximation of the average distance between the objects being laid out and on a crowding index calculated from a convex polygon envelope.

(2) Description of the Prior Art

In the inventor's previous patent entitled "Process Which Aids to the Laying Out of Locations of a Limited Number of 100, Personnel and Equipments in Functional Organization", U.S. Pat. No. 5,235,506, which is incorporated into this disclosure in its entirety by reference, a process is described whereby the relationship among objects in a particular space can be accurately determined to minimize crowding. A crowding index, or Population Density Index (PDI), for the space, termed PDI.sub.act, is calculated and compared to theoretical minimum (PDI.sub.min) and maximum (PDI.sub.max) values, such that PDI.sub.min <PDI.sub.act <PDI.sub.max. The formula for calculating PDI.sub.act is as follows: ##EQU1## where n=number of objects in the space;

A=the geometric area of the space; and

d.sub.act =average Euclidean distance among all possible pairs of n objects within the space.

The values of PDI.sub.min and PDI.sub.max are given as follows: ##EQU2## where .DELTA.=the average Euclidean distance of all possible pairs of points for a unit lattice, i.e., a lattice of n points uniformly distributed in area A; and

c=an arbitrary constant which corresponds to the minimum possible spacing between the objects, e.g., personnel standing shoulder to shoulder within a space would be spaced approximately one foot from head to head, so c would be equal to one foot.

It can be seen that PDI.sub.min corresponds to a uniform distribution of n points in the space, while PDI.sub.max corresponds to a uniform distribution of n points in the space with a minimum distance c between each horizontal and vertical point.

For small workplace layouts, i.e., where the number of points do not exceed 100, a table of values for .DELTA. is provided:

In the inventor's related patent entitled "Two-Step Method Constructing Large-Area Facilities and Small-Area Intrafacilities Equipments Optimized by User Population Density", U.S. Pat. No. 5,402,335, the following formula was provided for calculating .DELTA. for any number of points: ##EQU3## where C=the number of vertical points in each column of the unit lattice; and

R=the number of horizontal points in each row of the unit lattice, such that RC=the total number of points in the unit lattice.

The formula provides an exact solution for .DELTA., corresponding to the values given in Table 1.

As an example of using PDI to determine the crowding of a particular layout, assume a workspace of 25 ft.sup.2 (A=25) with a total of 12 objects or personnel (n=12) which need to be laid out within the space. In using Table 1 or equation (4), the row by column distribution of the lattice points should be commensurate with the shape of the region A in which the lattice points reside. If the area is relatively square, i.e., 5.times.5, a corresponding distribution of 12 points would be 4.times.3, with .DELTA.=1.90. For a rectangular area of approximately 8.33.times.3, a corresponding distribution would be 6.times.2, with .DELTA.=2.32. Assuming a relatively square area and a 4.times.3 distribution, the calculation of PDI.sub.min from equation (2) yields (1/1.90)(12/25).apprxeq.0.25 and the calculation of PDI.sub.max from equation (3) yields (1/c)(1/1.90)(12/25).sup.1/2 .apprxeq.0.36, where c is taken as one foot as in the example of personnel standing shoulder to shoulder. Note that the value of PDI.sub.max is seen to increase as c, or the minimum distance between points, becomes smaller, corresponding to the ability to pack additional points into the space. To determine PDI.sub.act, measurements of the proposed distribution of points need to be taken and those measurements used to calculate d.sub.act as follows: ##EQU4## where d.sub.ij =measured distance between point i and point j. For realistic workspace layout problems, the process of measuring the distances between all points can be cumbersome at best. The inventor's '335 patent disclosed an approximation method for determining d.sub.act. The workspace, having an area X units by Y units, or A=XY, is partitioned into n rectangles with sides equal to (X/R) and (Y/C). By visual inspection of the partitioned workspace, a cluster count, m, can be obtained by counting the number of rectangles occupied by one or more objects. An approximation for d.sub.act can then be derived as follows: ##EQU5## Substituting equation (6) into equation (1) yields: ##EQU6## Assuming a proposed distribution where m=8, PDI.sub.act ' from equation (7) yields (12/25)(1/1.9)(12/8).sup.1/2 .apprxeq.0.31. This would indicate the space is 24% more crowded (0.25 vs. 0.31) than the theoretical minimum and 16% less crowded than the theoretical maximum (0.31 vs. 0.36).

It will be noticed that the total area, A, of the space is used in computing PDI.sub.act ', the approximate crowding index for the workspace in question. In actuality, the perceived crowding will depend on the area encompassed by the points (objects or personnel) within the space. As an example, assume four points arranged in a square having sides approximately 4.4 units long. For such an arrangement, d.sub.act, as calculated in accordance with equation (5), is 2(d.sub.12 +d.sub.13 +d.sub.14 +d.sub.23 +d.sub.24 +d.sub.34)/(4(4-1))=5.0. This can be compared to a rectangular arrangement having sides of 2.5 and 6 units long. Again d.sub.act is calculated to be 5.0. For a 2.times.2 distribution, we obtain .DELTA.=1.14 from Table 1. If we now assume an area of A=100 for both distributions and c=1, we can calculate PDI.sub.min, PDI.sub.max and PDI.sub.act from equations (2), (3) and (1), respectively.

The same analysis would hold where the number of points to be laid out would require the use of d.sub.act '. Note that the various PDI's, or the crowding indices, have the same values for both the square and rectangular distributions of points. However, the perceived crowding of personnel separated by 2.5 units, which is approaching the minimum spacing of c=1, would probably be greater than those separated by 4.4 units. Carrying the example to its extreme, a long, narrow rectangle can be formed where the two points forming the shorter side of the rectangle are at the minimum spacing "c". Again, the PDI values would remain the same, but the crowding at the ends of the rectangle would probably be intolerable.

Accordingly, it is a general purpose and object of the present invention to provide an improvement to the approximate PDI method for laying out workplaces which better takes into account the distribution of points within an area.

It is a further object of the present invention that the improvement better reflect the perceived crowding within the point distribution.

These objects are provided with the present invention by an improved method of calculating the approximate crowding index for a space, PDI.sub.act ', which accounts for the distribution of points within the space. While the approximate term d.sub.act ' attempts to account for the spacing between points, it is to be noted in the example given above that the change from a square distribution of points to a rectangular distribution had no effect on the crowding indices. However, with d.sub.act ' held constant, there is a change in the area bounded by the points as the distribution moves from a square configuration (A.sub.square =4.4.times.4.4=19.36) to a rectangular one (A.sub.rect. =2.5.times.6=15). The decrease in area is consistent with an increase in the perceived crowding. It is proposed that a more accurate measure of the approximate crowding index will utilize a measure of the actual polygonal space occupied by the distribution of points within the total area as well as the approximate average Euclidean distance, d.sub.act ', between the points for which a layout is desired. This new measure can be expressed as follows: ##EQU7## where A.sub.poly =the area of the polygonal space occupied by the distribution.

The method of the present invention further provides for the calculation of A.sub.poly based on the use of Pick's theorem, as further developed herein .

A more complete understanding of the invention and many of the attendant advantages thereto will be readily appreciated as the same becomes better understood by reference to the following detailed description when considered in conjunction with the accompanying drawings wherein corresponding reference characters indicate corresponding parts throughout the several views of the drawings and wherein:

FIG. 1 depicts an area A of 20.times.16 units with n=64 points distributed therein;

FIG. 1A depicts the area divided into n equal rectangles;

FIG. 2 depicts a polygonal area containing the distributed points; and

FIG. 3 depicts a lattice overlaid on the polygonal area.

Referring now to FIG. 1, there is shown a configuration of 64 points arranged in a space of 320 square units (A=320). In using the improved PDI method, the values for PDI.sub.min and PDI.sub.max are computed in accordance with the prior art. Using Table 1 or equation (4), an 8.times.8 lattice is chosen, yielding a .DELTA. of 4.20. Calculating PDI.sub.min and PDI.sub.max, we obtain the values 0.048 and 0.106, respectively. To determine the value of d.sub.act, a total of n(n-1)/2, or 2,016 distances would have to be measured. Using the approximation method, the approximate value PDI.sub.act ' can be determined directly from equation (7). Using the distribution shown in FIG. 1, we first divide the space into rectangles corresponding to the unit lattice choasen, in this case 8.times.8 rectangles as shown in FIG. 1A. Counting those rectangles having at least one point therein, we determine that m=33. Using equation (7) we find PDI.sub.act '=(64/(320.times.4.2))(64/33).sup.1/2 .apprxeq.0.066 where the minimum distance between objects c is taken as 1. A PDI.sub.act ' just slightly higher than PDI.sub.min would indicate a non-crowded layout. Referring now to FIG. 2, the area to be used in calculating the improved crowding index, PDI.sub.poly ', in accordance with the present invention is depicted therein. The polygonal area A.sub.poly, is referred to as a convex hull and is constructed as described in Computational Geometry: An Introduction, Preparata, F. P. and Shamos, M. I. (1985, pp. 104-106) New York: Springer-Verlag. Intuitively, the convex hull is constructed by imagining a rubber band stretched around all the points and, when released, the band assumes the shape of the hull. If the points are then connected pairwise, no line falls outside the bounded figure. A number of methods, well known in the art, are available for calculating the convex hull area. In a previous paper, "Measuring The Areal Density Of A Finite Ensemble", Perceptual and Motor Skills, O'Brien, F. (1995, vol. 81, pp. 195-200), the inventor discusses three such methods: (1) Pick's theorem; (2) the Surveyor's Area formula; and (3) Hero's formula. Pick's theorem will be used to illustrate the calculation of the area of the convex hull, A.sub.poly, which will then be used in determining the improved approximate crowding index, PDI.sub.poly '.

Referring now to FIG. 3, the convex hull is shown overlaid with a square lattice of points such that each vertex of the hull meets a point of the lattice. It is anticipated the spacing between lattice points will be determined by overlaying the convex hull with lattices having successively smaller and smaller spacing. The process is continued until the lattice spacing is such that each vertex of the convex hull falls on a lattice point. Pick's theorem states:

where

r=the spacing between lattice points;

i=the number of lattice points in the interior of the hull; and

b=the number of lattice points on the boundary.

FIG. 3 shows a lattice with r=1.0. Counting the number of lattice points on the interior of the convex hull yields i=132 and the number of lattice points on the boundary gives b=25. A.sub.poly from equation (9) is (1).sup.2 (132+25/2-1)=143.5. Using this value in equation (8) yields a value of 0.148 for PDI.sub.poly '. Since PDI.sub.poly '>PDI.sub.max, a crowded condition is indicated. Looking to FIG. 3, we can see a tight grouping of points towards the upper right of the convex hull area and the entire distribution of points appears concentrated in the center of the rectangular area. The tight grouping of points is accounted for in the term d.sub.act ' when calculating PDI.sub.poly ', in the same manner as in calculating PDI.sub.act '. However, the concentration of points in a relatively small area at the center of the rectangle was not taken into account in calculating PDI.sub.act '. As indicated in the above calculation, the use of PDI.sub.poly ' with the convex hull area term A.sub.poly does take this concentration into account. Another way of looking at this result is to note that PDI.sub.poly ' is independent of the area A being laid out. Changes in the total area A effect PDI.sub.min and PDI.sub.max, or the bounds of PDI.sub.poly ', but the crowding index within the convex hull area is not effected by the changes to the total area A.

What has thus been described is an improvement to the prior art crowding index, or PDI, method for laying out workspace where the average interpoint distance between the personnel and/or equipment to be laid out, d.sub.act, cannot realistically be determined and an approximation, d.sub.act ', must be used. The improvement lies in using the convex hull area, A.sub.poly, of the distribution of points being laid out within the space to calculate the actual crowding index for the workspace. The convex hull area is that area having a boundary line connecting pairs of points being laid out such that no line connecting any pair of points crosses the boundary line. The calculation of the convex hull area is illustrated using Pick's theorem. The improved crowding index is termed PDI.sub.poly ' to distinguish it from the prior art crowding index, PDI.sub.act with the prime denoting the value is an approximation. In the prior art, the distribution of points within the workplace was taken into account in the approximate crowding index, PDI.sub.act ', solely through the approximate average interpoint distance term d.sub.act '. The use of the area bounded by the personnel or equipment being laid out in determining the improved crowding index, PDI.sub.poly ', more fully takes into account the distribution of points within the total area being laid out and also better reflects the perceived crowding within the point distribution.

While a preferred embodiment of the invention using Pick's theorem has been disclosed in detail, it should be understood by those skilled in the art that various other methods or formulae for calculating the convex hull area, A.sub.poly, may be used. For example, the convex hull area may be calculated using the Surveyor's Area formula or Hero's formula.

When Cartesian coordinates are readily available for the points forming the vertices of the convex hull, the Surveyor's Area formula may be used:

where .vertline..multidot..vertline. indicates the absolute value and {(x.sub.1 y.sub.1), . . . , (x.sub.x y.sub.2)} are the Cartesian coordinates of the s boundary points of the convex hull. When coordinate measurements are not easily available, but one is able to obtain the distances between the vertices of the convex hull, such as from an aerial photograph, then Hero's formula may be used. Hero's formula is based on summing the areas of non-overlapping triangles within the convex hull. The area of each triangle is calculated from: ##EQU8## where S.sub.1, S.sub.2 and S.sub.3 are the lengths of the sides of triangle and C.sub.p is the semiperimeter of the triangle, or (S.sub.1 +S.sub.2 +S.sub.3)/2. In general, s-2 triangles will result from a convex hull consisting of s boundary points. The total area of the convex hull is then given as: ##EQU9## As with the use of Pick's theorem to calculate A.sub.poly, the Surveyor's Area formula and Hero's formula are well known in the art.

In light of the above, it is therefore understood that within the scope of the appended claims, the invention may be practiced otherwise than as specifically described.