use super::Point;
use super::detect::Chain;
const MIN_FRAGMENT: usize = 20;
const MAX_FRAGMENT_RMS: f32 = 1.2;
const MIN_DIRECTION_COS: f32 = 0.992_546_2;
const MAX_OFFSET: f32 = 1.6;
const MAX_GAP: f32 = 160.0;
const MAX_OVERLAP: f32 = 4.0;
const MIN_SINGLE: usize = 60;
#[derive(Clone, Copy)]
struct Line {
center: Point<f32>,
dir: Point<f32>,
}
impl Line {
fn through<'a>(points: impl Iterator<Item = &'a Point<f32>> + Clone) -> Self {
let n = points.clone().count().max(1) as f32;
let (mut cx, mut cy) = (0f32, 0f32);
for p in points.clone() {
cx += p.x;
cy += p.y;
}
(cx, cy) = (cx / n, cy / n);
let (mut sxx, mut sxy, mut syy) = (0f32, 0f32, 0f32);
for p in points {
let (dx, dy) = (p.x - cx, p.y - cy);
sxx += dx * dx;
sxy += dx * dy;
syy += dy * dy;
}
let angle = 0.5 * (2.0 * sxy).atan2(sxx - syy);
Line {
center: Point::new(cx, cy),
dir: Point::new(angle.cos(), angle.sin()),
}
}
#[inline]
fn along(&self, p: Point<f32>) -> f32 {
(p.x - self.center.x) * self.dir.x + (p.y - self.center.y) * self.dir.y
}
#[inline]
fn across(&self, p: Point<f32>) -> f32 {
(p.y - self.center.y) * self.dir.x - (p.x - self.center.x) * self.dir.y
}
}
struct Fragment {
index: usize,
line: Line,
}
fn straight_fragment(index: usize, chain: &Chain) -> Option<Fragment> {
if chain.points.len() < MIN_FRAGMENT {
return None;
}
let line = Line::through(chain.points.iter());
let sum: f32 = chain.points.iter().map(|&p| line.across(p).powi(2)).sum();
((sum / chain.points.len() as f32).sqrt() <= MAX_FRAGMENT_RMS)
.then_some(Fragment { index, line })
}
fn placement(line: &Line, chain: &Chain) -> (f32, f32, f32) {
let points = &chain.points;
let probes = [
points[0],
points[points.len() / 2],
points[points.len() - 1],
];
let offset = probes
.iter()
.map(|&p| line.across(p).abs())
.fold(0.0, f32::max);
let (a, b) = (line.along(probes[0]), line.along(probes[2]));
(a.min(b), a.max(b), offset)
}
fn join(chains: &[Chain], members: &[usize]) -> Chain {
let line = Line::through(members.iter().flat_map(|&m| chains[m].points.iter()));
let mut order = members.to_vec();
order.sort_by(|&a, &b| {
let mid = |m: usize| line.along(chains[m].points[chains[m].points.len() / 2]);
mid(a).total_cmp(&mid(b))
});
let mut points: Vec<Point<f32>> = Vec::new();
let (mut scale, mut weight) = (0f32, 0f32);
for &m in &order {
let chain = &chains[m];
let forward =
line.along(chain.points[chain.points.len() - 1]) >= line.along(chain.points[0]);
let first = if forward {
chain.points[0]
} else {
chain.points[chain.points.len() - 1]
};
if let Some(&last) = points.last() {
let gap = (first.x - last.x).hypot(first.y - last.y) as usize;
for k in 1..gap {
let t = k as f32 / gap as f32;
points.push(Point::new(
last.x + t * (first.x - last.x),
last.y + t * (first.y - last.y),
));
}
}
if forward {
points.extend_from_slice(&chain.points);
} else {
points.extend(chain.points.iter().rev());
}
scale += chain.scale * chain.points.len() as f32;
weight += chain.points.len() as f32;
}
Chain {
points,
scale: scale / weight.max(1.0),
}
}
pub(super) fn find_long_lines(chains: &[Chain]) -> Vec<Chain> {
let mut fragments: Vec<Fragment> = chains
.iter()
.enumerate()
.filter_map(|(i, c)| straight_fragment(i, c))
.collect();
fragments.sort_by_key(|f| std::cmp::Reverse(chains[f.index].points.len()));
let mut used = vec![false; chains.len()];
let mut lines = Vec::new();
for seed in 0..fragments.len() {
let seed_index = fragments[seed].index;
if used[seed_index] {
continue;
}
let mut members = vec![seed_index];
loop {
let line = Line::through(members.iter().flat_map(|&m| chains[m].points.iter()));
let (mut lo, mut hi) = (f32::INFINITY, f32::NEG_INFINITY);
for &m in &members {
let (a, b, _) = placement(&line, &chains[m]);
(lo, hi) = (lo.min(a), hi.max(b));
}
let mut nearest: Option<(f32, usize)> = None;
for fragment in &fragments {
let j = fragment.index;
if used[j] || members.contains(&j) {
continue;
}
let cos = line.dir.x * fragment.line.dir.x + line.dir.y * fragment.line.dir.y;
if cos.abs() < MIN_DIRECTION_COS {
continue;
}
let (a, b, offset) = placement(&line, &chains[j]);
let gap = (a - hi).max(lo - b);
if offset <= MAX_OFFSET
&& (-MAX_OVERLAP..=MAX_GAP).contains(&gap)
&& nearest.is_none_or(|(g, _)| gap < g)
{
nearest = Some((gap, j));
}
}
match nearest {
Some((_, j)) => members.push(j),
None => break,
}
}
if members.len() >= 2 {
members.iter().for_each(|&m| used[m] = true);
lines.push(join(chains, &members));
} else if chains[seed_index].points.len() >= MIN_SINGLE {
used[seed_index] = true;
lines.push(Chain {
points: chains[seed_index].points.clone(),
scale: chains[seed_index].scale,
});
}
}
lines
}
#[cfg(test)]
mod tests {
use super::*;
fn segment(x0: f32, x1: f32, y: f32, slope: f32) -> Chain {
let n = (x1 - x0).abs() as usize;
let step = if x1 >= x0 { 1.0 } else { -1.0 };
let points = (0..=n)
.map(|k| {
let x = x0 + step * k as f32;
Point::new(x, y + slope * x)
})
.collect();
Chain { points, scale: 1.0 }
}
#[test]
fn collinear_fragments_join_across_gaps_in_either_direction() {
let chains = [
segment(10.0, 50.0, 20.0, 0.1),
segment(200.0, 150.0, 20.0, 0.1),
segment(80.0, 110.0, 20.0, 0.1),
];
let lines = find_long_lines(&chains);
assert_eq!(lines.len(), 1);
let points = &lines[0].points;
assert!(
(points[0].x - 10.0).abs() < 1e-3 && (points[points.len() - 1].x - 200.0).abs() < 1e-3
);
for pair in points.windows(2) {
assert!(
pair[1].x > pair[0].x,
"points must run monotonically along the line"
);
assert!(
(pair[1].x - pair[0].x) <= 1.5,
"gaps must be bridged at about 1 px"
);
}
}
#[test]
fn parallel_and_tilted_neighbours_stay_apart() {
let chains = [
segment(10.0, 60.0, 20.0, 0.0),
segment(80.0, 130.0, 24.0, 0.0),
segment(80.0, 130.0, 0.0, 0.3),
];
assert!(find_long_lines(&chains).is_empty());
}
#[test]
fn a_long_straight_chain_is_a_line_on_its_own_and_a_short_one_is_not() {
let lines = find_long_lines(&[
segment(10.0, 100.0, 30.0, -0.2),
segment(10.0, 45.0, 90.0, 0.0),
]);
assert_eq!(lines.len(), 1);
assert_eq!(lines[0].points.len(), 91);
}
#[test]
fn distant_fragments_are_not_joined() {
let chains = [
segment(10.0, 40.0, 20.0, 0.0),
segment(260.0, 300.0, 20.0, 0.0),
];
assert!(find_long_lines(&chains).is_empty());
}
}