7.2. 凸多边形的直径

7.2. 凸多边形的直径

1.    i = n – 1;
2.    j = 0;
3.    while($$\operatorname{area}({{p}_{i}},{{p}_{next(i)}},{{p}_{next(j)}})\succ \operatorname{area}({{p}_{i}},{{p}_{next(i)}},{{p}_{j}})$$)             //$$area({{p}_{0}},{{p}_{1}},{{p}_{2}})\equiv ({{p}_{1}}-{{p}_{0}})\times ({{p}_{2}}-{{p}_{0}})$$
4.           j = next(j);                                                       // next(i) = (i + 1) % n
5.    end while;
6.    q = j;
7.    i = next(i);
8.    d = -1.0;                                                                 //凸多边形的直径
9.    while( j != 0 && i <= q)
10.          d =$$dist({{p}_{i}},{{p}_{j}})$$> d ?$$dist({{p}_{i}},{{p}_{j}})$$: d;
11.          while($$area({{p}_{i}},{{p}_{next(i)}},{{p}_{next(j)}})\succ area({{p}_{i}},{{p}_{next(i)}},{{p}_{j}})$$ )
12.                 j = next(j);
13.                 if  i != q || j != 0, then
14.                        d =$$dist({{p}_{i}},{{p}_{j}})$$> d ?$$dist({{p}_{i}},{{p}_{j}})$$: d;
15.                 else
16.                        return d;
17.                 end if;
18.          end while;
19.          if $$area({{p}_{i}},{{p}_{next(i)}},{{p}_{next(j)}})==area({{p}_{i}},{{p}_{next(i)}},{{p}_{j}})$$, then
20.                 if  i != q || j != n-1 , then
21.                        d =$$dist({{p}_{i}},{{p}_{next(j)}})$$ > d ?$$dist({{p}_{i}},{{p}_{next(j)}})$$: d;
22.                 else
23.                        d =$$dist({{p}_{next(i)}},{{p}_{j}})$$ > d ?$$dist({{p}_{next(i)}},{{p}_{j}})$$: d;
24.                        return d;
25.                 end if;
26.          end if;
27.          i = next(i);
28.   end while;
29.   return d;