2bc41aeb8602
tests.rs
use std::collections::HashMap;
use kurbo::{Point, Vec2};
use vectorcraft_geom::{Anchor, AnchorKind, EPS, SubPath};
use super::{
End, Rejoined, chains, close_nearly_closed, merge_duplicate_anchors, near_point_groups, outward, rejoin, remove_collinear_anchors,
retract_tiny_handles, root,
};
fn line(pts: &[(f64, f64)], closed: bool) -> SubPath {
SubPath::polyline(&pts.iter().map(|&p| p.into()).collect::<Vec<Point>>(), closed)
}
fn points(sp: &SubPath) -> Vec<(f64, f64)> {
sp.anchors.iter().map(|a| (a.p.x, a.p.y)).collect()
}
#[test]
fn collinear_anchors_go_and_corners_stay() {
let mut sp = line(&[(0.0, 0.0), (5.0, 0.0), (10.0, 0.0), (10.0, 10.0), (0.0, 10.0), (0.0, 5.0)], true);
assert_eq!(remove_collinear_anchors(&mut sp, 0.005), 2);
assert_eq!(points(&sp), [(0.0, 0.0), (10.0, 0.0), (10.0, 10.0), (0.0, 10.0)]);
assert_eq!(remove_collinear_anchors(&mut sp, 0.005), 0, "clean art is left alone");
// A turn back on itself is not a straight run; an open end stays.
let mut back = line(&[(0.0, 0.0), (10.0, 0.0), (5.0, 0.0)], false);
assert_eq!(remove_collinear_anchors(&mut back, 0.005), 0);
// An anchor with a handle is not a corner on a straight run.
let mut curved = line(&[(0.0, 0.0), (5.0, 0.0), (10.0, 0.0)], false);
curved.anchors[1] = Anchor::smooth((5.0, 0.0).into(), (7.0, 0.0).into());
assert_eq!(remove_collinear_anchors(&mut curved, 0.005), 0);
// A slight bend within the tolerance goes; a larger one stays.
let mut bend = line(&[(0.0, 0.0), (100.0, 0.1), (200.0, 0.0)], false);
assert_eq!(remove_collinear_anchors(&mut bend.clone(), 0.0001), 0);
assert_eq!(remove_collinear_anchors(&mut bend, 0.005), 1);
}
/// The collinear-anchor removal done one `Vec::remove` at a time, testing the anchor that moves
/// into the gap next: the result [`remove_collinear_anchors`] gives.
fn one_at_a_time(sp: &mut SubPath, tolerance: f64) -> usize {
let min = if sp.closed { 3 } else { 2 };
let mut removed = 0;
let mut i = 0;
while i < sp.anchors.len() && sp.anchors.len() > min {
let n = sp.anchors.len();
let inner = sp.closed || (i > 0 && i + 1 < n);
let (prev, cur, next) = (sp.anchors[(i + n - 1) % n], sp.anchors[i], sp.anchors[(i + 1) % n]);
let straight = !prev.has_out() && !cur.has_in() && !cur.has_out() && !next.has_in();
let (a, b) = (cur.p - prev.p, next.p - cur.p);
let len = a.hypot() * b.hypot();
if inner && straight && len > EPS && a.dot(b) > 0.0 && a.cross(b).abs() / len <= tolerance {
sp.anchors.remove(i);
removed += 1;
} else {
i += 1;
}
}
removed
}
/// A subpath's closed flag and every anchor's coordinates bit for bit, with its kind.
fn bits(sp: &SubPath) -> (bool, Vec<([u64; 6], AnchorKind)>) {
let anchors = sp.anchors.iter().map(|a| ([a.p.x, a.p.y, a.h_in.x, a.h_in.y, a.h_out.x, a.h_out.y].map(f64::to_bits), a.kind));
(sp.closed, anchors.collect())
}
/// Check that [`remove_collinear_anchors`] gives `sp` the count and anchors [`one_at_a_time`] does.
fn same_as_one_at_a_time(sp: &SubPath, tolerance: f64) {
let (mut fast, mut slow) = (sp.clone(), sp.clone());
let got = remove_collinear_anchors(&mut fast, tolerance);
let want = one_at_a_time(&mut slow, tolerance);
assert_eq!(got, want, "count at tolerance {tolerance} for {sp:?}");
assert_eq!(bits(&fast), bits(&slow), "anchors at tolerance {tolerance} for {sp:?}");
}
/// xorshift64: the same numbers on every run.
struct Rng(u64);
impl Rng {
fn next(&mut self) -> u64 {
self.0 ^= self.0 << 13;
self.0 ^= self.0 >> 7;
self.0 ^= self.0 << 17;
self.0
}
fn pick<T: Copy>(&mut self, xs: &[T]) -> T {
xs[(self.next() % xs.len() as u64) as usize]
}
}
/// A subpath of `n` anchors stepping mostly straight along one direction, with repeated points,
/// small and large bends, reversals, short and long handles and non-finite or huge coordinates.
fn generated(r: &mut Rng, n: usize, closed: bool) -> SubPath {
let dir = r.pick(&[Vec2::new(1.0, 0.0), Vec2::new(0.0, -1.0), Vec2::new(0.6, 0.8), Vec2::new(-1.0, 1.0)]);
let side = Vec2::new(-dir.y, dir.x);
let mut at = Point::new(r.pick(&[0.0, 3.0, -7.5]), r.pick(&[0.0, 2.0]));
let anchors = (0..n)
.map(|_| {
at += dir * r.pick(&[1.0, 1.0, 1.0, 2.0, 0.5, 0.0, -1.0]);
let bend = r.pick(&[0.0, 0.0, 0.0, 0.0, 1e-3, 0.004, 0.005, 0.006, 1.0]);
let mut p = at + side * bend;
match r.next() % 40 {
0 => p.x = f64::NAN,
1 => p.y = f64::INFINITY,
2 => p.x = f64::NEG_INFINITY,
3 => p = Point::new(p.x * 1e300, p.y * 1e300),
4 => p = Point::new(1e-300, -1e-300),
_ => {}
}
let handle = |r: &mut Rng| p + Vec2::new(r.pick(&[0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1e-10, 1.0]), 0.0);
let (h_in, h_out) = (handle(r), handle(r));
Anchor { p, h_in, h_out, kind: r.pick(&[AnchorKind::Corner, AnchorKind::Corner, AnchorKind::Smooth]) }
})
.collect();
SubPath::new(anchors, closed)
}
const TOLERANCES: [f64; 12] = [-1.0, -0.0, 0.0, 1e-9, 0.001, 0.005, 0.5, 1.0, 2.0, f64::NAN, f64::INFINITY, f64::NEG_INFINITY];
#[test]
fn collinear_anchors_go_as_when_removed_one_at_a_time() {
let mut r = Rng(0x9e37_79b9_7f4a_7c15);
for n in (0..40).chain([64, 100, 257]) {
for _ in 0..40 {
for closed in [false, true] {
let sp = generated(&mut r, n, closed);
for tolerance in TOLERANCES {
same_as_one_at_a_time(&sp, tolerance);
}
}
}
}
}
#[test]
fn collinear_anchors_keep_their_neighbors_order_and_ends() {
let ring = |pts: &[(f64, f64)]| line(pts, true);
let cases = [
// A closed run whose first anchor goes: the last anchor's next neighbor is then the second.
ring(&[(5.0, 0.0), (10.0, 0.0), (10.0, 10.0), (0.0, 10.0), (0.0, 0.0)]),
ring(&[(0.0, 0.0), (1.0, 0.0), (2.0, 0.0), (3.0, 0.0), (4.0, 0.0), (5.0, 0.0), (2.0, 4.0)]),
// Every anchor on one line: the path stops at three (closed) or two (open) anchors.
ring(&[(0.0, 0.0), (1.0, 0.0), (2.0, 0.0), (3.0, 0.0), (4.0, 0.0)]),
line(&[(0.0, 0.0), (1.0, 0.0), (2.0, 0.0), (3.0, 0.0), (4.0, 0.0)], false),
// The last anchor lies between the first one kept and the one before it.
ring(&[(0.0, 0.0), (10.0, 0.0), (10.0, 10.0), (0.0, 10.0), (0.0, 5.0)]),
// Repeated and zero-length points.
line(&[(0.0, 0.0), (0.0, 0.0), (1.0, 0.0), (1.0, 0.0), (2.0, 0.0)], false),
ring(&[(0.0, 0.0), (0.0, 0.0), (0.0, 0.0), (0.0, 0.0)]),
// Products of huge coordinates overflow; tiny ones underflow.
line(&[(0.0, 0.0), (1e200, 1e200), (2e200, 2e200), (f64::MAX, f64::MAX)], false),
line(&[(0.0, 0.0), (1e-200, 0.0), (2e-200, 0.0)], false),
line(&[(0.0, 0.0), (f64::NAN, 0.0), (2.0, 0.0), (f64::INFINITY, 0.0), (5.0, 0.0)], false),
];
for sp in &cases {
for tolerance in TOLERANCES {
same_as_one_at_a_time(sp, tolerance);
}
}
let mut first = cases[0].clone();
assert_eq!(remove_collinear_anchors(&mut first, 0.0), 1);
assert_eq!(points(&first), [(10.0, 0.0), (10.0, 10.0), (0.0, 10.0), (0.0, 0.0)]);
let (mut closed, mut open) = (cases[2].clone(), cases[3].clone());
assert_eq!((remove_collinear_anchors(&mut closed, 0.0), closed.anchors.len()), (2, 3));
assert_eq!(remove_collinear_anchors(&mut open, 0.0), 3);
assert_eq!(points(&open), [(0.0, 0.0), (4.0, 0.0)], "open ends stay");
// A handle on either side of either segment keeps the anchor between them.
for side in 0..4 {
let mut sp = line(&[(0.0, 0.0), (1.0, 0.0), (2.0, 0.0)], false);
let (i, h) = [(0, 1), (1, 0), (1, 1), (2, 0)][side];
for kind in [AnchorKind::Corner, AnchorKind::Smooth] {
let a = &mut sp.anchors[i];
a.kind = kind;
*(if h == 0 { &mut a.h_in } else { &mut a.h_out }) = a.p + Vec2::new(0.0, 1.0);
same_as_one_at_a_time(&sp, 0.005);
assert_eq!(remove_collinear_anchors(&mut sp.clone(), 0.005), 0, "handle {h} on anchor {i}");
}
}
}
#[test]
fn collinear_anchors_at_the_tolerance_go_and_just_past_it_stay() {
let sp = line(&[(0.0, 0.0), (100.0, 0.1), (200.0, 0.0)], false);
let (a, b) = (sp.anchors[1].p - sp.anchors[0].p, sp.anchors[2].p - sp.anchors[1].p);
let sine = a.cross(b).abs() / (a.hypot() * b.hypot());
for (tolerance, removed) in [(sine, 1), (sine.next_down(), 0), (sine.next_up(), 1)] {
same_as_one_at_a_time(&sp, tolerance);
assert_eq!(remove_collinear_anchors(&mut sp.clone(), tolerance), removed, "{tolerance}");
}
}
#[test]
fn collinear_anchors_go_in_linear_work() {
for (n, closed) in [(10_000, false), (20_000, false), (20_000, true)] {
let pts: Vec<Point> = (0..n).map(|i| Point::new(i as f64, 0.0)).collect();
let mut sp = SubPath::polyline(&pts, closed);
let removed = remove_collinear_anchors(&mut sp, 0.005);
// A closed straight run stops at three anchors; an open one keeps its two ends.
assert_eq!((removed, sp.anchors.len()), if closed { (n - 3, 3) } else { (n - 2, 2) });
let work = super::COLLINEAR_WORK.with(std::cell::Cell::get);
assert!(work <= 2 * n, "{n} anchors took {work} steps");
}
}
#[test]
fn duplicate_anchors_merge_keeping_the_outer_handles() {
let mut sp = SubPath::new(
vec![
Anchor::with_handles((0.0, 0.0).into(), (0.0, 0.0).into(), (0.0, 0.0).into()),
Anchor::with_handles((10.0, 0.0).into(), (8.0, 0.0).into(), (10.0, 0.0).into()),
Anchor::with_handles((10.005, 0.0).into(), (10.005, 0.0).into(), (10.005, 3.0).into()),
Anchor::corner((10.0, 10.0).into()),
],
false,
);
assert_eq!(merge_duplicate_anchors(&mut sp, 0.01), 1);
assert_eq!(sp.anchors.len(), 3);
let a = sp.anchors[1];
assert_eq!((a.p, a.h_in), (Point::new(10.0, 0.0), Point::new(8.0, 0.0)));
assert!(a.h_out.distance(Point::new(10.0, 3.0)) < 1e-9, "{:?}", a.h_out);
assert_eq!(merge_duplicate_anchors(&mut sp, 0.01), 0);
// A closed path's last anchor on its first merges into it.
let mut ring = line(&[(0.0, 0.0), (10.0, 0.0), (10.0, 10.0), (0.0, 0.0)], true);
assert_eq!(merge_duplicate_anchors(&mut ring, 0.01), 1);
assert_eq!(points(&ring), [(0.0, 0.0), (10.0, 0.0), (10.0, 10.0)]);
}
#[test]
fn tiny_handles_retract() {
let p = Point::new(5.0, 5.0);
let mut sp = SubPath::new(vec![Anchor { p, h_in: p - Vec2::new(0.004, 0.0), h_out: p + Vec2::new(3.0, 0.0), kind: AnchorKind::Smooth }], false);
assert_eq!(retract_tiny_handles(&mut sp, 0.01), 1);
let a = sp.anchors[0];
assert_eq!((a.h_in, a.kind), (p, AnchorKind::Corner));
assert_eq!(a.h_out, p + Vec2::new(3.0, 0.0), "a long handle stays");
assert_eq!(retract_tiny_handles(&mut sp, 0.01), 0);
}
#[test]
fn nearly_closed_paths_close() {
let mut sp = line(&[(0.0, 0.0), (10.0, 0.0), (10.0, 10.0), (0.005, 0.0)], false);
assert!(close_nearly_closed(&mut sp, 0.01));
assert!(sp.closed);
assert_eq!(points(&sp), [(0.0, 0.0), (10.0, 0.0), (10.0, 10.0)]);
let mut apart = line(&[(0.0, 0.0), (10.0, 0.0), (10.0, 10.0), (1.0, 0.0)], false);
assert!(!close_nearly_closed(&mut apart, 0.01));
assert!(!apart.closed);
let mut two = line(&[(0.0, 0.0), (0.0, 0.0)], false);
assert!(!close_nearly_closed(&mut two, 0.01), "two anchors make no shape");
}
#[test]
fn near_points_group_but_linked_and_equal_ones_do_not() {
let pts: Vec<Point> = [(0.0, 0.0), (0.005, 0.0), (5.0, 5.0), (5.0, 5.0), (9.0, 9.0), (9.004, 9.0), (f64::NAN, 0.0)].map(Into::into).to_vec();
let groups = near_point_groups(&pts, 0.01, |a, b| (a, b) == (4, 5));
assert_eq!(groups, [vec![0, 1]], "equal points and linked ones are not snapped");
assert!(near_point_groups(&pts, 0.0, |_, _| false).is_empty());
assert!(near_point_groups(&pts, f64::NAN, |_, _| false).is_empty());
// Far coordinates don't overflow the grid.
let far: Vec<Point> = [(1e300, 1e300), (-1e300, 1e300)].map(Into::into).to_vec();
assert!(near_point_groups(&far, 1e-300, |_, _| false).is_empty());
}
/// Nearly Coincident Anchors' grouping comparing every pair of points in touching grid cells: the
/// groups [`near_point_groups`] gives.
fn near_groups_pair_by_pair(points: &[Point], distance: f64, linked: impl Fn(usize, usize) -> bool) -> Vec<Vec<usize>> {
if !(distance > 0.0 && distance.is_finite()) {
return vec![];
}
let cell = |p: Point| ((p.x / distance).floor() as i64, (p.y / distance).floor() as i64);
let mut grid: HashMap<(i64, i64), Vec<usize>> = HashMap::new();
for (i, p) in points.iter().enumerate().filter(|(_, p)| p.is_finite()) {
grid.entry(cell(*p)).or_default().push(i);
}
let mut parent: Vec<usize> = (0..points.len()).collect();
for (&(cx, cy), members) in &grid {
for (dx, dy) in [(0, 0), (1, 0), (-1, 1), (0, 1), (1, 1)] {
let Some(others) = grid.get(&(cx.saturating_add(dx), cy.saturating_add(dy))) else { continue };
for &i in members {
for &j in others.iter().filter(|&&j| (dx, dy) != (0, 0) || j > i) {
let d = points[i].distance(points[j]);
if d <= distance && d > 0.0 && !linked(i.min(j), i.max(j)) {
let (ri, rj) = (root(&mut parent, i), root(&mut parent, j));
parent[ri.max(rj)] = ri.min(rj);
}
}
}
}
}
let mut groups: HashMap<usize, Vec<usize>> = HashMap::new();
for i in 0..points.len() {
groups.entry(root(&mut parent, i)).or_default().push(i);
}
let mut out: Vec<Vec<usize>> = groups.into_values().filter(|g| g.len() > 1).collect();
out.sort_unstable();
out
}
/// Points around a few spots on a lattice, many at the same place, with signed zeros, huge, tiny
/// and non-finite coordinates.
fn generated_points(r: &mut Rng, n: usize, distance: f64) -> Vec<Point> {
let spots: Vec<Point> = (0..1 + r.next() % 6).map(|_| Point::new((r.next() % 5) as f64 * distance, (r.next() % 5) as f64 * distance)).collect();
(0..n)
.map(|_| {
let jitter = |r: &mut Rng| r.pick(&[0.0, 0.0, -0.0, 0.1, 0.3, 0.5, 0.7, 0.99, 1.0, 1.01, 2.0, -0.5, -1.0]) * distance;
let at = r.pick(&spots);
let p = Point::new(at.x + jitter(r), at.y + jitter(r));
match r.next() % 50 {
0 => Point::new(f64::NAN, p.y),
1 => Point::new(p.x, f64::INFINITY),
2 => Point::new(-0.0, -0.0),
3 => Point::new(p.x * 1e300, p.y),
4 => Point::new(1e-300, 1e-300),
_ => p,
}
})
.collect()
}
#[test]
fn near_points_group_as_when_every_pair_is_compared() {
let mut r = Rng(0x2545_f491_4f6c_dd1d);
let linked: [fn(usize, usize) -> bool; 5] =
[|_, _| false, |a, b| b == a + 1, |a, b| (a * 31 + b * 17) % 5 == 0, |a, b| (a + b) % 2 == 0, |_, _| true];
for n in (0..30).chain([64, 150, 300]) {
for _ in 0..12 {
for distance in [0.01, 0.5, 1.0, 3.0, 1e-200, 1e300] {
let pts = generated_points(&mut r, n, distance);
for (k, linked) in linked.iter().enumerate() {
let want = near_groups_pair_by_pair(&pts, distance, linked);
assert_eq!(near_point_groups(&pts, distance, linked), want, "linked {k} at {distance} for {pts:?}");
}
}
}
}
}
/// A tight cluster of `n` points around `at`, no two at the same place.
fn cluster(at: Point, radius: f64, n: usize) -> Vec<Point> {
(0..n).map(|i| at + Vec2::from_angle(i as f64 * 2.399_963) * (radius * ((i + 1) as f64 / n as f64).sqrt())).collect()
}
#[test]
fn near_points_in_a_dense_cell_group_in_linear_work() {
let n = 4_000;
let neighbours = |a: usize, b: usize| b == a + 1;
let one_cluster = cluster(Point::new(0.005, 0.005), 0.004, n);
let mut two_clusters = cluster(Point::new(0.001, 0.001), 0.0009, n / 2);
two_clusters.extend(cluster(Point::new(0.019, 0.019), 0.0009, n / 2));
let same_place = vec![Point::new(0.005, 0.005); n];
let cases = [(&one_cluster, 1, n), (&two_clusters, 2, n / 2), (&same_place, 0, 0)];
for (pts, count, size) in cases {
let groups = near_point_groups(pts, 0.01, neighbours);
let work = super::NEAR_WORK.with(std::cell::Cell::get);
assert_eq!(groups, near_groups_pair_by_pair(pts, 0.01, neighbours));
assert_eq!(groups.len(), count);
assert!(groups.iter().all(|g| g.len() == size), "{:?}", groups.iter().map(Vec::len).collect::<Vec<_>>());
assert!(work <= 4 * n, "{n} points took {work} steps");
}
}
/// One pair of ends (`a` < `b` in the list of ends) for [`rejoin_sorting_every_pair`]: the turn,
/// the distance, and the two ends.
type Pair = (f64, f64, End, End);
/// Rejoin listing every pair of ends in touching grid cells and sorting them by turn and then
/// distance: the joins [`rejoin`] makes.
fn rejoin_sorting_every_pair(pieces: &[SubPath], gap: f64) -> Vec<Rejoined> {
if !(gap >= 0.0 && gap.is_finite()) {
return vec![];
}
let usable = |sp: &&SubPath| {
!sp.closed && sp.anchors.len() >= 2 && sp.anchors.iter().all(|a| a.p.is_finite() && a.h_in.is_finite() && a.h_out.is_finite())
};
let ends: Vec<(End, Point, Vec2)> = pieces
.iter()
.enumerate()
.filter(|(_, sp)| usable(sp))
.flat_map(|(i, sp)| [(i, sp, false), (i, sp, true)])
.filter_map(|(i, sp, last)| {
let a = if last { sp.anchors.last() } else { sp.anchors.first() }?;
Some(((i, last), a.p, outward(sp, last)?))
})
.collect();
let size = gap.max(1e-9);
let cell = |p: Point| ((p.x / size).floor() as i64, (p.y / size).floor() as i64);
let mut grid: HashMap<(i64, i64), Vec<usize>> = HashMap::new();
for (i, e) in ends.iter().enumerate() {
grid.entry(cell(e.1)).or_default().push(i);
}
let mut pairs: Vec<Pair> = vec![];
for (a, &(ea, pa, oa)) in ends.iter().enumerate() {
let (cx, cy) = cell(pa);
for dx in -1..=1 {
for dy in -1..=1 {
let Some(others) = grid.get(&(cx.saturating_add(dx), cy.saturating_add(dy))) else { continue };
for &b in others.iter().filter(|&&b| b > a) {
let (eb, pb, ob) = ends[b];
if ea.0 == eb.0 && pieces[ea.0].anchors.len() < 3 {
continue;
}
let d = pa.distance(pb);
if d <= gap {
pairs.push((oa.dot(-ob).clamp(-1.0, 1.0).acos(), d, ea, eb));
}
}
}
}
}
pairs.sort_by(|x, y| x.0.total_cmp(&y.0).then(x.1.total_cmp(&y.1)));
let mut link: HashMap<End, End> = HashMap::new();
for (_, _, a, b) in pairs {
if !link.contains_key(&a) && !link.contains_key(&b) {
link.insert(a, b);
link.insert(b, a);
}
}
chains(pieces, &link)
}
/// Check that [`rejoin`] joins `pieces` as [`rejoin_sorting_every_pair`] does, bit for bit.
fn same_as_sorting_every_pair(pieces: &[SubPath], gap: f64) {
let (got, want) = (rejoin(pieces, gap), rejoin_sorting_every_pair(pieces, gap));
let shape = |out: &[Rejoined]| out.iter().map(|j| (j.members.clone(), bits(&j.path))).collect::<Vec<_>>();
assert_eq!(shape(&got), shape(&want), "gap {gap} for {pieces:?}");
}
/// Pieces of two to four anchors whose ends sit on or near a few lattice points, often at the
/// same place, some curving, closed or non-finite.
fn generated_pieces(r: &mut Rng, n: usize, gap: f64) -> Vec<SubPath> {
let spot = |r: &mut Rng| {
let near = r.pick(&[0.0, 0.0, 0.0, 0.25, 0.5, 1.0, 1.5]) * gap;
Point::new((r.next() % 3) as f64 + near, (r.next() % 3) as f64 + r.pick(&[0.0, 0.0, near, -near]))
};
(0..n)
.map(|_| {
let count = 2 + (r.next() % 3) as usize;
let mut pts: Vec<Point> = (0..count).map(|_| spot(r)).collect();
if r.next().is_multiple_of(30) {
pts[0].x = f64::NAN;
}
let mut sp = SubPath::polyline(&pts, r.next().is_multiple_of(15));
if r.next().is_multiple_of(4) {
let a = &mut sp.anchors[0];
a.h_out = a.p + r.pick(&[Vec2::new(0.3, 0.1), Vec2::new(0.0, -0.2), Vec2::new(-0.1, -0.1)]);
}
sp
})
.collect()
}
#[test]
fn rejoin_joins_as_when_every_pair_is_sorted() {
let mut r = Rng(0xd1b5_4a32_d192_ed03);
for n in (0..25).chain([40, 80, 160]) {
for _ in 0..15 {
for gap in [0.0, 0.05, 0.1, 0.5, 1.0, 3.0] {
same_as_sorting_every_pair(&generated_pieces(&mut r, n, gap), gap);
}
}
}
// Ends meeting from directions that tie: a plus sign, a doubled star and stacked copies.
let plus: Vec<SubPath> = [(1.0, 0.0), (0.0, 1.0), (-1.0, 0.0), (0.0, -1.0)].map(|(x, y)| line(&[(0.0, 0.0), (x, y)], false)).to_vec();
let mut doubled = plus.clone();
doubled.extend(plus.iter().map(|sp| {
let mut sp = sp.clone();
sp.reverse();
sp
}));
let stacked = vec![line(&[(0.0, 0.0), (1.0, 0.0), (2.0, 1.0)], false); 7];
for pieces in [&plus, &doubled, &stacked] {
for gap in [0.0, 0.1, 5.0] {
same_as_sorting_every_pair(pieces, gap);
}
}
}
#[test]
fn rejoin_pairs_coincident_ends_in_near_linear_work() {
let n = 2_000;
let ray = |angle: f64| {
let tip = Vec2::from_angle(angle) * 100.0;
line(&[(0.0, 0.0), (tip.x, tip.y)], false)
};
let star: Vec<SubPath> = (0..n).map(|i| ray(i as f64 * std::f64::consts::TAU / n as f64)).collect();
let mut r = Rng(0x9e37_79b9_7f4a_7c15);
let scattered: Vec<SubPath> = (0..n).map(|_| ray((r.next() % 1_000_000) as f64 * 1e-6 * std::f64::consts::TAU)).collect();
let stacked = vec![line(&[(0.0, 0.0), (10.0, 0.0)], false); n];
for (name, pieces) in [("star", &star), ("scattered", &scattered), ("stacked", &stacked)] {
let out = rejoin(pieces, 0.1);
let work = super::REJOIN_WORK.with(std::cell::Cell::get);
let want = rejoin_sorting_every_pair(pieces, 0.1);
assert_eq!(
out.iter().map(|j| (j.members.clone(), bits(&j.path))).collect::<Vec<_>>(),
want.iter().map(|j| (j.members.clone(), bits(&j.path))).collect::<Vec<_>>(),
"{name}"
);
assert!(work <= 20 * n, "{name}: {n} pieces took {work} steps");
}
}
#[test]
fn rejoin_welds_pieces_within_the_gap() {
// Three pieces of one zig-zag, the middle one drawn backwards, plus one too far away.
let pieces = [
line(&[(0.0, 0.0), (10.0, 0.0)], false),
line(&[(20.0, 10.0), (10.05, 0.0)], false),
line(&[(20.0, 10.0), (30.0, 10.0)], false),
line(&[(31.0, 10.0), (40.0, 10.0)], false),
];
let out = rejoin(&pieces, 0.1);
assert_eq!(out.len(), 1, "{out:?}");
assert_eq!(out[0].members, [0, 1, 2]);
assert_eq!(points(&out[0].path), [(0.0, 0.0), (10.0, 0.0), (20.0, 10.0), (30.0, 10.0)]);
assert!(!out[0].path.closed);
// With a wider gap the last piece joins too.
assert_eq!(rejoin(&pieces, 1.0)[0].members, [0, 1, 2, 3]);
// Nothing within the gap: nothing joins.
assert!(rejoin(&pieces[2..], 0.5).is_empty());
}
#[test]
fn rejoin_takes_the_straightest_continuation_and_closes_loops() {
// Piece 0 ends at the origin; piece 1 goes straight on, piece 2 turns back.
let pieces = [line(&[(-10.0, 0.0), (0.0, 0.0)], false), line(&[(0.0, 0.0), (0.0, 10.0)], false), line(&[(0.0, 0.0), (10.0, 0.0)], false)];
let out = rejoin(&pieces, 0.1);
assert_eq!(out.len(), 1);
assert_eq!(out[0].members, [0, 2]);
// Four sides of a square close into one path.
let sides = [
line(&[(0.0, 0.0), (10.0, 0.0)], false),
line(&[(10.0, 0.0), (10.0, 10.0)], false),
line(&[(0.0, 10.0), (10.0, 10.0)], false),
line(&[(0.0, 10.0), (0.0, 0.0)], false),
];
let out = rejoin(&sides, 0.1);
assert_eq!(out.len(), 1);
assert!(out[0].path.closed);
assert_eq!(out[0].path.anchors.len(), 4);
// Closed, single-anchor and non-finite pieces stay out; bad gaps join nothing.
let odd = [line(&[(0.0, 0.0), (1.0, 0.0), (0.0, 1.0)], true), line(&[(1.0, 0.0)], false), line(&[(f64::NAN, 0.0), (0.0, 1.0)], false)];
assert!(rejoin(&odd, 1.0).is_empty());
assert!(rejoin(&sides, f64::NAN).is_empty() && rejoin(&sides, -1.0).is_empty());
}
No file is open. Choose one in the tree, or press Ctrl+O (⌘O on a Mac) to find one by name.
Syntax highlighting could not load. The unmodified read-only text remains available above.