# Computation of Compact Distributions of Discrete Elements
## 3 Methods of This Paper
### Voronoi Diagram Generation Based on GPU Acceleration  
To generate a Voronoi diagram, the iteration process must be repeated and every iteration process needs to loop through all the distribution points, which is quite time-consuming. [PERSON] et al. (2016) proposed a method of converting the Voronoi generation process into a graphical rendering process. First, the distribution of the initial points is determined, and then a circular cone with height equal to the radius is constructed at each initial point location. The vertices of the cones are used as the initial seed points. The cones are the same in terms of all parameters except color. In this way, the height of the side part of the cone can be adopted to measure the distance from the corresponding points on the bottom surface to the center; thus, the correct Voronoi diagram can be obtained by rendering all the cones with visibility detection via the z-buffer algorithm. The Voronoi generation process is successfully transformed into a graphical rendering process, and the GPU parallel computing ability can be fully utilized to increase the speed. This paper, taking this as a reference, implemented a GPU rendering process to achieve quick generation of Voronoi regions with many shapes. In the following part of this paper, the Voronoi regions generated by GPU rendering are described--they are of five shapes; namely, circle, square, rectangle, oval, and triangle. The key to accomplishing the Voronoi generation via geometric rendering and visibility detection with the z-buffer algorithm is to ensure that the height of any point on the side of the geometric shape is equal to the distance between the corresponding points of the random point on the bottom surface and the center. Taking the cone shown in Figure 8 as an example, the height of the cone and the radius of the bottom surface are both \(\mathrm{L_{a}}\), and the corresponding point of any random point \(\mathrm{A}\) on the side is \(A_{0}\). Given that the distance between \(A_{0}\) and center is the yellow segment \(|OA_{0}|\) and the height of \(\mathrm{A}\) is the blue segment \(|AB|\), based on \(|TB|=|AB|\) and \(|TB|=|OA_{0}|\), we conclude that \(|AB|=|OA_{0}|\). As shown in Figure 9, by rendering a mass of three-dimensional cones, we can obtain the Voronoi diagram. In the rendering, the orthographic projection is adopted, and the z-buffer method is used for visibility detection. Figure 7: Left: equidistant line distance. Right: the Voronoi diagram and the Voronoi region shape (lower right corner) by the equidistant line distance. To generate Voronoi diagrams in many shapes, we adopt many kinds of geometries that conform to the above distance conditions; the detailed information is shown in Table 1.  
Calculation process:  
Step 1. Randomly generate initial distribution point set p.  
Step 2. Show geometries (circular cone, square pyramid, pyramid, elliptic cone, and triangular pyramid) in different colors at every p(x, y) location; different colors can make it easier to distinguish different Voronoi regions. Step 3. Rotate the geometry \(\psi\)(x, y) according to the direction field of p(x, y). Step 4. Perform the depth measurement, and read the current drawing results; calculate the center of gravity of each Voronoi region; the results are the new distribution point set p.  
Step 5. Repeat steps 2 to 4 for the new point set p until the specified number of iterations is reached. Step 6. Place the elements at the locations of the final centers of gravity.