这是一个创建于 776 天前的主题，其中的信息可能已经有所发展或是发生改变。
现在有一个坐标围成的 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