wikipedia Polygon triangulation
Polygon triangulation without extra vertices
Special cases
NOTE:
1、这就是"凸多边形的三角剖分",这是DP中的一类问题
It is trivial to triangulate(把…分成三角形,三角剖分) any convex polygon in linear time into a fan triangulation, by adding diagonals from one vertex to all other vertices.
The total number of ways to triangulate a convex n-gon by non-intersecting diagonals is the (n−2)nd Catalan number.