有没有图形学大佬，球指点

[yirius]

现在有一个坐标围成的 Polygon ，例子坐标如[[0,0], [0,10], [15,10], [15,20], [20,20], [20,5], [5,5]]，现在想要把这个图形切割成三块 [矩形] ，如[[0,0], [0,10], [5,10], [5,0]]就是其中一块，思索了三天，没有任何头绪。用二维图像布尔计算也无法直接提取出来其中的矩形，有大佬有思路吗？

[xing7673]

实在不行就暴力搜索，对每个节点都 90 度延长线

[Xs0ul]

1. 切割的块数 n=3 是确定的吗？
2. 输入确保有解吗？

1 、2 的回答都是 yes 的情况下，也许可以穷举出所有可能的形状。或者把问题简化成，先切掉一个矩形，剩下的图形能不能分割成俩矩形

[also24]

我没太理解题目，你是说这个形状，能够被切割成三块 矩形 么？

而且黄色的还是其中一块？

[Xs0ul]

@also24 #3 看起来应该是描述里漏了个 [5,0] 的点

[also24]

@Xs0ul #4
哦哦，我也有错，我把 [5,5] 看成 [5,0] 了，这样就合理多了

[bluebirdv2]

三个矩形要求覆盖, 只有八个自由度. 首先搜索两条边, 分别作为两个矩形的一条边.
由于覆盖要求确定两个矩形就可以了, 剩下的矩形直接用其他两个的边.
确定两个矩形 1 条边后, 只需要确定这两个 x 偏移. 根据覆盖要求, 只需要写出方程. 要求这两条边, 相互平行是矩形.

[documentzhangx66]

这还不简单，以 5 楼的形状为例，直接让每条边，在限制区域内，向两端延伸，必然能得到切点的坐标。

被切成的小块，能组成好几种 3 个矩形。

[ynyounuo]

搜索 rectangulation algorithm 有挺多线程的例子
比如： https://www.cise.ufl.edu/~sahni/papers/part.pdf

[ynyounuo]

现成*