一种高效的2D切割算法

Question

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

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

由于我需要自己实现此算法，因此需要在算法的复杂性和实现的简易性之间进行权衡。

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

​

​

Answer 1

我认为这比你所描述的要复杂得多。最终切割的质量、切割的速度(取决于要移除的体积)、是否可以更改钻头、如何夹紧材料等方面可能存在限制。

但仅从表面上考虑您的请求，我建议：

按照轮廓切割剩余的材料，并使用栅格扫描(左右移动，两端按位宽向下移动)来吃掉材料

这会给你一个很好的完成(轮廓是一个单一的切割，所以只有一个关节，可以在角落)和合理的速度(你试图最小化不切割的时间，只有在从一个扫描区域移动到另一个扫描区域时才会如此)。