将可调整大小的圆形图形放置在彼此附近

Question

我正在开发一个基于浏览器的实验，其中我有N个特定的圆形（假设它们里面有独特的图片），需要将它们紧密地排列在一起，尽可能减少它们之间的空隙。它不必被排列成一个圆形，但它们应该“聚集”在一起。

圆的大小是可定制的，用户可以通过拖动JavaScript滑块来更改大小，更改一些圆的大小（例如，在滑块的10％中，圆4的半径为20px，圆2为10px，圆5保持不变等）。如您可能已经猜到的那样，当移动滑块时，我将尝试使调整大小和重新定位平稳过渡。

我迄今尝试的方法：而不是手动尝试对它们进行定位，我尝试使用物理引擎-

思路：

1. 在屏幕中心放置某种重力吸引力
2. 使用物理引擎来处理球的碰撞
3. 在“拖动时间”滑块事件期间，我只会设置不同的球体尺寸，让引擎处理其余部分

为此任务，我使用了“box2Dweb”引擎。我将重力吸引放在屏幕中心，但是那花费了很长时间，直到球被放置在中心并开始漂移。然后我在中心放置了一个小的静态球体，使它们撞上它然后停止。看起来像这样：

结果稍微好了一些，但圆仍然在运动一段时间后才会静止。即使调整了变量，例如球体摩擦和不同的重力吸引，整个系统仍然只是漂移着，感觉非常“摇晃”，而我希望当我拖动时间滑块（更改大小时）时球能够移动。此外，box2d不允许更改对象的大小，我必须想办法解决这个问题。

所以，box2d方法让我意识到，也许让物理引擎处理这个问题不是最好的解决方案。或者可能我需要包括一些其他的力量，我还没有考虑到。我在StackOverflow上找到了一个与我的类似的问题，链接为this similar question。然而，非常重要的区别是它只一次生成一些n个不特定的圆圈，并且不允许额外的具体球大小和位置操作。

我现在真的很困惑，有没有人有任何想法来解决这个问题？

更新：现在已经过去将近一年了，我完全忘记了这个主题。最终我做的是坚持物理模型并在几乎空闲的条件下重置力量/停止。结果可以看到这里http://stateofwealth.net/你看到的三角形在这些圆圈内部。其余的线通过“Delaunay三角测量算法”连接。

- user151496

---

尝试线性和角阻尼。Box2d支持通过重新创建来调整大小（这是您的黑客吗？）。 - Pavel

是的，我正在Box2d中销毁和创建对象。然而，这会产生非常“跳跃”的结果。我觉得我选择了错误的框架来完成这个任务。我将在谷歌上搜索Box2d线性/角阻尼以获得更少抖动的模型，但我有点怀疑它能否解决我的问题。 - user151496

Answer 1

我记得看到一个非常类似于你所描述的 d3.js 演示，它是由 Mike Bostock 本人编写的：http://bl.ocks.org/mbostock/1747543

它使用四叉树进行快速碰撞检测，并使用基于力的图形，这两者都是d3.js实用程序。

在“tick”函数中，您应该能够添加一个“.attr（“ r”，function（d）{return d.radius;}）”，它将在更改“nodes”数据时每个“tick”更新半径。仅供初学者使用，您可以将其设置为随机返回，圆圈应该会疯狂抖动。

- gak

---

谢谢您的建议。我已经测试了这个引擎，它非常好！然而，在使用该引擎时，有一件事情让我感到困惑，这真是太可惜了，因为它很好——那就是：当我移动/调整圆圈时，它们重叠了:(对于我来说，圆圈不重叠非常重要，因为实验的主要方面是审美体验。我尝试寻找某种变量/设置，以实现即使在移动圆圈时也能进行精确定位碰撞检测，但不幸的是没有找到：/你知道怎么解决这个引擎的问题吗？ - user151496

不了解代码本身，似乎圆圈之间由于cluster()和力导向布局而重叠，但最终通过collision()随着时间的推移分离。也许如果您在每个刻度中更频繁地调用collision()，或者只是循环直到不再检测到碰撞。还有一个alpha变量（https://github.com/mbostock/d3/wiki/Force-Layout#wiki-alpha）可能很方便进行微调。 - gak

此外，如果您有更多问题，我建议您创建一个演示您的问题并在 d3.js 邮件列表上发布。他们通常非常乐意提供帮助。 - gak

谢谢你的建议，我一定会尝试使用collision()。只是希望之后不会太卡顿。 - user151496

Answer 2

（不是注释，因为它太长了）

我很欣赏你引入Box2D来帮助处理重力问题，但不幸的是，它可能并不适合你的要求，因为当你想要模拟刚体及其碰撞动态时，Box2D才能发挥最佳效果。

我认为，如果你真正考虑自己需要什么，这根本不是一个刚体动力学问题。你实际上不需要Box2D的任何复杂性，因为你的所有几何图形都由球体组成（我向你保证，这比任意凸多边形简单得多，这也是我认为Box2D的复杂性来源），而且正如你所提到的，Box2D无法平滑地改变几何参数，这会在浏览器中产生不必要的几何分配和释放，并且无法应用任何平滑的动画。

你可能正在寻找一种算法或方法，以演化一组坐标的位置（每个坐标都有一个半径，也可能在变化），使它们保持分离状态，并尽量减小到中心位置的距离。如果需要平滑过渡，你不能每次都应用最小解决方案，因为在滑块移动的特定点处，最优配置可能会发生巨大转变，从而导致“扭曲”。可以说，你需要进行很多调整，但并没有什么比 Box2D 内部必须处理的东西更可怕。

你的圆形不重叠有多重要？我认为你应该只做一个简单的迭代“求解器”，首先试图将圆形靠近它们的目标（屏幕中心？），然后基于半径尝试将它们分开。

我相信，如果你试图为所需运动制定一个简化的数学模型，这将比试图让 Box2D 做到更好。Box2D 是神奇的，但它只擅长于它所擅长的事情。

- Steven Lu

---

我没想到我的想法会给任何人留下深刻印象:D，实际上我认为使用物理学来解决我的问题是一种“愚蠢”的方法。我理解你的观点，对于我的问题来说，box2d有点过头了，因为我只想处理圆形而不是刚体。然而，当我只使用圆形时，box2d的计算非常快，因为我没有使用其他复杂的多边形。我甚至成功地通过快速销毁和创建它们来“平滑地”调整形状——但是——这就是帧率大幅下降的地方，这就是我现在要处理的问题。[评论太长，待续..] - user151496

对我来说，圆形不重叠非常重要，因为这样做可以提高视觉效果。但是拥有最小解决方案并不重要，另一个标准是平稳过渡（这就是为什么我选择了物理引擎）。实际上，我一开始尝试编写自己的简单碰撞圆逻辑，但失败了。圆形重叠，它只是跳来跳去的，等等。这就是为什么我决定从知道如何正确处理它的人那里选择一个引擎（并找到了box2d）。您知道是否有其他适合此问题的物理引擎吗？ - user151496

我仍然认为这不是物理问题。有哪些物理事物可以如此平滑地扩张和收缩呢？你可能需要开发一种新的数学分支来对其进行建模。在浏览器中使用像box2d这样的重量级工具（当你在循环中创建和销毁物体时，它只会无端地使你的浏览器垃圾回收器繁忙），这并不能让你更接近实现平稳运动的目标。 - Steven Lu

物理模型并不意味着模拟真实的物理现象，它可以是任何东西，如原子、弹簧等。目前为止，Box2D模型最接近我想要的。在这里有人提到的d3.js库（也使用了物理模型）也非常适合，但它存在重叠问题，这对我来说至关重要。Box2D帧率低的问题是由于其刚体模型导致对象需要重新创建。因此，除非我找到更好的模型来完成任务，否则我将被困在Box2D中。但如果您知道这个“数学模型”，我会很高兴使用它。毕竟，我在这里是因为卡住了。 - user151496

我的意思是，Box2D在其几何公式中没有努力融入动态半径的概念。这是完全可能的，如果它具备这种能力，那么它将非常适合您的使用。我已经深入研究了它的架构，并且我相信存在一种合理的方法来模拟这样的“膨胀”圆形几何体；这只是一个仅在像您这样的特定情况下才会派上用场的功能。它也可以用于模拟某种形式的爆炸冲击波，但即使是这样，我也更喜欢较为柔和的碰撞响应。 - Steven Lu

Answer 3

至少对我来说，似乎最简单的解决方案是首先在一个簇中设置圆。所以先将最大的圆放在中心，在第一个圆旁边放置第二个圆。对于第三个圆，你可以把它放在第一个圆旁边，然后沿着边缘移动直到它碰到第二个圆。

所有其他圆可以按照相同的方法：将其放置在任意一个圆旁边，然后沿边缘移动直到与另一个圆接触但不相交为止。请注意，这并不会使其成为最高效的聚类方法，但它确实有效。之后，当你扩展，比如说，圆1时，你会将所有相邻的圆向外移动，并重新排列它们以进行重新聚类。

- woojoo666

---

谢谢您的建议，圆形放置的想法非常好，但这种方法更适合静态的“设置并将其作为图片留下”的方法。该方法无法处理调整大小或移动圆圈时需要的动态/平滑过渡。 - user151496