Skip to content

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.