pythonportingcircle-pack
Controlled circle packing with Python
I'm trying to port to Python the "Controlled Circle Packing with Processing" algorithm that I found here:
For now my goal is just to make it work, before I tweak it for my own needs. This question is not about the best way to do circle packing.
So far here is what I have:
#!/usr/bin/python
# coding: utf-8
import numpy as np
import matplotlib.pyplot as plt
from random import uniform
class Ball:
def __init__(self, x, y, radius):
self.r = radius
self.acceleration = np.array([0, 0])
self.velocity = np.array([uniform(0, 1),
uniform(0, 1)])
self.position = np.array([x, y])
@property
def x(self):
return self.position[0]
@property
def y(self):
return self.position[1]
def applyForce(self, force):
self.acceleration = np.add(self.acceleration, force)
def update(self):
self.velocity = np.add(self.velocity, self.acceleration)
self.position = np.add(self.position, self.velocity)
self.acceleration *= 0
class Pack:
def __init__(self, radius, list_balls):
self.list_balls = list_balls
self.r = radius
self.list_separate_forces = [np.array([0, 0])] * len(self.list_balls)
self.list_near_balls = [0] * len(self.list_balls)
def _normalize(self, v):
norm = np.linalg.norm(v)
if norm == 0:
return v
return v / norm
def run(self):
for i in range(300):
print(i)
for ball in self.list_balls:
self.checkBorders(ball)
self.checkBallPositions(ball)
self.applySeparationForcesToBall(ball)
def checkBorders(self, ball):
if (ball.x - ball.r) < - self.r or (ball.x + ball.r) > self.r:
ball.velocity[0] *= -1
ball.update()
if (ball.y - ball.r) < -self.r or (ball.y + ball.r) > self.r:
ball.velocity[1] *= -1
ball.update()
def checkBallPositions(self, ball):
list_neighbours = [e for e in self.list_balls if e is not ball]
for neighbour in list_neighbours:
d = self._distanceBalls(ball, neighbour)
if d < (ball.r + neighbour.r):
return
ball.velocity[0] = 0
ball.velocity[1] = 0
def getSeparationForce(self, c1, c2):
steer = np.array([0, 0])
d = self._distanceBalls(c1, c2)
if d > 0 and d < (c1.r + c2.r):
diff = np.subtract(c1.position, c2.position)
diff = self._normalize(diff)
diff = np.divide(diff, d)
steer = np.add(steer, diff)
return steer
def _distanceBalls(self, c1, c2):
x1, y1 = c1.x, c1.y
x2, y2 = c2.x, c2.y
dist = np.sqrt((x2 - x1)**2 + (y2 - y1)**2)
return dist
def applySeparationForcesToBall(self, ball):
i = self.list_balls.index(ball)
list_neighbours = [e for e in self.list_balls if e is not ball]
for neighbour in list_neighbours:
j = self.list_balls.index(neighbour)
forceij = self.getSeparationForce(ball, neighbour)
if np.linalg.norm(forceij) > 0:
self.list_separate_forces[i] = np.add(self.list_separate_forces[i], forceij)
self.list_separate_forces[j] = np.subtract(self.list_separate_forces[j], forceij)
self.list_near_balls[i] += 1
self.list_near_balls[j] += 1
if self.list_near_balls[i] > 0:
self.list_separate_forces[i] = np.divide(self.list_separate_forces[i], self.list_near_balls[i])
if np.linalg.norm(self.list_separate_forces[i]) > 0:
self.list_separate_forces[i] = self._normalize(self.list_separate_forces[i])
self.list_separate_forces[i] = np.subtract(self.list_separate_forces[i], ball.velocity)
self.list_separate_forces[i] = np.clip(self.list_separate_forces[i], a_min=0, a_max=np.array([1]))
separation = self.list_separate_forces[i]
ball.applyForce(separation)
ball.update()
list_balls = list()
for i in range(10):
b = Ball(0, 0, 7)
list_balls.append(b)
p = Pack(30, list_balls)
p.run()
plt.axes()
# Big container
circle = plt.Circle((0, 0), radius=30, fc='none', ec='k')
plt.gca().add_patch(circle)
for c in list_balls:
ball = plt.Circle((c.x, c.y), radius=c.r, picker=True, fc='none', ec='k')
plt.gca().add_patch(ball)
plt.axis('scaled')
plt.show()
The code was originally written with Processing, I did my best to use numpy instead.
I'm not quite sure of my checkBallPosition, the original author uses a count variable that looks useless to me. I also wonder why the steer vector in the original code has a dimension of 3.
So far, here is what my code yields:
The circles (I had to rename them balls to not conflict with Circle from matplotlib) overlap and don't seem to get away from each other. I don't think I'm really far but I would need a bit of help to find what's wrong with my code. Could you help me please ?
EDIT: I realize that I probably need to do several passes. Maybe the Processing package (language ?) runs the run function several times. It actually makes sense to me, this problem is very similar to molecular mechanics optimization and it's an iterative process.
My question can now be a bit more specific: it seems the checkBorders function doesn't do its job properly and doesn't rebound the circles properly. But given its simplicity, I'd say the bug is in applySeparationForcesToBall, I probably don't apply the forces correctly.
Solution
Ok after days of fiddling, I managed to do it:
Here is the complete code:
#!/usr/bin/python
# coding: utf-8
"""
http://www.codeplastic.com/2017/09/09/controlled-circle-packing-with-processing/
https://stackoverflow.com/questions/573084/how-to-calculate-bounce-angle/573206#573206
https://stackoverflow.com/questions/4613345/python-pygame-ball-collision-with-interior-of-circle
"""
import numpy as np
import matplotlib.pyplot as plt
from random import randint
from random import uniform
from matplotlib import animation
class Ball:
def __init__(self, x, y, radius):
self.r = radius
self.acceleration = np.array([0, 0])
self.velocity = np.array([uniform(0, 1),
uniform(0, 1)])
self.position = np.array([x, y])
@property
def x(self):
return self.position[0]
@property
def y(self):
return self.position[1]
def applyForce(self, force):
self.acceleration = np.add(self.acceleration, force)
def _normalize(self, v):
norm = np.linalg.norm(v)
if norm == 0:
return v
return v / norm
def update(self):
self.velocity = np.add(self.velocity, self.acceleration)
self.position = np.add(self.position, self.velocity)
self.acceleration *= 0
class Pack:
def __init__(self, radius, list_balls):
self.iter = 0
self.list_balls = list_balls
self.r = radius
self.list_separate_forces = [np.array([0, 0])] * len(self.list_balls)
self.list_near_balls = [0] * len(self.list_balls)
self.wait = True
def _normalize(self, v):
norm = np.linalg.norm(v)
if norm == 0:
return v
return v / norm
def run(self):
self.iter += 1
for ball in self.list_balls:
self.checkBorders(ball)
self.checkBallPositions(ball)
self.applySeparationForcesToBall(ball)
print(ball.position)
print("\n")
def checkBorders(self, ball):
d = np.sqrt(ball.x**2 + ball.y**2)
if d >= self.r - ball.r:
vr = self._normalize(ball.velocity) * ball.r
# P1 is collision point between circle and container
P1x = ball.x + vr[0]
P1y = ball.y + vr[1]
P1 = np.array([P1x, P1y])
# Normal vector
n_v = -1 * self._normalize(P1)
u = np.dot(ball.velocity, n_v) * n_v
w = np.subtract(ball.velocity, u)
ball.velocity = np.subtract(w, u)
ball.update()
def checkBallPositions(self, ball):
i = self.list_balls.index(ball)
# for neighbour in list_neighbours:
# ot a full loop; if we had two full loops, we'd compare every
# particle to every other particle twice over (and compare each
# particle to itself)
for neighbour in self.list_balls[i + 1:]:
d = self._distanceBalls(ball, neighbour)
if d < (ball.r + neighbour.r):
return
ball.velocity[0] = 0
ball.velocity[1] = 0
def getSeparationForce(self, c1, c2):
steer = np.array([0, 0])
d = self._distanceBalls(c1, c2)
if d > 0 and d < (c1.r + c2.r):
diff = np.subtract(c1.position, c2.position)
diff = self._normalize(diff)
diff = np.divide(diff, 1 / d**2)
steer = np.add(steer, diff)
return steer
def _distanceBalls(self, c1, c2):
x1, y1 = c1.x, c1.y
x2, y2 = c2.x, c2.y
dist = np.sqrt((x2 - x1)**2 + (y2 - y1)**2)
return dist
def applySeparationForcesToBall(self, ball):
i = self.list_balls.index(ball)
for neighbour in self.list_balls[i + 1:]:
j = self.list_balls.index(neighbour)
forceij = self.getSeparationForce(ball, neighbour)
if np.linalg.norm(forceij) > 0:
self.list_separate_forces[i] = np.add(self.list_separate_forces[i], forceij)
self.list_separate_forces[j] = np.subtract(self.list_separate_forces[j], forceij)
self.list_near_balls[i] += 1
self.list_near_balls[j] += 1
if np.linalg.norm(self.list_separate_forces[i]) > 0:
self.list_separate_forces[i] = np.subtract(self.list_separate_forces[i], ball.velocity)
if self.list_near_balls[i] > 0:
self.list_separate_forces[i] = np.divide(self.list_separate_forces[i], self.list_near_balls[i])
separation = self.list_separate_forces[i]
ball.applyForce(separation)
ball.update()
list_balls = list()
for i in range(25):
# b = Ball(randint(-15, 15), randint(-15, 15), 5)
b = Ball(0, 0, 5)
list_balls.append(b)
p = Pack(30, list_balls)
fig = plt.figure()
circle = plt.Circle((0, 0), radius=30, fc='none', ec='k')
plt.gca().add_patch(circle)
plt.axis('scaled')
plt.axes().set_xlim(-50, 50)
plt.axes().set_ylim(-50, 50)
def draw(i):
patches = []
p.run()
fig.clf()
circle = plt.Circle((0, 0), radius=30, fc='none', ec='k')
plt.gca().add_patch(circle)
plt.axis('scaled')
plt.axes().set_xlim(-50, 50)
plt.axes().set_ylim(-50, 50)
for c in list_balls:
ball = plt.Circle((c.x, c.y), radius=c.r, picker=True, fc='none', ec='k')
patches.append(plt.gca().add_patch(ball))
return patches
co = False
anim = animation.FuncAnimation(fig, draw,
frames=500, interval=2, blit=True)
# plt.show()
anim.save('line2.gif', dpi=80, writer='imagemagick')
From the original code, I modified the checkBorder function to bounce the circles properly from the edge, and changed the separation force between circles, it was too low. I know my question was a bit too vague from start, but I would have appreciated a more constructive feedback.
- What does cls() function do inside a class method?
- Load Registered Component in Azure ML for Pipeline using Python sdk v2
- Can I add message to the tqdm progressbar?
- How can I preserve the previous value to find the row that is greater than it?
- What's a correct and good way to implement __hash__()?
- Python Harvesters Image Acquisition GigeCam
- Why do I get a recursion error when the depth of the expected recursion should be way less than 999?
- How to (intermittently) skip certain cells when running IPython notebook?
- How to give jupyter cell standard input in python?
- Connect EtherCAT Device with pysoem
- Regex to substitute the next two words after a matching point
- What is the time complexity of heapq.nlargest?
- How to check if a given number is a power of two?
- How to move Jupyter notebook cells up/down using keyboard shortcut?
- cannot override sys.excepthook
- Getting Python's unittest results in a tearDown() method
- Is redis in Python asynchronous?
- How to tell Click to always show option defaults
- flask sqlalchemy with circular imports with db models
- .join with a query
- Python's argparse to show program's version with prog and version string formatting
- classifiers in scikit-learn that handle nan/null
- How does improve detection of line in images by open cv?
- Performance Advantages to Iterators?
- Problem with selecting a specific web element with Playwright in Python
- Thread long running python task, doesn't work inside Docker
- How to add a column with JSON representation of rows in Polars DataFrame?
- Pandas insert empty row at 0th position
- What should HTTP 201 response body be when responding to a POST request with large data?
- Can Python's unittest test in parallel, like nose can?