输入网格可能非常复杂，可能包含多个孔。顶点的位置不限于网格。
此用例是为Box2D物理引擎创建多个多边形。
其他信息：
结果不必是确定性的。
结果不需要垂直条纹。
正如trichoplax所指出的那样，图片的右侧部分与可以达到的最小多边形数量不一样。这只是一个例子。
并不一定要找到凸多边形的绝对最小值。快速算法比“最佳解决方案”更可取。
#1 楼
如果边角是凹形的，则需要将输出多边形中的2个作为边界。所以一种算法是找到所有凹角（包括孔中的那些）并从它们开始进行切割其他凹角。这会将多边形分为两部分，或将2个孔合并为1个孔，或将一个孔连接到外部。
从凹角切割时应限制角度，否则会产生新的凹角，然后需要再次切割。
评论
我注意到示例输出根据定义不是最小的（存在覆盖网格的5个凸多边形的排列）。是因为这仅仅是一个示例，还是有其他要求阻止5个多边形的输出有效？例如，是否需要将输出多边形设置为固定宽度的垂直条，还是仅用于示例图像？谢谢trichoplax。我已将请求的其他信息添加到该问题。希望他们能澄清您的问题。
我已经确定了示例输出与我所想到的最小输出之间的区别：我的生产使用仅使用现有顶点但不使用现有三角形的凸多边形覆盖区域。如果需要从现有三角形构造凸多边形，则示例输出显示最小数量的凸多边形。这是一个要求吗？
不，这不是必需的。可以使用任何可用方式生成结果多边形。唯一的要求是，生成的形状与三角形完全相同。
这个问题被称为凸分解。参见gamedev.stackexchange.com/q/53142，doc.cgal.org/latest/Partition_2/index.html#title2，masc.cs.gmu.edu/wiki/ACD