Home > Art, Learning, Problem, Projects/Experiments, Python > Python: Circle Packing

Python: Circle Packing



Circle Packing Project
Subject: Draw, circles, Turtle

Definition: In geometry, circle packing is the study of the arrangement of circles on a given surface such that no overlapping occurs and so that all circles touch one another. Wikipedia

So, we have a canvas size (w,h) and we want to write a code to draw X number of circles in this area without any overlapping or intersecting between circles. We will write some functions to do this task, thous functions are:
1. c_draw (x1,y1,di): This function will take three arguments x1,y1 for circle position and di as circle diameter.

2. draw_fram(): This function will draw the frame on the screen, we set the frame_w and frame_h as variables in the setup area in the code.

3. c_generator (max_di): c_generator is the circles generating function, and takes one argument max_di presenting the maximum circles diameter. To generate a circle we will generate three random numbers for x position, y position and for circle diameter (max_di is the upper limit),also with each generating a while loop will make sure that the circle is inside the frame, if not regenerate another one.

4. can_we_draw_it (q1,di1): This is very important, to make sure that the circle is not overlapping with any other we need to use a function call (hypot) from math library hypot return the distance between two points, then if the distance between two circles is less than the total of there diameters then the two circles are not overlaps.



So, lets start coding …

First: the import and setup variables:


from turtle import *
import random
import math

# Create a turtle named t:
t =Turtle()
t.speed(0)
t.hideturtle()
t.setheading(0) 
t.pensize(0.5)
t.penup()

# frame size
frame_w = 500 
frame_h = 600 

di_list = [] # To hold the circles x,y and diameters


Now, Drawing the frame function:


def draw_fram () :

t.penup()

t.setheading(0)

t.goto(-frame_w/2,frame_h/2)

t.pendown()

t.forward(frame_w)

t.right(90)

t.forward(frame_h)

t.right(90)

t.forward(frame_w)

t.right(90)

t.forward(frame_h)

t.penup()

t.goto(0,0)


Now, Draw circle function:


def c_draw (x1,y1,di):

t.goto(x1,y1)

t.setheading(-90)

t.pendown()

t.circle(di)

t.penup()


This is Circles generator, we randomly select x,y and diameter then checks if it is in or out the canvas.


def c_generator (max_di):

falls_out_frame = True

while falls_out_frame :

x1 = random.randint(-(frame_w/2),(frame_w/2))

y1 = random.randint(-(frame_h/2),(frame_h/2))

di = random.randint(3,max_di)

# if true circle is in canvas

if (x1-di > ((frame_w/2)*-1)) and (x1-di < ((frame_w/2)-(di*2))) :

if (y1 ((frame_h/2)-(di))*-1) :

falls_out_frame = False

di_list.append([x1-di,y1,di])


With each new circle we need to check the distances and the diameter between new circle and all circles we have in the list, if there is an overlap then we delete the new circle data (using di_list.pop()) and generate a new circle. So to get the distances and sum of diameters we use this code ..

 # get circles distance

    cs_dis = math.hypot(((last_cx + last_cdi) - (c_n_list_x + c_n_list_di)) , (last_cy - c_n_list_y))
    di_total = last_cdi + c_n_list_di


To speed up the generation of right size of circles I use a method of counting the trying times of wrong sizes, that’s mean if the circles is not fit, and we pop it’s details from the circles list we count pops, if we reach certain number then we reduce the upper limits of random diameter of the new circles we generate. Say we start with max_di = 200, then if we pop for a number that divide by 30 (pop%30) then we reduce the max_di with (-1) and if we reach max_di less then 10 then max_di = 60. and we keep doing this until we draw 700 circles.


# if di_list pops x time then we reduce the randomization upper limits 
  if (total_pop % 30) == 0:
    max_di = max_di - 1
    if max_di < 10 :
      max_di = 60


Here are some output circles packing ..




With current output we reach the goal we are looking for, although there is some empty spaces, but if we increase the number of circles then there will be more time finding those area with random (x,y,di) generator, I am thinking in another version of this code that’s will cover:
1. Coloring the circles based on the diameter size.
2. A method to fill the spaces.



Follow me on Twitter..





  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: