-150 -100 -50 0 50 100 150
-150
-100
-50
0
50
100
150
凸多边形
算法思想:
1. 由最高最低点中垂线得出相对中垂线的最大投影点和最小投影点(带符号);
2. 往最左边取凸多边形闭包点:
1) 得到的凸包点和产生凸包的“原始点”间分别再做一条中垂线;
2) 检测相对此中垂线是否产生了一个在连线左端的投影,如果如此将此点加入凸包点阵
中;
3) 如果所有凸包点阵中的点无法产生新的凸包点,算法结束;
3. 往最左边取凸多边形闭包点:与 2 中类似。
4. 求面积仍用“自然三角形”法,将凸包多边形切成自然三角形计算得面积。
关键步骤:
1. 最“左”点插入凸包点集与调用凸包:
1) 开始得到的两个起点的序号,放入点集 B 中;
所得新的最“左”投影点不断加入点集 B 中,新得到的 B 下一步又被调用,直到不再生成新的
凸包点…………
2. 最大最小的相对投影的求解[投影值 x,点序号 b
AB
]=min/max(所有点在 AB 点中垂线方向
上的投影);
最“左”点 1
最“右”点 1
最“左”点 2.1
最“左”点 2.2