haar_lib/geom/
convex_hull.rs

1//! 凸包
2
3use crate::geom::*;
4
5/// 凸包の上半分か下半分かを指定する
6#[derive(Clone, Copy, PartialEq, Eq)]
7pub enum Hull {
8    /// 上半分
9    Upper,
10    /// 下半分
11    Lower,
12}
13
14/// 上半分/下半分の凸包を求める
15pub fn half_hull(mut ps: Vec<Vector>, hull: Hull, eps: Eps) -> Vec<Vector> {
16    if ps.is_empty() {
17        return vec![];
18    }
19
20    ps.sort_by(|p, q| (p.0, p.1).partial_cmp(&(q.0, q.1)).unwrap());
21
22    if hull == Hull::Upper {
23        ps.reverse();
24    }
25
26    let mut ret = vec![*ps.last().unwrap()];
27    ps.pop();
28
29    while let Some(s) = ps.pop() {
30        if ret.len() == 1 {
31            ret.push(s);
32        } else {
33            let p = ret[ret.len() - 2];
34            let q = *ret.last().unwrap();
35
36            if eps.le((q - p).cross(s - p), 0.0) {
37                ret.push(s);
38            } else {
39                ret.pop();
40                ps.push(s);
41            }
42        }
43    }
44
45    ret
46}
47
48/// 凸包を求める
49pub fn convex_hull(ps: Vec<Vector>, eps: Eps) -> Vec<Vector> {
50    let mut ret = half_hull(ps.clone(), Hull::Upper, eps);
51    ret.pop();
52    let mut lower = half_hull(ps, Hull::Lower, eps);
53    lower.pop();
54    ret.extend(lower);
55    ret
56}
haar_lib/geom/convex_hull.rs

haar_lib/geom/
convex_hull.rs
