Nik*_*des 7 time-complexity computational-geometry
我有SVG的无线路径,我需要在给定的矩形内尽可能有效地打包(尽可能减少空间浪费).经过一些研究,我发现了bin打包算法,它似乎是处理盒子而不是弯曲的随机形状(我的SVG形状非常复杂,包括beziers等).
AFAIK,没有用于实际打包抽象形状的确定性算法.
我希望在这里被证明是错误的,这将是理想的(有一个数学确定性方法来包装它们).如果我是对的而且没有,那么这个问题的最佳方法是什么
主题名称是形状嵌套,嵌套问题或嵌套过程.
在形状嵌套中,没有单一/统一的算法或数学方法来嵌套形状并且可以获得最少的空间浪费.
第一种方法是打包算法(为每个形状创建一个虚构的边界框,并使用矩形2D算法来打包边界框).这种方法速度快,但在空间浪费方面效率最低.
第二种方法是某种增量旋转.该算法以增量步长旋转形状并检查它是否适合空间.在空间浪费方面,这比包装方法更好,但是它的速度非常慢,
有哪些其他课堂示例可以解决这个问题？
[编辑1]新答案
正如之前提到的，装箱是 NP 完全的（困难），所以忘记代数解已知的方法是：
生成并测试
要么测试问题的所有可能性并记住最佳解决方案，要么以相同的方式逐项添加项目（不是一次全部）。基本上，如果没有适当的启发式方法，您现在所做的事情就会慢得无法使用。但具有最好的空间效率（第一个好得多，但慢得多）O(N!)
利用按尺寸对物品进行排序的优势
像这样的东西几乎快得多O(N.log(N))（根据使用的排序算法）。空间效率很大程度上取决于物品的尺寸范围和数量。对于矩形形状，这是最好的方法（甚至对于 来说也是最快且可用的N>1000）。对于复杂的形状这不是一个好方法，但无论如何看看它也许你会得到一些想法......
神经网络的使用
这是极其模糊的方法，没有任何解决方案的保证，但可能是最佳的空间效率/运行时间比
我认为可能有一些现场方法
我播种了一些来生成图形布局。所有物品都会产生场（展位有吸引力和令人厌恶），因此它们正在进入半稳定状态。
这种方法比泛型和测试要快得多，并且可以提供非常接近的解决方案，但如果未最佳选择字段，它可能会停留在局部最小值/最大值或振荡。例如，所有物体彼此之间可以具有恒定的吸引力，并且只有当物体非常接近时排斥力才会变得更强。您必须防止物品重叠（通过更强的排斥力或通过碰撞测试）。您还必须创建一些旋转力矩，例如使用排斥力。它在任何顶点上都不同，因此会产生旋转力矩（可以自动将相似的边更靠近地对齐）。此外，您还可以在项目之间具有较大距离的半稳定状态，在找到最佳解决方案后，只需关闭排斥场，以便它们粘在一起。有时它可以得到更好的结果，有时却不能......这是图形布局计算的一个很好的例子
这里是用于在 2D 中放置滑块的解算器：
[Edit0] 重新表述问题之前的旧答案
我不清楚你想实现什么目标。
[1的解决方案]
另一种不精确但更简单的方法是：