algorithm - 高效的二维切割算法

Question

我需要为一台铣出部分铝块的机器设计一个程序。零件是二维的。铣削每个零件所需的时间相当长。

我正在寻找一种算法来找到在最短的时间内磨出这些零件的解决方案。该机器将铝从块体中移除以构建最终形状，因此可能的铣削路径几乎是无限的。谁能指出我正确的方向或提出解决此问题的方法？我不知道这样的算法是否存在。

由于我需要自己实现这个算法，所以在算法的复杂性和实现的难易度之间需要权衡。

更新：我在下面添加了一个示例形状。带有对角线的部分是最终形状，虚线矩形是起始铝块。机器需要去除除对角线区域外的所有铝。

Answer 1

我认为这比您描述的要复杂得多。最终切割的质量、切割速度（取决于您要去除的体积）、是否可以更换钻头、如何夹紧材料等可能存在限制。

但只是从表面上考虑您的要求，我建议：

• 按照轮廓切割形状。

• 识别剩余的材料并使用光栅扫描（从一侧到另一侧，在每一端向下移动位宽）来吃掉材料

这为您提供了不错的光洁度（轮廓是单次切割，因此只有一个关节，可以在拐角处）和合理的速度（您试图最大限度地减少不切割所花费的时间，这只会发生在从一个扫描区域移动时给另一个）。