Anonymous user
Closest-pair problem: Difference between revisions
Add Rust implementation
m (→{{header|REXX}}: optimized the inner DO loop.) |
(Add Rust implementation) |
||
Line 4,383:
data 0.293786, 0.691701
data 0.839186, 0.72826</lang>
=={{header|Rust}}==
<lang rust>
//! We interpret complex numbers as points in the Cartesian plane, here. We also use the
//! [sweepline/plane sweep closest pairs algorithm][algorithm] instead of the divide-and-conquer
//! algorithm, since it's (arguably) easier to implement, and an efficient implementation does not
//! require use of unsafe.
//!
//! [algorithm]: http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPairPS.html
extern crate num;
use num::complex::Complex;
use std::cmp::{Ordering, PartialOrd};
use std::collections::BTreeSet;
type Point = Complex<f32>;
/// Wrapper around `Point` (i.e. `Complex<f32>`) so that we can use a `TreeSet`
#[derive(PartialEq)]
struct YSortedPoint {
point: Point,
}
impl PartialOrd for YSortedPoint {
fn partial_cmp(&self, other: &YSortedPoint) -> Option<Ordering> {
(self.point.im, self.point.re).partial_cmp(&(other.point.im, other.point.re))
}
}
impl Ord for YSortedPoint {
fn cmp(&self, other: &YSortedPoint) -> Ordering {
self.partial_cmp(other).unwrap()
}
}
impl Eq for YSortedPoint {}
fn closest_pair(points: &mut [Point]) -> Option<(Point, Point)> {
if points.len() < 2 {
return None;
}
points.sort_by(|a, b| (a.re, a.im).partial_cmp(&(b.re, b.im)).unwrap());
let mut closest_pair = (points[0], points[1]);
let mut closest_distance_sqr = (points[0] - points[1]).norm_sqr();
let mut closest_distance = closest_distance_sqr.sqrt();
// the strip that we inspect for closest pairs as we sweep right
let mut strip: BTreeSet<YSortedPoint> = BTreeSet::new();
strip.insert(YSortedPoint { point: points[0] });
strip.insert(YSortedPoint { point: points[1] });
// index of the leftmost point on the strip (on points)
let mut leftmost_idx = 0;
// Start the sweep!
for (idx, point) in points.iter().enumerate().skip(2) {
// Remove all points farther than `closest_distance` away from `point`
// along the x-axis
while leftmost_idx < idx {
let leftmost_point = &points[leftmost_idx];
if (leftmost_point.re - point.re).powi(2) < closest_distance_sqr {
break;
}
strip.remove(&YSortedPoint {
point: *leftmost_point,
});
leftmost_idx += 1;
}
// Compare to points in bounding box
{
let low_bound = YSortedPoint {
point: Point {
re: ::std::f32::INFINITY,
im: point.im - closest_distance,
},
};
let mut strip_iter = strip.iter().skip_while(|&p| p < &low_bound);
loop {
let point2 = match strip_iter.next() {
None => break,
Some(p) => p.point,
};
if point2.im - point.im >= closest_distance {
// we've reached the end of the box
break;
}
let dist_sqr = (*point - point2).norm_sqr();
if dist_sqr < closest_distance_sqr {
closest_pair = (point2, *point);
closest_distance_sqr = dist_sqr;
closest_distance = dist_sqr.sqrt();
}
}
}
// Insert point into strip
strip.insert(YSortedPoint { point: *point });
}
Some(closest_pair)
}
pub fn main() {
let mut test_data = [
Complex::new(0.654682, 0.925557),
Complex::new(0.409382, 0.619391),
Complex::new(0.891663, 0.888594),
Complex::new(0.716629, 0.996200),
Complex::new(0.477721, 0.946355),
Complex::new(0.925092, 0.818220),
Complex::new(0.624291, 0.142924),
Complex::new(0.211332, 0.221507),
Complex::new(0.293786, 0.691701),
Complex::new(0.839186, 0.728260),
];
let (p1, p2) = closest_pair(&mut test_data[..]).unwrap();
println!("Closest pair: {} and {}", p1, p2);
println!("Distance: {}", (p1 - p2).norm_sqr().sqrt());
}
</lang>
{{out}}
<pre>
Closest pair: 0.891663+0.888594i and 0.925092+0.81822i
Distance: 0.07791013
</pre>
=={{header|Scala}}==
| |||