Farthest Points
Code
/// Returns the two farthest points from `p`, or `None` if `p` is empty.
fn farthest_points(p: &[P]) -> Option<[P; 2]> {
let dist = |a: P, b: P| dot(sub(a, b), sub(a, b));
let cvh = convex_hull::<false>(p);
if cvh.len() == 1 {
return Some([cvh[0], cvh[0]]);
} else if cvh.len() == 2 {
return Some([cvh[0], cvh[1]]);
}
fn line_iterator(poly: &[P]) -> impl Iterator<Item = [P; 2]> + '_ {
let mut it = poly.iter().copied().cycle().peekable();
iter::from_fn(move || {
let u = it.next().unwrap();
let v = *it.peek().unwrap();
Some([u, v])
})
}
let mut r = line_iterator(&cvh).skip(1).peekable();
let mut rec = None;
for [la, lb] in line_iterator(&cvh).take(cvh.len()) {
let lv = sub(lb, la);
while {
let &[ra, rb] = r.peek().unwrap();
cross(lv, sub(rb, ra)) > 0
} {
r.next();
}
let &[ra, _] = r.peek().unwrap();
let ch = [la, ra];
let d = dist(ch[0], ch[1]);
if rec.map_or(true, |(x, _)| x < d) {
rec = Some((d, ch));
}
}
rec.map(|x| x.1)
}
Last modified on 231225.