首先,来说以个问题;若该多边形为凸多边形的话,
那么设 d(i,j)代表以i节点为起点以j为最后一个点组成的多边形的最大面积最小的剖分;
有状态转移式子 d(i,j) = min( d[i][j] , max( max(d(i,k),d(k,j) ),s(i,k,j) )) (其中i<k<j ,s(i,k,j)为三点组成的三角形面积);
但对于不是凸多边形的话,上述式子在对k决策时,要额外满足一个条件i-->k,k-->j 两条线段必须都是多边形的对角线;
判断是否为对角线的话
首先该线段不和任一条边相交(不包括在端点相交),其次该线段在多边形内部;(判断第二个条件时,因为没......
阅读全文