Plot random generated 'n' non-colliding circles using Matplotlib

Question

I have a function which plots n randomly generated non-colliding circles. The circle is a Circle object, part of matplotlib.patches. We will generate each random circle by its center and r, for example : r = random.uniform(min_r, max_r).

To make circles with no collision, no two circles (with c1, r1 and c2, r2 as the center and radius) can have : distance(c1, c2) < r1 + r2.

Here is the imports:

import random
import matplotlib.pyplot as plt
from matplotlib.patches import Circle
import numpy 

The implementation is done by the function below, how to make the script more compact and the implementation more efficient (faster)? Thanks.

The main function:

def nocollide_random_unif_circles():
 def add_circle(ax, center=(0,0), r=1, face_color=(0,0,1,1), edge_color=(0,0,1,1), line_width = None):
 C = Circle(center, radius = r, facecolor = face_color, edgecolor = edge_color, linewidth = line_width)
 ax.add_patch(C)
 def dist2d(p, q):
 distance = numpy.sqrt( (p[0]-q[0])**2 + (p[1]-q[1])**2 )
 return distance
 def collide(center, rad, centers, rads):
 for c, r in zip(centers, rads):
 if dist2d(c, center) < r + rad:
 return True
 return False
 ncircle = 1000
 min_r = 1
 max_r = 200
 color = 'blue'
 sizex = [0, 1000]; sizey = [0, 1000]
 fig, ax = plt.subplots(1, 1)
 centers = [(random.uniform(sizex[0], sizex[1]), \
 random.uniform(sizey[0], sizey[1]))]
 rads = [random.uniform(min_r, max_r)]
 add_circle(ax, center = centers[0], r = rads[0],\
 face_color = color, edge_color = (0, 0, 0, 0))
 for n in range(ncircle-1):
 center = (random.uniform(sizex[0], sizex[1]), \
 random.uniform(sizey[0], sizey[1]))
 rad = random.uniform(min_r, max_r)
 while collide(center, rad, centers, rads):
 center = (random.uniform(sizex[0], sizex[1]), \
 random.uniform(sizey[0], sizey[1]))
 rad = random.uniform(min_r, max_r)
 centers.append(center); rads.append(rad)
 add_circle(ax, center = centers[-1], r = rads[-1],\
 face_color = color, edge_color = (0, 0, 0, 0))
 print(n)
 ax.axis('equal')
 ax.set_xlim(sizex); ax.set_ylim(sizey)
 ax.tick_params(colors = (0,0,0,0))
 ax.set_title('min radius = {}, max radius = {}, n = {} circles'.format(min_r, max_r, ncircle))
 fig.tight_layout()
 fig.show()

Example result with n=4000 (took quite some time):

enter image description here

Answer 1

I would pull out the generation of the next circle and the generation of all circles into their own functions. This allows you to test those parts without having to plot the result, allowing some speed comparisons:

def place_circle(centers, rads, size_x, size_y, size_r):
 center = random.uniform(*size_x), random.uniform(*size_y)
 rad = random.uniform(*size_r)
 if centers and rads:
 while collide(center, rad, centers, rads):
 center = random.uniform(*size_x), random.uniform(*size_y)
 rad = random.uniform(*size_r)
 return center, rad
def place_circles(ncirle, size_x, size_y, size_r):
 centers, rads = [], []
 for n in range(ncircle):
 center, rad = place_circle(centers, rads, size_x, size_y, size_r)
 centers.append(center)
 rads.append(rad)
 # print(n)
 return centers, rads

You can then use this like this in your main function:

centers, rads = place_circles(ncircle, sizex, sizey, (min_r, max_r))
for center, rad in zip(centers, rads):
 add_circle(ax, center=center, r=rad, face_color=color, edge_color=BLACK)

Note that I made (0, 0, 0, 0) global constant called BLACK and removed the whitespace around = for keywords (as recommended by Python's official style-guide, PEP8).

Now, we can test how long it takes to find a place for 1000 circles:

%timeit place_circles(1000, (0, 1000), (0, 1000), (1, 200))
3.33 s ± 139 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

With this baseline, you can try to improve the performance.