# Algorithm for random distribution of circles in a square

I am searching for a concept to distribute circles in a square randomly, so that they dont overlap. All circles are of the same size. The area covered by the circles can be high, up to the theoretical maximum of ca. 90 % of the square (in which they are completely ordered). About 200 circles should be placed and I want to specify the number of circles exactly. (The distribution is needed as input for a model generation of a FE-analysis, btw). Can you help me for generate the maximum with script

• Are they placed at random points anywhere in the square, or only at random points among the positions that ordered circles would have? – Dimali Sep 5 '17 at 18:50
• this circles is random in the square – saded Sep 5 '17 at 19:05
• Unfortunately the html5 link doesn't work for me (firefox 55.0.3 (64-bit)) Placing the circles randomly and getting anywhere near optimal packing is possibly akin to winning lotto. 200 circles of radius 0.036612 can be packed into unit square at a density of 0.84225. As this is the solution to travelling salesman problem I'd consider a bmesh approach using verts and edges for network. – batFINGER Sep 6 '17 at 6:39
• Would you consider a "random" packing routine, eg add one randomly located circle, then keep adding a random path of touching circles to square edge (and missing existing circles), until no circle can have a path. – batFINGER Sep 6 '17 at 6:56

This simple script to place a number of num_circles circles with radius radiusin a refined rectangle (aligned to global axes) speficied by xmin, xmax, ymin and ymax by trying random locations until it not colliding with an existing circle. This is certainly not the most efficient way of doing it, but it should be fine for smaller problems and if the relative area covered is not too high.

At some point the script will not find a free spot anymore and throw an error. If you increase max_tries, the algorithm is more likely to find free spots at the cost of additional computation time, but the needed time raises extremely fast if you need a higher covered area. It is hard to get much higher than 50%.

from mathutils import Vector
from mathutils.noise import random, seed_set
import bpy

# Specify parameters
seed = 0
xmin = -1
xmax = 1
ymin = -1
ymax = 1
num_circles = 68
max_tries = 10000

# Init
seed_set(seed)
existing_locations = []
sce = bpy.context.scene
ref_circle = bpy.context.object

# Loop
for i in range(num_circles):
j = 0
searchOn = True
while searchOn:
if j > max_tries:
bpy.ops.object.select_all(action='DESELECT')
ref_circle.select = True
bpy.ops.object.delete()
raise ValueError('Found no more room for another circle')
break
j += 1
new_location = (xminm + random()*sx,
yminm + random()*sy,
0)
for existing_location in existing_locations:
break
else:
new_circle = ref_circle.copy()
new_circle.location = new_location

• Nice one. Some suggestions: make one circle with the operator, then add a copy circle.copy() set to new loc and link to scene. The random location could be s * Vector((random(), random())) where s (cos it's a square) is w - 2 * r , w is the height/width of square,. s need be calculated once. (akin to local coords) Lastly 8^) have a look at python any for your collide method. – batFINGER Sep 6 '17 at 7:00