将 2d 多边形最佳分割(即镶嵌/分区)到更小的多边形的算法？

Question

我有一些二维多边形，每个多边形都是顺时针坐标列表。多边形是 simple (即它们可能是凹形的，但它们本身不相交)并且彼此不重叠。

我需要将这些多边形分割为更小的多边形以适应大小限制。就像原始的多边形一样，较小的多边形应该是简单的(非自相交的)并且约束是它们每个都应该适合一个“单位正方形”(为了简单起见，我可以假设为 1x1)。

问题是，我需要尽可能高效地执行此操作，其中“高效”意味着生成的(小)多边形数量最少。计算时间并不重要。

是否有一些智能算法？起初我想递归地分割每个多边形(将其分成两半，水平或垂直方向较大)这是有效的，但我似乎没有得到非常理想的结果。有什么想法吗？

Answer 1

画一个圆，圆心为初始多边形的初始点之一，半径为所需长度约束。

圆将在两点处至少与两条线相交。现在你有了第一个尽可能大的三角形。然后选择这些路口作为下一个目标。直到外面没有初始点为止。你的三角形尽可能大(尽可能少)

• 不要将已创建的三角形边视为交点。
• 生成的多边形并不总是三角形，它们也可以是四边形。也许还有更大的点数!
• 它们都几乎等于所需的大小。

微调内部零件需要一些计算。