Improving the efficiency of randomly generated sphere interference inspection by block division

Improve the efficiency of randomly generated sphere interference inspection through block division

   In material research , Regular use Matlab To simulate various situations of materials —— For example, simulate the distribution of battery particles and subsequent calculation .
   In material simulation , Our first step is generally to generate the material to be simulated . One of the methods used is to generate a certain number of particles of specific size at random positions . For example, the following figure looks like ：

   When these particles are randomly generated , For every randomly generated particle, we have to judge the positional relationship between the newly generated particle and other existing particles , If interference occurs, the newly generated particles need to be regenerated . The time complexity of such a calculation method is O(N!) Of , As the number of particles to be generated increases, the calculation time will become long .
   In order to improve the efficiency of calculation , We judge the interference between newly generated particles and existing particles , Block division can be adopted . That is to divide the space into several blocks , Each time, the newly generated particles only interfere with the existing particles in several blocks , In this way , Reduce the amount of calculation .
   In the following illustration , We divide the generated space into 10x10 Block . One new particle at a time , We will no longer check the interference between new particles and all existing particles , Instead, only the block where the new particles are located and the existing particles in the eight surrounding blocks are checked for interference . When our particle formation is completely random , Then our interference calculation is only the original way 9/100.

   In the case of block method , Regardless of the total number of blocks , We all just need to 9 Block by block . therefore , When we divide space into x When a block , The efficiency is the of the original efficiency x/9. however , It should be noted that , Blocks cannot be increased indefinitely , Because we must ensure that the block can hold the largest particles , Otherwise, there will be problems in the calculation .

   In this way , We can quickly and randomly generate a specific number of particles of different sizes .

The method of randomly generating particles by block method Matlab Code