2D多边形最佳细分（即镶嵌/分割）算法是什么？

Question

我有一些二维多边形，每个多边形都是一个顺时针坐标列表。这些多边形是simple的（即它们可能是凹多边形，但不会自相交），它们之间也不会重叠。

我需要将这些多边形细分为更小的多边形以适应尺寸约束。与原始多边形一样，这些小多边形应该是简单的（非自相交），约束条件是它们应该每个适合一个“单位正方形”内（为了简单起见，我可以假设为1x1）。

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

是否有一些聪明的算法可以实现这一点？起初，我考虑递归地细分每个多边形（将其水平或垂直地分成两半，取决于哪个方向更大），这种方法可以工作，但我似乎无法获得非常优化的结果。有什么想法吗？

- Sheldon Pinkman

---

你需要类似于“三角剖分器”的东西吗？ - huseyin tugrul buyukisik

@tuğrul büyükışık：（哦，之前有一个关于20x20正方形的问题 - 以防万一：是的，如果我有一个20x20的正方形，在这种情况下最佳的细分将是400个1x1的正方形）关于“三角剖分器”：我不确定，我认为不是，较小的多边形不需要是三角形。只要它适合1x1的正方形，它可以是任何随机的简单多边形。 - Sheldon Pinkman

允许旋转多边形吗？ - Qnan

什么对你来说是最优结果？结果多边形/顶点数量较少？ - ltjax

@ltjax 在文本中已经提到了，最优的细分是多边形数量最少的那个。 - Qnan

@SheldonPinkman：只是出于好奇：你是用这个做什么的？纹理映射吗？ - ltjax

Answer 1

在一个多边形的初始点之一作为圆心，选择你想要的长度约束作为半径画一个圆。

该圆将与至少两条线相交于两点。现在通过最大化尽可能大的三角形来选择这些交点作为下一个目标。直到没有初始点在外面为止，重复进行。这样你得到的三角形尽可能大(也就是尽量少)。

• 不要将已经创建的三角形边界计算在交点内。
• 结果形状不总是三角形，它们也可以是四边形。也许还有更大的点数!
• 它们几乎都与所需的大小相等。

微调内部部分需要一些计算。

- huseyin tugrul buyukisik

---

你第四张图片中的四个点（1个黑色，3个红色）构成了最终图片中最左边的四边形。由于它有一个邻边长度为1的钝角，所以该四边形无法放入任何单位正方形中。最终图片中除了一个菱形外，所有的菱形似乎都有同样的问题。更明确地说：画一个标准的单位正方形，将其平移和旋转直到其底部与一个单位长度且毗邻一个钝角的菱形边重合。然后，从该角度出发的一条线段的端点在平移旋转后的单位正方形之外。 - James Waldby - jwpat7

你是对的。你是在说使用正方形来表示“这个例子中的钻石”还是整个形状从一开始就用正方形？ - huseyin tugrul buyukisik

一个简单的修复方法是在每个菱形的较短对角线上画一条直线。请注意，对于圆形方法，假设ABC和CDE是原多边形的边，角ACE锐角，BC，CD单位长度。ABD和BDE都是钝角。如果BD超过单位长度，我不知道你的方法会怎么做。然而，详细说明您的圆形方法可能并不值得：移动正方形的方法可能更简单。即，沿着多边形的每条边滑动一个单位正方形，并在多边形内递归；我想交点计算比圆形更简单。 - James Waldby - jwpat7

太棒了，兄弟！非常感谢你提供如此详尽的描述！我正在仔细阅读以完全理解它。不过有一件事：大小限制意味着单位正方形（任何子多边形都应适合其中）不能旋转。但我想这并不难解决（将圆的半径和连接标准除以sqrt(2)或其他值即可）。 - Sheldon Pinkman

Answer 2

我建议您采用以下方法：

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

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

3. 使用动态规划来连接三角形，同时保持约束条件并只连接相邻的多边形。

- ltjax