algorithm - 将 2d 多边形优化细分（即镶嵌/分割）成更小的多边形的算法？

Question

我有一些 2D 多边形，每个都是顺时针坐标的列表。多边形很 简单（即它们可能是凹的，但它们不会相互交叉）并且它们不会相互重叠。

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

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

有一些智能算法吗？起初我考虑递归地细分每个多边形（将它分成两半，水平或垂直哪个方向较大），但我似乎没有得到非常理想的结果。有任何想法吗？

Answer 1

以初始多边形的初始点之一和所需长度约束的半径绘制一个圆。

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

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

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

Answer 2

我建议您使用以下内容：

1. 对多边形进行三角剖分，例如使用扫描线算法。

2. 确保所有三角形不违反约束。如果违反了约束，首先尝试边缘翻转来修复它，否则在最长的边上细分。

3. 使用动态编程连接三角形，同时保持约束并仅连接相邻的多边形。