# Divide-and-conquer approach for finding the closest pair of points

This is an algorithm for finding the closest pair of points on a 2d plane by dividing the problem by half recursively, as illustrated here:

use point::Point;

type PairDistance = (Point, Point, f64);

// Divide and conquer approach for finding the closest pair of points
// See http://i.imgur.com/bm0vid8.png
pub fn closest_pair(points: &mut Vec<Point>) -> PairDistance {
fn helper(points: &[Point]) -> PairDistance {
assert!(points.len() >= 2);
match points.len() {
2 => (points[0], points[1], points[0].distance(&points[1])),
3 => {
let p0 = points[0];
let p1 = points[1];
let p2 = points[2];
let d01 = p0.distance(&p1);
let d02 = p0.distance(&p2);
let d12 = p1.distance(&p2);
let mut v: Vec<PairDistance> = vec![(p0, p1, d01), (p0, p2, d02), (p1, p2, d12)];
v.sort_by(|a, b| a.2.partial_cmp(&b.2).unwrap());
v[0]
}
_ => {
let mid = points.len() / 2;
let mid_point = points[mid];
let mid_x = mid_point.x.to_f64();
let pair1 = helper(&points[0..mid]);
let pair2 = helper(&points[mid..points.len()]);
// which is closer, pair1 or pair2?
let mut v_pair12: Vec<PairDistance> = vec![pair1, pair2];
v_pair12.sort_by(|a, b| a.2.partial_cmp(&b.2).unwrap());
let min_pair12 = v_pair12[0];
let min_d_pair12 = min_pair12.2;
// filter out all points that are not in the ±d strip
let points_in_strip: Vec<_> = points.iter()
.cloned()
.filter(|p| (p.x.to_f64() - mid_x).abs() < min_d_pair12)
.collect();
if points_in_strip.len() >= 2 {
let pair_in_strip = helper(points_in_strip.as_slice());
if pair_in_strip.2 < min_d_pair12 {
pair_in_strip
} else {
min_pair12
}
} else {
min_pair12
}
}
}
}

points.sort();
let res = helper(points.as_slice());
res
}

#[test]
fn test_closest_pair() {
let mut v = vec![
Point::new(-3.0, -1.0),
Point::new(-2.0, 0.0),
Point::new(0.0, 0.0),
Point::new(1.0, 1.0),
Point::new(3.0, 1.0),
Point::new(3.0, 2.0),
];
let p = closest_pair(&mut v);
let p_should_be = (
Point::new(3.0, 1.0),
Point::new(3.0, 2.0),
1.0
);
assert_eq!(p, p_should_be);
}


Point can be found in my previous post.

All suggestions are welcome.

• Your code doesn't compile - reproduction. – Shepmaster Sep 21 '16 at 14:15
• You need a --features verbose flag. – qed Sep 21 '16 at 14:21
• I'm not sure how that would fix error: attributes on non-item statements and expressions are experimental. (see issue #15701) - the syntax itself is invalid. – Shepmaster Sep 21 '16 at 14:28
• Maybe I should just remove those lines. – qed Sep 21 '16 at 14:42
• For those who are interested in the setup of the "verbose" feature, here is the link to my Cargo.toml: github.com/kindlychung/algorithms_in_a_nutshell/blob/master/… , and to lib.rs github.com/kindlychung/algorithms_in_a_nutshell/blob/master/src/… – qed Sep 21 '16 at 15:25