geometry - 如何用特定区域的较小多边形拟合多边形

Question

我想将多边形划分为具有特定区域且没有特定维度的非重叠多边形。多边形应该是矩形的。您可以添加积分。

输入多边形：

期望的输出（请注意所有的线都是直的）：

请忽略断开的线路。输入将是多边形的数量和每个多边形的面积。

所以，我想知道如何解决这个问题？

标签： geometrydynamic-programmingcomputational-geometry

Answer 1

我将在下面假设输入多边形上的所有角度都是直角。

起初我被你的数字弄糊涂了，因为矩形有不同的面积，解决这个问题很容易，只需修改耳朵切割算法以使用正方形而不是三角形（它的工作原理是直角）。如果它们只需要具有相同的面积，您只需将每个生成的矩形划分为较小的矩形，其大小与您迄今为止找到的所有矩形的面积的最大公约数相同。然后，我要解决该区域的特定预选值的问题。

关于我们可以用来解决这个问题的解决方案的性质有一些认识（假设给定的实例是可解决的）。

第一个实现是多边形需要其面积可被特定面积整除，并且多边形的任何细分也必须满足这一点。

第二个实现是，将具有可被特定区域整除的区域的矩形细分为正确大小的较小矩形是微不足道的，只需将其沿其中一个方向划分为正确数量的切片即可。

第三个认识是我们需要减少多边形的复杂性，直到我们只剩下矩形。具体来说，必须存在一组细分，每个细分都具有正确区域的倍数，并且每个细分都形成一个矩形。

第四个实现是第三个实现的（一组）细分必须使其内部边界是我们开始的多边形的内部凹角的延伸。理解为什么会这样可能有点棘手，但如果我们没有这样的扩展，那么在这样一个细分的一侧，我们需要越过这条线，并且生成的形式不会降低它的复杂性，无论我们继续细分多少次，我们都将不断被迫侵入另一个矩形的一部分区域，这意味着矩形的复杂性也会增加，因此我们永远无法消除复杂性。

换句话说，找到将多边形适当划分为特定区域的矩形的一种方法是首先沿着凹角延伸的线寻找多边形的细分（其中每边的面积是特定区域的倍数） area) 直到所有的细分都变成矩形。如果失败，则不存在合适的细分。如果成功，剩下的就是细分这些矩形，如前所述。

应该注意，可能存在不符合实现 3 和 4 中描述的细分的此类矩形的细分，但它们仅在可以进行这种合适的划分时才存在，因为它们实际上只是矩形的重新排列，使得他们跨越了这些细分。