输入:凹多边形的顶点序列p1、p2、、、、pn;
输出:剖分形成的三角集合
剖分方法:
1) 从顶点p1开始,判断连续的三点p1p2p3组成的三角形是否为逆时针,若是则将三角型p1p2p3添加到三角型集合中,在顶点序列链表中去掉顶点p2,然后判断连续的三点p1p3p4是否构成逆时针三角形;若p1p2p3组成三角形为顺时针,则从p2点开始重复步骤1)继续处理顶点序列,相邻三点组成逆时针三角形,则从顶点序列中去掉中间点,并将该三角形添加到三角形集合中。
注:判断三角形ABC是否为逆时针,只需判定向量AC角度是否大于向量AB 或根据三角形面积是否为正判断。三角形面积为正,三角形为逆时针,否则为顺时针。
计算三角形面积公式:s = 0.5* | x1 y1 1 |
|x2 y2 1 |
|x3 y3 1 |
A(x1,y1) B(x2,y2) C(x3,y3)