DIGITAL SIMULATION OF FILLING IN THE PLANE ON THE “MINSK-1” COMPUTER

I. E. NAATS, N. M. BYLINO

(Presented by the scientific seminar of the Computing Laboratory)

In [1] it was noted that the model of filling space is used to describe the geometric properties of a number of discrete structures. It is quite obvious here that both the packing density and the other geometric characteristics [1] of the structures under consideration depend on the geometric properties of the system of filling bodies and on the shape of the body being filled. For the simplest regular packing in the plane it is possible to estimate analytically the values of the geometric characteristics. However, in the general case, especially for a system of convex bodies of different diameters, obtaining analytical estimates is very difficult.

In the present work an algorithm is proposed for the digital simulation of the process of packing a rectangular region with a system of circles and for determining the homogeneity function of the packings obtained.

Let us dwell on a general description of the packing algorithm. Suppose there is a rectangular region of size \(a \times b\) (Fig. 1).

We shall assume that filling the region with circles (of equal diameter) is carried out layer by layer. In the first layer the circles are placed next to one another from left to right, so that each touches one circle on the left and the abscissa axis. Filling is carried out up to the circle with number \(i\); in this case control of the filling of the first layer is carried out according to the inequality

\[ iD < b < (i+1)D. \]

The second layer is filled from right to left; in this case the filling begins with determining the position of the \((i+1)\)-st circle (the boundary circle). The position of this circle is determined from the condition of contact of the \(i\)-th circle with the right boundary

Fig. 1. Examples of filling a rectangular region depending on the ratio of the parameters \(a\) and \(b\)

region. The position of the next circle in the second layer with index \((i+2)\) is determined from the condition of tangency of two adjacent circles, which are chosen as follows. If \(b-iD \ge \dfrac{D}{2}\), then circle \((i+2)\) is completely placed in the “hollow” between the \((i-1)\)-th and \(i\)-th circles of the lower layer, and, consequently, its position is determined by tangency precisely with these circles (Fig. 1, \(a, b\)). If, however, \(b-iD < \dfrac{D}{2}\), then the position of the \((i+2)\)-nd circle is determined from the condition of tangency of the first circle of the second layer, i.e., the \((i+1)\)-st in the order of packing, and the next-to-last circle, i.e., the \((i-1)\)-st, of the lower layer (Fig. 1, \(v, g\)). The position of the \((i+3)\)-rd circle in the second layer

Fig. 2. Flowchart of the program on “Minsk-1”

Flowchart block labels:

• Filling the first layer
• Comparing coordinates with the right boundary of the region
• Finding the coordinates of the 1st circle of the new layer
• Comparing the \(y\)-coordinate with the upper boundary of the region
• Selecting circles of tangency
• Finding the coordinates of a new circle of the new layer
• Comparing the \(y\)-coordinate with the upper boundary of the region
• Comparing the coordinates with the right boundary of the region
• Computing the filling-homogeneity function

Fig. 3. Curves \(l_y(x)\) calculated for the examples in Fig. 1

is determined in the same way as the position of the \((i+2)\)-nd, i.e., from the condition of tangency of one circle from the lower layer with another adjacent one on the right. The “reflection” of circles from the left wall of the region at the end of the second and the beginning of the third layers is carried out analogously to the above. As a result, a rectangular region is filled layer by layer with circles, i.e., the centers of the circles that have filled this region are determined.

The determination of the filling density \(\rho\) is carried out by counting the number of circles that fall into the region under consideration and forming the ratio of the occupied area to the area of the region. The coefficient of homogeneity of filling \(l_y(x)\) is calculated as follows. First of all, the set of circles (also the set of indices \(I(x)\)) is determined that intersect a straight line parallel to the \(y\)-axis and intersecting

intersecting the abscissa axis at the point \(x\), from the condition \(\lvert x - x_k\rvert < \dfrac{D}{2}\) for all \(k \in I(x)\). This determines the length of the chord in the circle with index \(k\) lying on the indicated straight line (ray), with subsequent summation over all \(k \in I(x)\).

Figure 2 presents the flowchart of the program for filling a rectangular region, implemented on the “Minsk-1” computer. Figure 3 gives the curves \(l_y(x)\) for the corresponding examples of the arrangement of circles in the region in Fig. 1. In the indicated examples, the successive decrease of \(b\) deforms the lattice of centers, with the corresponding change in the geometric properties of the structure determined by this lattice, which is also reflected in Fig. 3.

The computations were performed on the machine with the following data: \(D = 0.2\), \(n\)—the number of layers—is equal to 5; the value of \(b\) is indicated in Fig. 3.

In an analogous way, more complex cases of filling in the plane can be subjected to digital simulation, in particular filling by a system of circles of different diameter.

References

1. I. E. Naats. Questions of the geometric description of discrete structures. (The present collection).