1 最小代价多边形三角剖分算法 凸多边形的三角剖分是通过在非相邻顶点（角点）之间绘制对角线来形成的，这样对角线就不会相交。问题是如何以最小的代价找到三角剖分的代价。三角剖分的代价是其组成三角形的权重之和。每个三角形的重量是其周长（所有边的长度之和） 请参阅以下来源的示例。 多项式三角 同一凸五边形的两个三角剖分。左侧的三角测量的成本为8+2√2+2√5（约15.30），右侧的成本为