Workplace layout method using convex polygon envelope

Claim 2

An improved method of determining a population density index which aids in laying out the locations of any number of objects in a quadrilateral space where an exact average Euclidean distance between pairs of objects can be determined, the improved method comprising the steps of: distributing the objects in the space; determining a convex hull area for the distribution of the objects, the convex hull area being bounded by a boundary line connecting pairs of objects such that no line connecting any pair of objects crosses the boundary line; determining the population density index for the space and the distribution of objects by the relationship ##EQU10## where d act is the average Euclidean distance between pairs of objects, n is the number of objects and A poly is the convex hull area; and optimizing the layout of the objects in the space based on the population density index.

Claim 3

An improved method of determining a population density index which aids in laying out the locations of any number of objects in a quadrilateral space where an exact average Euclidean distance between pairs of objects can be determined, the improved method comprising the steps of: distributing the objects in the space; overlaying the space with a Cartesian coordinate system having an arbitrary origin; locating a first object having the minimum X coordinate and establishing the first object as a prime object; locating a next object by extending a vertical line from the prime object and rotating the vertical line in a clockwise manner about the prime object, the next object being that object first encountered by the vertical line; extending a boundary line section between the prime object and the next object; establishing the next object as the prime object; locating a next object by extending a sweep line from the prime object in the direction of the boundary line section and rotating the sweep line in a clockwise manner about the prime object, the next object being that object first encountered by the sweep line; repeating the steps beginning with the step of extending a boundary line section until the boundary line is extended to the first point, forming a closed convex hull; determining the population density index for the space and the distribution of objects by the relationship ##EQU11## where d act is the average Euclidean distance between pairs of objects, n is the number of objects and A poly is the convex hull area; and optimizing the layout of the objects in the space based on the population density index.

Claim 4

An improved method of determining a population density index which aids in laying out the locations of any number of objects in a quadrilateral space where an exact average Euclidean distance between pairs of objects can be determined, the improved method comprising the steps of: distributing the objects in the space; overlaying the space with a Cartesian coordinate system having an arbitrary origin; locating a first object having the minimum X coordinate and establishing the first object as a prime object; locating a next object by extending a vertical line from the prime object and rotating the vertical line in a clockwise manner about the prime object, the next object being that object first encountered by the vertical line; extending a boundary line section between the prime object and the next object; establishing the next object as the prime object; locating a next object by extending a sweep line from the prime object in the direction of the boundary line section and rotating the sweep line in a clockwise manner about the prime object, the next object being that object first encountered by the sweep line; repeating the steps beginning with the step of extending a boundary line section until the boundary line is extended to the first point, forming a closed convex hull; determining the population density index for the space and the distribution of objects by the relationship ##EQU11## where d act is the average Euclidean distance between pairs of objects, n is the number of objects and A poly is the convex hull area; and optimizing the layout of the objects in the space based on the population density index.

Claim 5

The improved method of claim 1 wherein the convex hull determining step further comprises the steps of: overlaying the convex hull area with progressively smaller square lattices until each vertex of the convex hull meets a point on the lattice; counting the number of lattice points in the interior of the convex hull; counting the number of lattice points on the boundary line of the convex hull; and determining the convex hull area by the relationship ##EQU12## where r is the spacing between lattice points, i is the number of lattice points in the interior of the hull and b is the number of lattice points on the boundary line.

Claim 6

The improved method of claim 2 wherein the convex hull determining step further comprises the steps of: overlaying the convex hull area with progressively smaller square lattices until each vertex of the convex hull meets a point on the lattice; counting the number of lattice points in the interior of the convex hull; counting the number of lattice points on the boundary line of the convex hull; and determining the convex hull area by the relationship ##EQU13## where r is the spacing between lattice points, i is the number of lattice points in the interior of the hull and b is the number of lattice points on the boundary line.

Claim 7

The improved method of claim 1 wherein the convex hull determining step further comprises the steps of: overlaying the convex hull with a Cartesian coordinate system; determining coordinates for the objects lying on the boundary line of the convex hull; and determining the convex hull area from the relationship A.sub.poly =1/2|(x.sub.1 y.sub.2 -x.sub.2 y.sub.1)+(x.sub.2 y.sub.3 -x.sub.3 y.sub.2)+ . . . +(x.sub.s y.sub.1 -x.sub.1 y.sub.s)| where |·| indicates the absolute value and {(x 1 y 1 ), . . . (x s y s )} are the Cartesian coordinates of the objects lying on the boundary line, the number of objects lying on the boundary line being designated s.

Claim 8

The improved method of claim 2 wherein the convex hull determining step further comprises the steps of: overlaying the convex hull with a Cartesian coordinate system; determining coordinates for the objects lying on the boundary line of the convex hull; and determining the convex hull area from the relationship A.sub.poly =1/2|(x.sub.1 y.sub.2 -x.sub.2 y.sub.1)+(x.sub.2 y.sub.3 -x.sub.3 y.sub.2)+ . . . +(x.sub.s y.sub.1 -x.sub.1 y.sub.s)| where |·| indicates the absolute value and {(x 1 y 1 ), . . . (x s y s )} are the Cartesian coordinates of the objects lying on the boundary line, the number of objects lying on the boundary line being designated s.

Claim 9

The improved method of claim 1 wherein the convex hull determining step further comprises the steps of: extending side lines connecting pairs of objects lying on the boundary line to form non-overlapping triangles within the convex hull; summing the area of the triangles to determine the total convex hull area.

Claim 10

The improved method of claim 7 wherein the area summing step further comprises the steps of: measuring the lengths of the side lines of each triangle; determining a semiperimeter, C p , for each triangle equal to one half of the sum of the lengths of the side lines for the triangle; and determining an area for each triangle from the relationship ##EQU14## where S 1 , S 2 and S 3 are the lengths of the side lines of the triangle.

Claim 11

The improved method of claim 2 wherein the convex hull determining step further comprises the steps of: extending side lines connecting pairs of objects lying on the boundary line to form non-overlapping triangles within the convex hull; and summing the area of the triangles to determine the total convex hull area.

Claim 12

The improved method of claim 9 wherein the area summing step further comprises the steps of: measuring the lengths of the side lines of each triangle; determining a semiperimeter, C p , for each triangle equal to one half of the sum of the lengths of the side lines for the triangle; and determining an area for each triangle from the relationship ##EQU15## where S 1 , S 2 and S 3 are the lengths of the side lines of the triangle.