Python 的受控圆包装
Controlled circle packing with Python
我正在尝试将我在此处找到的 "Controlled Circle Packing with Processing" 算法移植到 Python：
目前我的目标只是让它发挥作用，然后再根据自己的需要对其进行调整。这个问题不是关于做圆形包装的最佳方法。
到目前为止，这是我所拥有的：
#!/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()
代码本来是用Processing写的，我尽量改用numpy。
我不太确定我的checkBallPosition，原作者用了一个我看没用的count变量。我也想知道为什么原始代码中的 steer 向量的维度为 3.
到目前为止，这是我的代码产生的结果：
圆圈（我不得不将它们重命名为 balls 以不与 matplotlib 中的 Circle 冲突）重叠并且似乎没有远离彼此。我不认为我真的很远，但我需要一些帮助来找出我的代码有什么问题。你能帮帮我吗？
编辑：我意识到我可能需要做几遍。也许 Processing 包（语言？）多次运行 run 函数。其实对我来说很有意义，这个问题与分子力学优化非常相似，它是一个迭代过程。
我的问题现在可以更具体一些：checkBorders 函数似乎没有正常工作，也没有正确地反弹圆圈。但考虑到它的简单性，我会说错误在 applySeparationForcesToBall，我可能没有正确应用力。
好的，经过几天的摆弄，我设法做到了：
完整代码如下：
#!/usr/bin/python
# coding: utf-8
"""
http://www.codeplastic.com/2017/09/09/controlled-circle-packing-with-processing/
"""
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')
在原来的代码基础上，我修改了checkBorder函数，让圆从边缘适当反弹，并改变了圆与圆之间的分离力，太低了。我知道我的问题从一开始就有点太模糊了，但我希望能得到更有建设性的反馈。
我正在尝试将我在此处找到的 "Controlled Circle Packing with Processing" 算法移植到 Python：
目前我的目标只是让它发挥作用，然后再根据自己的需要对其进行调整。这个问题不是关于做圆形包装的最佳方法。
到目前为止，这是我所拥有的：
#!/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()
代码本来是用Processing写的，我尽量改用numpy。
我不太确定我的checkBallPosition，原作者用了一个我看没用的count变量。我也想知道为什么原始代码中的 steer 向量的维度为 3.
到目前为止，这是我的代码产生的结果：
圆圈（我不得不将它们重命名为 balls 以不与 matplotlib 中的 Circle 冲突）重叠并且似乎没有远离彼此。我不认为我真的很远，但我需要一些帮助来找出我的代码有什么问题。你能帮帮我吗？
编辑：我意识到我可能需要做几遍。也许 Processing 包（语言？）多次运行 run 函数。其实对我来说很有意义，这个问题与分子力学优化非常相似，它是一个迭代过程。
我的问题现在可以更具体一些：checkBorders 函数似乎没有正常工作，也没有正确地反弹圆圈。但考虑到它的简单性，我会说错误在 applySeparationForcesToBall，我可能没有正确应用力。
好的，经过几天的摆弄，我设法做到了：
完整代码如下：
#!/usr/bin/python
# coding: utf-8
"""
http://www.codeplastic.com/2017/09/09/controlled-circle-packing-with-processing/
"""
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')
在原来的代码基础上，我修改了checkBorder函数，让圆从边缘适当反弹，并改变了圆与圆之间的分离力，太低了。我知道我的问题从一开始就有点太模糊了，但我希望能得到更有建设性的反馈。