haar_lib/geom/
convex_diameter.rs

1//! 凸多角形の直径
2
3use crate::geom::*;
4
5/// 凸多角形の直径を求める
6pub fn convex_diameter(ps: &[Vector]) -> f64 {
7    let n = ps.len();
8
9    let mut i = ps
10        .iter()
11        .enumerate()
12        .min_by(|(_, p), (_, q)| p.1.partial_cmp(&q.1).unwrap())
13        .unwrap()
14        .0;
15    let mut j = ps
16        .iter()
17        .enumerate()
18        .max_by(|(_, p), (_, q)| p.1.partial_cmp(&q.1).unwrap())
19        .unwrap()
20        .0;
21
22    let mut ret = (ps[i] - ps[j]).abs();
23
24    for _ in 0..2 * n {
25        if (ps[(i + 1) % n] - ps[i]).cross(ps[(j + 1) % n] - ps[j]) > 0.0 {
26            j = (j + 1) % n;
27        } else {
28            i = (i + 1) % n;
29        }
30
31        ret = ret.max((ps[i] - ps[j]).abs());
32    }
33
34    ret
35}