python - 用 Python 控制圆包装

Question

我正在尝试将我在此处找到的“带处理的受控圆打包”算法移植到 Python:

http://www.codeplastic.com/2017/09/09/controlled-circle-packing-with-processing/?replytocom=22#respond

目前我的目标只是让它发挥作用，然后再根据自己的需要对其进行调整。这个问题不是关于进行圆形包装的最佳方法。

到目前为止，这是我所拥有的:

#!/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 中，我可能没有正确应用力。

Answer 1

好吧，经过几天的摆弄，我设法做到了:

完整代码如下:

#!/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')

在原来的代码中，我修改了checkBorder函数，让圆圈从边缘适当反弹，并改变了圆圈之间的分离力，太低了。我知道我的问题从一开始就有点过于模糊，但我希望能得到更有建设性的反馈。