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):

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.