0
$\begingroup$

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
Example for the distribution: https://zoada.com/html5/brute.html

$\endgroup$
  • $\begingroup$ Are they placed at random points anywhere in the square, or only at random points among the positions that ordered circles would have? $\endgroup$ – Dimali Sep 5 '17 at 18:50
  • $\begingroup$ this circles is random in the square $\endgroup$ – saded Sep 5 '17 at 19:05
  • $\begingroup$ 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. $\endgroup$ – batFINGER Sep 6 '17 at 6:39
  • $\begingroup$ 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. $\endgroup$ – batFINGER Sep 6 '17 at 6:56
4
$\begingroup$

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.

enter image description here enter image description here

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%.

enter image description here

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
radius = 0.1
num_circles = 68
max_tries = 10000

# Init
seed_set(seed)
sx = xmax-xmin-2*radius
sy = ymax-ymin-2*radius
xminm = xmin+radius 
yminm = ymin+radius 
existing_locations = []
sce = bpy.context.scene
bpy.ops.mesh.primitive_circle_add(location=(0,0,0), radius=radius)
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:
            if (Vector(existing_location)-Vector(new_location)).length < 2*radius:
                break
        else:
            new_circle = ref_circle.copy()
            new_circle.location = new_location
            sce.objects.link(new_circle)
            existing_locations.append(new_location)
            searchOn = False

ref_circle.select = True
bpy.ops.object.delete() 
sce.update()
|improve this answer|||||
$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – batFINGER Sep 6 '17 at 7:00
  • 1
    $\begingroup$ Nice one. Notice link in my comment on question. Interested how close you can get to optima using unit square and radii from tables, using random placement. $\endgroup$ – batFINGER Sep 6 '17 at 7:20
  • 2
    $\begingroup$ @saded surely this answer worth a UV from you? Given all the talk of research et al there is a distinct lack of code / research etc in your question. For instance the 0.9 limit is for infinitely small (approaching 0) optimally hexagonally packed circles. Is Dmali doing your homework for you? $\endgroup$ – batFINGER Sep 6 '17 at 11:25
  • 2
    $\begingroup$ This is all well, but please ask a specific question and don't change it after it has been answered. I clarified in the beginning that you want random distribution and you agreed. If this answer helped you please accept it (or vote up if it helped anyway) or make clear what you expect instead. Remember that this is a QA forum and not professional support. $\endgroup$ – Dimali Sep 6 '17 at 12:22
  • 1
    $\begingroup$ Have used this here blender.stackexchange.com/a/135811/15543 $\endgroup$ – batFINGER Mar 31 '19 at 14:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.