# 7.3. 凸多边形的宽

## 7.3. 凸多边形的宽

1. 点-点对踵对

2. 边-边对踵对

1.    $m=-\infty$;
2.    for( i=1 ; i<n ; i++ )
3.           if $area({{p}_{n-1}},{{p}_{0}},{{p}_{i}})\succ m$, then                   //$area({{p}_{0}},{{p}_{1}},{{p}_{2}})\equiv ({{p}_{1}}-{{p}_{0}})\times ({{p}_{2}}-{{p}_{0}})$
4.                  k = i;
5.                  m = $area({{p}_{n-1}},{{p}_{0}},{{p}_{i}})$;
6.           end if;
7.    end for;
8.    $w=m/\left\| {{p}_{0}}-{{p}_{n-1}} \right\|$;
9.    for( i = 1 ; i < n ; i++ )
10.          $m=area({{p}_{i-1}},{{p}_{i}},{{p}_{k}})$;
11.          while(1)
12.                 if $area({{p}_{i-1}},{{p}_{i}},{{p}_{next(k)}})\prec m$, then           //$next(k)\equiv (k+1)%n$
13.                        break;
14.                 else
15.                        $m=area({{p}_{i-1}},{{p}_{i}},{{p}_{next(k)}})$;
16.                        $k=next(k)$;
17.                 end if;
18.          end while;
19.          if $w\succ m/\left\| {{p}_{i}}-{{p}_{i-1}} \right\|$, then
20.                 $w=m/\left\| {{p}_{i}}-{{p}_{i-1}} \right\|$;
21.          end if;
22.   end for;
23.   return w;