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.
- Convert Categorical codes to Categorical values
- Python-Sphinx: "inherit" method documentation from superclass
- Getting Home Directory with pathlib
- How to redirect the user back to the home page using FastAPI, after submitting an HTML form?
- No FileSystem for scheme: s3 with pyspark
- How to add a state to a Selection field and show it ordered in the statusbar in Odoo 11?
- Breaking long method chains into multiple lines in Python
- Enable ruff rules only on specific files
- Filter by time in DRF
- Plotting lambda functions in Python and mpmath.plot
- How to remove Empty Rows from a list in Python 3.5
- matplotlib 3D scatter plot alpha varies when viewing different angles
- How to write very long string that conforms with PEP8 and prevent E501
- how to avoid bot detection on websites using selenium python
- Python mock to create a fake object return a dictionary when any of its attributes are used
- Polars vs. Pandas: size and speed difference
- How to mock.patch a class imported in another module
- Python - error cannot determine truth value of Relational (Newton-Raphson)
- ProcessPoolExecutor logging fails to log inside function on Windows but not on Unix / Mac
- SQLAlchemy ORM Insert or Update when importing from JSON
- django managers vs proxy models
- Pytroch clamp for complex values
- For every identifier select only rows with largest order column
- truth value for Expr is ambiguous in with_columns ternary expansion on dates
- Remove equal characters from two python strings
- Python pyad module can't set UPN
- Macro VS Micro VS Weighted VS Samples F1 Score
- Printing a Tree data structure in Python
- How to fix/reset decreasing timestamps while preserving gaps in time-series data for CNN training?
- Test that module is NOT imported