最优细分(即曲面细分/分割)2d多边形到较小多边形的算法？

Question

我有一些2D多边形,每个都是一个顺时针坐标列表.多边形很 简单(即它们可能是凹的但它们本身不相交)并且它们彼此不重叠.

我需要将这些多边形细分为更小的多边形以适应大小约束.就像原始多边​​形一样,较小的多边形应该是简单的(非自相交),并且约束是它们应该在一个'单位平方'内(为简单起见,我可以假设为1x1).

问题是,我需要尽可能高效地完成这项工作,其中"高效"意味着可能产生的最小数量(小)多边形.计算时间并不重要.

对此有一些智能算法吗？起初我想过递归细分每个多边形(将它分成两半,水平或垂直,无论哪个方向更大)都可以工作,但我似乎没有得到非常优化的结果.有任何想法吗？

Answer 1

绘制一个圆,其中心为初始多边形的初始点之一和所需长度约束的半径.

圆圈将在两个点处相交至少两条线.现在你的第一个三角形尽可能大.然后选择那些交叉点作为下一个目标.直到外面没有任何初始点.你的三角形尽可能大(尽可能少)

• 不要将已创建的三角形边缘视为交叉点.
• 产生的多边形不总是三角形,它们也可以是四边形.也许更大的点数!
• 它们几乎都等于所需的尺寸.

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