algorithm - 高效的帧切割算法

Question

遇到了最初看起来很简单的问题；但是，我找不到有效的解决方案。你们能帮忙吗？

---

工作表由不同长度和宽度的矩形(框架)组成，这些矩形(框架)可能有间隙但不相交。找到分隔这些矩形的最少直线切割(垂直或水平)。必须通过整个可用板进行切割。

输入由矩形的数量和每个矩形的左上角和右下角坐标组成。如果没有解决方案，输出应包含切割次数，后跟代表垂直/水平切割或 NA 的 2 个点。请注意，可能存在多个最佳解决方案。

输入:

(3,3)

(0,0) (1,1)

(2,0) (3,1)

(0,2) (3,3)

输出:

2

(0,2) (2,2)

(1,0) (1,2)

输入:

(5,5)

(0,0) (3,1)

(4,0) (5,3)

(0,2) (1,5)

(2,4) (5,5)

输出:

不适用

Answer 1

这是 P. Y. Wang 的自底向上二维算法(作为一种可能的方法)解决下料问题的经典示例。

Google 搜索链接通常指向付费文章，但有些 publically available也可以找到描述(PDF version，第 6 页)