7

我有 SVG 任意路径，我需要在给定的矩形内尽可能有效地打包（尽可能减少空间浪费）。经过一些研究，我发现 bin 打包算法似乎处理的是盒子而不是弯曲的随机形状（我的 SVG 形状非常复杂，包括贝塞尔曲线等）。

AFAIK，没有用于实际包装抽象形状的确定性算法。

我希望在这里被证明是错误的，这将是理想的（有一种数学确定性方法来打包它们）。如果我是对的但没有，那么解决这个问题的最佳方法是什么

主题名称是Shape Nesting、Nesting Problem 或 Nesting Process。

在形状嵌套中，没有单一/统一的算法或数学方法可用于嵌套形状并尽可能减少空间浪费。

  • 第一种方法是打包算法（为每个形状创建一个假想的边界框，并使用矩形 2D 算法来打包边界框）。这种方法速度快，但在空间浪费方面效率最低。

  • 第二种方法是某种增量旋转。该算法以增量步长旋转形状并检查它是否适合空间。就空间浪费而言，这比包装方法要好，但速度非常慢，

还有哪些其他课堂示例可以解决这个问题？

4

2 回答 2

3

[Edit1] 新答案

如前所述，装箱是 NP 完整的（硬），所以忘记代数解决方案已知的方法是：

  1. 生成和测试

    要么您测试问题的所有可能性并记住最佳解决方案，要么以相同的方式逐个添加项目（不是一次全部）。基本上，如果没有适当的启发式方法，您现在正在做的事情会非常缓慢。但是具有最佳的空间效率（第一个要好得多但要慢得多）O(N!)

  2. 利用按大小对项目进行排序

    像这样的东西几乎快得多O(N.log(N))（根据使用的排序算法）。空间效率很大程度上取决于物品的尺寸范围和数量。对于矩形形状，这是最好的方法（最快且可用于N>1000）。对于复杂的形状，这不是一个好方法，但无论如何看看它也许你会有一些想法......

  3. 神经网络的使用

    这是一种非常模糊的方法，没有任何解决方案的保证，但可能是最佳的空间效率/运行时间比

  4. 我认为可能会有一些现场方法

    我播种了一些用于生成图形布局。所有项目都创建了场（展位吸引和排斥），因此它们正在进入半稳定状态。

    • 起初，所有项目都在随机位置
    • 当运动停止时，记住最佳解决方案并稍微摇晃所有物品或再次随机化它们的位置。
    • 循环这几次

    这种方法比通用和测试要快得多，并且可以提供非常接近的解决方案，但它可以挂在本地最小值/最大值中或在未最佳选择字段时振荡。例如，所有物品彼此之间可以具有恒定的吸引力，只有当物品非常接近时，排斥力才会变得更强。您必须防止项目重叠（通过更强的排斥力或通过碰撞测试）。您还必须创建一些旋转力矩，例如使用该排斥力。它在任何顶点上都不同，因此它会产生旋转力矩（可以自动将相似的边对齐更近）。此外，您可以在项目之间具有较大距离的半稳定状态，并且在找到最佳解决方案后只需关闭排斥场，以便它们粘在一起。有时它可以有更好的结果，有时不是......这是图形布局计算的好例子

    这里是用于将滑块放置在 2D 中的求解器：

[Edit0] 重新制定问题之前的旧答案

我不清楚你想要实现什么。

  1. 有 SVG 图片并希望将其部分分隔为矩形区域
    • 尽可能填满
    • 最少的空间
    • 图片没有形状变化
  2. 有 svg 图片并想根据某些目的更改其形状
    • 如果是这种情况，需要一些额外的信息

[1的解决方案]

  1. 在全局 SVG 空间中为整个 SVG 创建一个点列表（所有点都被转换）
    • 对于线，你需要加 2 分
    • 对于矩形 4 点
    • 圆/椭圆/贝塞尔/椭圆弧 8 点
  2. 找到当地的质心
    • 使用经典方法
    • 或者可以通过分别计算每个 x,y 轴的平均点密度来加快速度，然后只需检查找到的局部最大密度位置的所有组合是否真的是子集群中心。
  3. 所有子集群中心都是您所在区域的中心
    • 现在找到仍然是集群一部分的最远点（离邻居点足够近）
    • 创建覆盖子集群中所有点的矩形区域。
    • 您还可以从列表中删除所有使用的点
  4. 重复所有有效的子集群
    • 直到所有点都用完

另一种不精确但更简单的方法是：

  1. 查找 SVG 大小
  2. 创建具有一定精度的 svg 平面图，例如 int map[256][256]。
    • 地图的大小可以是恒定的或与 SVG 具有相同的方面
  3. 用 0 清除地图
  4. 对于 SVG 的任何点，将相关地图点设置为 1（或 inc 或其他）
  5. 现在只需分割地图，您将找到您的对象
    • 分割后你有所有对象的位置和大小
    • 所以找到边界框应该很容易
于 2013-09-09T07:09:31.953 回答
1

您可以从矩形装箱算法的变体开始并添加旋转。有一种方法“Guillotine bin packer”，您可以在 github 下载论文和库。

于 2013-11-18T19:24:44.807 回答