这是一个创建于 1098 天前的主题，其中的信息可能已经有所发展或是发生改变。
现在有一个坐标围成的 Polygon ，例子坐标如[[0,0], [0,10], [15,10], [15,20], [20,20], [20,5], [5,5]]，现在想要把这个图形切割成三块 [矩形] ，如[[0,0], [0,10], [5,10], [5,0]]就是其中一块，思索了三天，没有任何头绪。用二维图像布尔计算也无法直接提取出来其中的矩形，有大佬有思路吗？
 | 1 xing7673 2022-10-12 01:20:19 +08:00 via iPhone 实在不行就暴力搜索，对每个节点都 90 度延长线 |
 | 2 Xs0ul 2022-10-12 01:42:38 +08:00 1. 切割的块数 n=3 是确定的吗？ 2. 输入确保有解吗？ 1 、2 的回答都是 yes 的情况下，也许可以穷举出所有可能的形状。或者把问题简化成，先切掉一个矩形，剩下的图形能不能分割成俩矩形 |
 | 3 also24 2022-10-12 01:55:28 +08:00 我没太理解题目，你是说这个形状，能够被切割成三块 矩形 么？ 而且黄色的还是其中一块？  |
 | 6 bluebirdv2 2022-10-12 02:11:33 +08:00 三个矩形要求覆盖, 只有八个自由度. 首先搜索两条边, 分别作为两个矩形的一条边. 由于覆盖要求确定两个矩形就可以了, 剩下的矩形直接用其他两个的边. 确定两个矩形 1 条边后, 只需要确定这两个 x 偏移. 根据覆盖要求, 只需要写出方程. 要求这两条边, 相互平行是矩形. |
 | 7 documentzhangx66 2022-10-12 03:01:49 +08:00 这还不简单，以 5 楼的形状为例，直接让每条边，在限制区域内，向两端延伸，必然能得到切点的坐标。 被切成的小块，能组成好几种 3 个矩形。 |
 | 8 ynyounuo 2022-10-12 03:26:44 +08:00 搜索 rectangulation algorithm 有挺多线程的例子 比如： https://www.cise.ufl.edu/~sahni/papers/part.pdf |
| 9 ynyounuo 2022-10-12 03:26:55 +08:00 现成* |
Select Language