3
\$\begingroup\$

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:

diagram

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.