algorithm - 如何用不相交的旋转矩形填充矩形区域？

Question

我尝试为物理模拟创建一个场景。该场景由漂浮在矩形池塘中的矩形漂浮物组成。像这样的东西：

所以我需要用宽度和高度在指定范围内的不相交的旋转矩形填充一个矩形区域。我不需要找到该区域的最佳覆盖范围。目标只是生成没有交叉点的不同大小的漂浮物。

我想得到一个没有任何动态的解决方案，只使用碰撞检测算法。

Answer 1

您可以考虑模拟一组盒子落入方形桶中，并在所有盒子静止后保存它们的位置。

box2d是一个开源的 2D 物理库，可以为您执行此操作 - 您可能会认为它是 Angry Birds 和数以百万计的 Flash 游戏背后的物理引擎。

Answer 2

要对实体（即不相交）对象建模，您可以使用物理引擎。碰巧的是，前几天我刚刚阅读了面向绝对初学者的 Farseer 教程，其中包括一个几乎完全符合您要求的视频。Farseer是 box2d 的 .NET 版本，您可能听说过。

Answer 3

我会做的是：

假设矩形的长度在 [MaxSize MinSize] 之间

r <- MaxSize

do{
  Trying adding non-intersecting circles to the area with radius r and random center (x,y). We use circle instead of rectangle because intersection detecting for circles are easier than rectangles. e.g. if distance(x,y,x',y')<r+r' then we are good.

  If adding circle failed{
    r--;
    if r< MinSize break;
  }
}

现在您将拥有一个充满相交正方形的平面。因为我们使用圆圈作为交叉点检测，所以会有间隙。如果这对您来说还不够好，请将正方形变成矩形。您可以通过检查某个边界上的所有点并决定您可以增长多少来做到这一点。