haar_lib/geom/
closest_pair.rs

1//! 最近点対
2
3use crate::{algo::merge::*, geom::*};
4
5/// 最近点対を求める。
6pub fn closest_pair(mut ps: Vec<Vector>, eps: Eps) -> Option<(Vector, Vector)> {
7    if ps.len() < 2 {
8        None
9    } else {
10        ps.sort_by(|p, q| p.0.partial_cmp(&q.0).unwrap());
11        rec(&mut ps, eps)
12    }
13}
14
15fn rec(ps: &mut [Vector], eps: Eps) -> Option<(Vector, Vector)> {
16    let n = ps.len();
17    match n {
18        0 => unreachable!(),
19        1 => None,
20        2 => {
21            if eps.gt(ps[0].1, ps[1].1) {
22                ps.swap(0, 1);
23            }
24            Some((ps[0], ps[1]))
25        }
26        _ => {
27            let mid_x = ps[n / 2].0;
28            let (left, right) = ps.split_at_mut(n / 2);
29            let d1 = rec(left, eps);
30            let d2 = rec(right, eps);
31
32            inplace_merge_by(ps, n / 2, |a, b| a.1 < b.1);
33
34            let mut d = f64::INFINITY;
35            let mut ret = None;
36
37            if let Some((p, q)) = d1 {
38                let t = (p - q).abs();
39                if eps.lt(t, d) {
40                    d = t;
41                    ret = Some((p, q));
42                }
43            }
44            if let Some((p, q)) = d2 {
45                let t = (p - q).abs();
46                if eps.lt(t, d) {
47                    d = t;
48                    ret = Some((p, q));
49                }
50            }
51
52            let mut v: Vec<Vector> = vec![];
53
54            for &mut p in ps {
55                if eps.gt((p.0 - mid_x).abs(), d) {
56                    continue;
57                }
58
59                for &q in v.iter().rev() {
60                    if eps.gt((p.1 - q.1).abs(), d) {
61                        break;
62                    }
63
64                    let t = (p - q).abs();
65                    if eps.lt(t, d) {
66                        d = t;
67                        ret = Some((p, q));
68                    }
69                }
70
71                v.push(p);
72            }
73
74            ret
75        }
76    }
77}
haar_lib/geom/closest_pair.rs

haar_lib/geom/
closest_pair.rs
