2bc41aeb8602
fold.rs
//! The panels and hinges of a packaging blank, from its fold lines.
//!
//! Cut lines bound the material. Each connected piece of Cut lines with material is one blank: its
//! outline is the largest closed Cut subpath of the piece when every other face of the piece lies
//! inside it or inside another closed Cut subpath, and the piece's outer boundary otherwise. A face
//! is material when it lies inside that outline and inside no other closed Cut subpath of the piece,
//! so a slot drawn as a rectangle across the outline leaves the same material as a notch drawn in
//! it. Crease, Partial Cut and Perforation lines divide the material into panels; the pieces of them
//! between two panels are that pair's hinge. [`blanks`] also lists what is wrong with the lines
//! ([`IssueCode`]).
use std::collections::{HashMap, HashSet};
use vectorcraft_geom::kurbo::{Line, ParamCurveArclen, ParamCurveNearest, PathSeg};
use vectorcraft_geom::{Affine, BezPath, FillRule, ParamCurve, PathData, Point, Rect, Shape as _, SubPath};
use vectorcraft_pathops::{Adjacency, DEFAULT_PRECISION, SHAPE_BUILDER_MAX_SEGMENTS, Shape, adjacency, find_gaps, interior_point, unite_all};
/// Most panels one blank may have. Its hinges are the edges of a planar graph on its panels, so there
/// are at most 3 ร 256 - 6 = 762 of them.
pub const MAX_PANELS: usize = 256;
/// Most segments the fold lines may have together.
pub const MAX_SEGMENTS: usize = SHAPE_BUILDER_MAX_SEGMENTS;
/// What a fold line does.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum LineKind {
/// Separates the material.
Cut,
/// A fold.
Crease,
/// A fold cut part way through the board.
PartialCut,
/// A fold along a line of cuts.
Perforation,
}
impl LineKind {
/// The angle (degrees) a line of this kind folds at: 90 for a Crease or a Perforation, -90 for
/// a Partial Cut. A positive angle folds away from the printed side; none for a Cut.
pub fn fold_angle(self) -> Option<f64> {
match self {
LineKind::Cut => None,
LineKind::Crease | LineKind::Perforation => Some(90.0),
LineKind::PartialCut => Some(-90.0),
}
}
}
/// A fold line: the path (document coordinates), its kind, and a key the issues name it by.
#[derive(Clone, Debug)]
pub struct FoldLine {
pub path: PathData,
pub kind: LineKind,
pub key: u64,
}
/// One blank: its panels, the hinges between them, and its holes.
#[derive(Clone, Debug, Default)]
pub struct Blank {
pub panels: Vec<Panel>,
pub hinges: Vec<Hinge>,
pub holes: Vec<PathData>,
}
/// A panel: an area of material between fold lines.
#[derive(Clone, Debug)]
pub struct Panel {
pub outline: PathData,
pub area: f64,
}
impl Panel {
/// A point inside the panel, or the middle of its bounds for one too thin to find one in.
pub fn point_inside(&self) -> Option<Point> {
point_in(&self.outline)
}
}
/// The hinge between panels `a` and `b` (indices into the blank's panels, `a` < `b`): the straight
/// line from `from` to `to`, made of the lines `keys`. `straight` is false when its pieces are not on
/// one straight line within the tolerance; `from` and `to` are then on the line through its longest
/// piece. `angle` (degrees) is the fold angle of the kind of line its longest piece is
/// ([`LineKind::fold_angle`]).
#[derive(Clone, Debug)]
pub struct Hinge {
pub a: usize,
pub b: usize,
pub from: Point,
pub to: Point,
pub keys: Vec<u64>,
pub straight: bool,
pub angle: f64,
}
/// What can be wrong with fold lines, in the order [`blanks`] lists them.
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum IssueCode {
/// No Cut line.
NoCut,
/// The Cut lines enclose no area.
Open,
/// An end of a Cut line meets no other fold line within the tolerance (a slit that ends on a
/// crease is not loose).
LooseEnd,
/// An end of a Cut line comes within the tolerance of a Cut line without meeting it; the panels
/// are built with the gap closed.
Gap,
/// Over [`MAX_SEGMENTS`] segments or [`MAX_PANELS`] panels in a blank, or the lines can't be
/// mapped.
TooComplex,
/// A Cut line and a crease lie on top of each other.
CutOverCrease,
/// Two Cut lines, or two of the lines that fold (of the same kind or not), lie on top of each
/// other.
Duplicate,
/// A crease ends inside a panel.
DanglingCrease,
/// A crease divides no two panels.
NoSplit,
/// A crease lies outside every blank, wholly, or in part for the tolerance or more.
Outside,
/// A hinge's pieces are not on one straight line.
NotStraight,
/// A gap between lines is narrower than the planar map can tell apart.
Sliver,
/// A hole holds crease lines, or a blank lies inside a hole.
Ambiguous,
/// A panel is joined to the largest panel of its blank by no chain of hinges.
LoosePanel,
/// A fold line is on a layer that does not print (the caller reports it).
NonPrinting,
}
impl IssueCode {
/// Every code, in order.
pub const ALL: [IssueCode; 15] = [
IssueCode::NoCut,
IssueCode::Open,
IssueCode::LooseEnd,
IssueCode::Gap,
IssueCode::TooComplex,
IssueCode::CutOverCrease,
IssueCode::Duplicate,
IssueCode::DanglingCrease,
IssueCode::NoSplit,
IssueCode::Outside,
IssueCode::NotStraight,
IssueCode::Sliver,
IssueCode::Ambiguous,
IssueCode::LoosePanel,
IssueCode::NonPrinting,
];
/// The code's stable id.
pub fn id(self) -> &'static str {
match self {
IssueCode::NoCut => "noCut",
IssueCode::Open => "open",
IssueCode::LooseEnd => "looseEnd",
IssueCode::Gap => "gap",
IssueCode::TooComplex => "tooComplex",
IssueCode::CutOverCrease => "cutOverCrease",
IssueCode::Duplicate => "duplicate",
IssueCode::DanglingCrease => "danglingCrease",
IssueCode::NoSplit => "noSplit",
IssueCode::Outside => "outside",
IssueCode::NotStraight => "notStraight",
IssueCode::Sliver => "sliver",
IssueCode::Ambiguous => "ambiguous",
IssueCode::LoosePanel => "loosePanel",
IssueCode::NonPrinting => "nonPrinting",
}
}
/// Whether it is an error (the blank can't be made as drawn) rather than a warning.
pub fn is_error(self) -> bool {
matches!(self, IssueCode::NoCut | IssueCode::Open | IssueCode::LooseEnd | IssueCode::TooComplex | IssueCode::CutOverCrease)
}
}
/// One issue: its code, the lines it is about, and the place it is at, when it has one.
#[derive(Clone, Debug, PartialEq)]
pub struct Issue {
pub code: IssueCode,
pub keys: Vec<u64>,
pub at: Option<Point>,
}
impl Issue {
fn new(code: IssueCode, mut keys: Vec<u64>, at: Option<Point>) -> Self {
keys.sort_unstable();
keys.dedup();
Issue { code, keys, at }
}
}
/// One subpath of a fold line.
struct Piece {
sp: SubPath,
line: usize,
}
/// The blanks `lines` make, and their issues in [`IssueCode`] order. `tolerance` (points) is how
/// far apart a Cut line's end and another Cut line may be and still be joined, by a line [`blanks`]
/// adds, and how far a hinge's pieces may stray from one straight line. Nothing is built when there
/// is no Cut line, the lines are too complex, or the Cut lines enclose no area.
pub fn blanks(lines: &[FoldLine], tolerance: f64) -> (Vec<Blank>, Vec<Issue>) {
let tolerance = if tolerance.is_finite() && tolerance > 0.0 { tolerance } else { DEFAULT_PRECISION };
// Counted before anything is copied.
let segments = lines.iter().flat_map(|l| &l.path.subpaths).filter(|sp| usable(sp)).try_fold(0usize, |n, sp| {
let n = n.saturating_add(sp.segment_count());
(n <= MAX_SEGMENTS).then_some(n)
});
if segments.is_none() {
return (vec![], vec![Issue::new(IssueCode::TooComplex, vec![], None)]);
}
let pieces: Vec<Piece> = lines
.iter()
.enumerate()
.flat_map(|(line, l)| l.path.subpaths.iter().filter(|sp| usable(sp)).map(move |sp| Piece { sp: sp.clone(), line }))
.collect();
let mut issues = vec![];
let kind = |p: &Piece| lines.get(p.line).map_or(LineKind::Cut, |l| l.kind);
let key = |p: &Piece| lines.get(p.line).map_or(0, |l| l.key);
let cuts: Vec<&Piece> = pieces.iter().filter(|p| kind(p) == LineKind::Cut).collect();
if cuts.is_empty() {
return (vec![], vec![Issue::new(IssueCode::NoCut, vec![], None)]);
}
let folds: Vec<&Piece> = pieces.iter().filter(|p| kind(p) != LineKind::Cut).collect();
if !gap_work_fits(&cuts, tolerance) {
return (vec![], vec![Issue::new(IssueCode::TooComplex, vec![], None)]);
}
let cut_shapes: Vec<Shape> = cuts.iter().map(|p| shape(p.sp.clone())).collect();
let gaps = find_gaps(&cut_shapes, tolerance);
// `find_gaps` takes ends closer than 1/10,000 of the tolerance as joined, which the map may not
// join: those are bridged too, without an issue.
let joined = find_gaps(&cut_shapes, (tolerance * 1e-4).max(1e-6));
// An end a gap starts or ends at is not loose.
let gap_ends =
Cells::new(gaps.iter().chain(&joined).flatten().map(|&e| (Rect::from_points(e, e), (e.x.to_bits(), e.y.to_bits()))).collect(), 0.0, 4096.0);
let bridged = |at: Point| gap_ends.near(at, 1e-6).into_iter().any(|(x, y)| Point::new(f64::from_bits(x), f64::from_bits(y)).distance(at) <= 1e-6);
issues.extend(
loose_ends(&cuts, &folds, tolerance)
.into_iter()
.filter(|&(_, at)| !bridged(at))
.map(|(i, at)| Issue::new(IssueCode::LooseEnd, vec![cuts.get(i).map_or(0, |p| key(p))], Some(at))),
);
if !gaps.is_empty() {
// The cut lines by their ends, to name the line each gap starts from.
let at_ends = cuts.iter().enumerate().flat_map(|(i, p)| ends(&p.sp).into_iter().map(move |e| (Rect::from_points(e, e), (i, e))));
let by_end = Cells::new(at_ends.map(|(r, (i, e))| (r, (i, e.x.to_bits(), e.y.to_bits()))).collect(), 0.0, 4096.0);
for g in &gaps {
let of = by_end
.near(g[0], 1e-6)
.into_iter()
.find(|&(_, x, y)| Point::new(f64::from_bits(x), f64::from_bits(y)).distance(g[0]) <= 1e-6)
.and_then(|(i, _, _)| cuts.get(i))
.map(|p| key(p));
issues.push(Issue::new(IssueCode::Gap, of.into_iter().collect(), Some(g[0])));
}
}
let gaps: Vec<[Point; 2]> = gaps.into_iter().chain(joined).collect();
let gap_shape = shape_of_gaps(&gaps);
let Some(material) = Material::new(&cuts, &gaps, cut_shapes.into_iter().chain(gap_shape.clone()).collect()) else {
issues.push(Issue::new(IssueCode::TooComplex, vec![], None));
return (vec![], sorted(issues));
};
if material.blanks.is_empty() {
issues.push(Issue::new(IssueCode::Open, cuts.iter().map(|p| key(p)).collect(), None));
return (vec![], sorted(issues));
}
let all: Vec<Shape> = pieces.iter().map(|p| shape(p.sp.clone())).chain(gap_shape).collect();
let Some(full) = adjacency(&all, DEFAULT_PRECISION) else {
issues.push(Issue::new(IssueCode::TooComplex, vec![], None));
return (vec![], sorted(issues));
};
let cut_lines: Vec<usize> = cuts.iter().map(|p| p.line).collect();
let ctx = Context { lines, pieces: &pieces, cut_lines: &cut_lines, material: &material, full: &full, tolerance };
let built = ctx.build(&mut issues);
(built, sorted(issues))
}
/// Most (open end, Cut segment) pairs within the tolerance of each other that the gap search may
/// look at.
const MAX_GAP_CANDIDATES: usize = 1 << 24;
/// Whether the gap search over `cuts` stays within [`MAX_GAP_CANDIDATES`]: it looks at the Cut
/// segments within `tolerance` of each open end, and lines drawn on top of each other many times
/// over make that work grow with the square of their number. The count stops at the limit.
fn gap_work_fits(cuts: &[&Piece], tolerance: f64) -> bool {
let boxes: Vec<(Rect, usize)> = cuts
.iter()
.flat_map(|p| {
PathData::single(p.sp.clone()).to_bezpath().segments().map(|s| s.bounding_box().inflate(tolerance, tolerance)).collect::<Vec<_>>()
})
.enumerate()
.map(|(i, b)| (b, i))
.collect();
let grid = Cells::new(boxes, 2.0 * tolerance, 4096.0);
let mut work = 0usize;
for e in cuts.iter().flat_map(|p| ends(&p.sp)) {
work = work.saturating_add(grid.near(e, 0.0).len());
if work > MAX_GAP_CANDIDATES {
return false;
}
}
true
}
fn sorted(mut issues: Vec<Issue>) -> Vec<Issue> {
issues.sort_by_key(|i| i.code);
issues
}
/// A subpath with two anchors or more, every coordinate finite.
fn usable(sp: &SubPath) -> bool {
sp.anchors.len() >= 2 && sp.anchors.iter().all(|a| a.p.is_finite() && a.h_in.is_finite() && a.h_out.is_finite())
}
fn shape(sp: SubPath) -> Shape {
Shape::new(PathData::single(sp), FillRule::NonZero, 0)
}
/// The lines across `gaps`, as one input.
fn shape_of_gaps(gaps: &[[Point; 2]]) -> Option<Shape> {
(!gaps.is_empty()).then(|| Shape::new(PathData::new(gaps.iter().map(|g| SubPath::polyline(g, false)).collect()), FillRule::NonZero, 0))
}
/// The two ends of an open subpath; none for a closed one or one that ends where it starts.
fn ends(sp: &SubPath) -> Vec<Point> {
match (sp.anchors.first(), sp.anchors.last()) {
(Some(a), Some(b)) if !sp.closed && a.p.distance(b.p) > 1e-6 => vec![a.p, b.p],
_ => vec![],
}
}
/// Whether `sp` encloses an area: closed, or open with its ends together.
fn is_loop(sp: &SubPath) -> bool {
ends(sp).is_empty() && sp.anchors.len() >= 2
}
/// Most grid cells one item is filed under by [`Cells`]; a larger one is tried for every point.
const SPAN: usize = 1024;
/// The farthest cell from the grid's origin, on each axis, that [`Cells`] numbers a point in.
const CELL_LIMIT: f64 = 1_048_576.0;
/// Most (cell, item) entries [`Cells`] holds in all; the items past it are tried for every point, as
/// large ones are.
const CELL_ENTRIES: usize = 1 << 21;
/// Items (segments, faces, ends) by the cells of a square grid that their bounds cover, so that
/// finding the items near a point tests only those in its cells.
struct Cells<T> {
origin: Point,
cell: f64,
cells: HashMap<(i64, i64), Vec<T>>,
/// Items whose bounds cover more than [`SPAN`] cells, near every point.
wide: Vec<T>,
}
impl<T: Copy + Ord> Cells<T> {
/// `items` by their bounds, in cells `cell` wide or `1/divisions` of all the bounds where that is
/// wider.
fn new(items: Vec<(Rect, T)>, cell: f64, divisions: f64) -> Self {
let bounds = items.iter().map(|(b, _)| *b).filter(Rect::is_finite).reduce(|a, b| a.union(b)).unwrap_or_default();
let cell = cell.max(bounds.width().max(bounds.height()) / divisions);
let cell = if cell.is_finite() && cell > 0.0 { cell } else { 1.0 };
let mut grid = Cells { origin: bounds.origin(), cell, cells: HashMap::new(), wide: vec![] };
let mut entries = 0usize;
for (b, item) in items {
let ((x0, y0), (x1, y1)) = (grid.cell_of(Point::new(b.x0, b.y0)), grid.cell_of(Point::new(b.x1, b.y1)));
let span = usize::try_from((x1 - x0 + 1).saturating_mul(y1 - y0 + 1)).unwrap_or(usize::MAX);
if span > SPAN || entries.saturating_add(span) > CELL_ENTRIES {
grid.wide.push(item);
continue;
}
entries += span;
for x in x0..=x1 {
for y in y0..=y1 {
grid.cells.entry((x, y)).or_default().push(item);
}
}
}
grid
}
fn cell_of(&self, p: Point) -> (i64, i64) {
let at = |v: f64, o: f64| ((v - o) / self.cell).floor().clamp(-CELL_LIMIT, CELL_LIMIT) as i64;
(at(p.x, self.origin.x), at(p.y, self.origin.y))
}
/// The items whose bounds come within `r` of `p` (and some farther ones), each once. When `r`
/// spans more cells than hold items, the cells that hold items are read instead.
fn near(&self, p: Point, r: f64) -> Vec<T> {
let mut out = self.wide.clone();
let ((x0, y0), (x1, y1)) = (self.cell_of(Point::new(p.x - r, p.y - r)), self.cell_of(Point::new(p.x + r, p.y + r)));
let span = (x1 - x0 + 1).saturating_mul(y1 - y0 + 1);
if usize::try_from(span).map_or(true, |n| n > self.cells.len()) {
for (&(x, y), items) in &self.cells {
if (x0..=x1).contains(&x) && (y0..=y1).contains(&y) {
out.extend(items);
}
}
} else {
for x in x0..=x1 {
for y in y0..=y1 {
out.extend(self.cells.get(&(x, y)).into_iter().flatten());
}
}
}
out.sort_unstable();
out.dedup();
out
}
}
/// The ends of `cuts` that lie more than `tolerance` from every other fold line among `cuts` and
/// `folds`, as (index into `cuts`, end). A line's own points count when they are more than
/// `tolerance` from the end along the line, so a cut line that comes back to its own end meets it.
fn loose_ends(cuts: &[&Piece], folds: &[&Piece], tolerance: f64) -> Vec<(usize, Point)> {
let segs: Vec<Vec<PathSeg>> = cuts.iter().chain(folds).map(|p| PathData::single(p.sp.clone()).to_bezpath().segments().collect()).collect();
let boxes = segs.iter().enumerate().flat_map(|(j, ss)| ss.iter().enumerate().map(move |(k, s)| (s.bounding_box(), (j, k))));
// The cells are as wide as the tolerance, or 1/4096 of the lines where that is wider.
let grid = Cells::new(boxes.collect(), tolerance, 4096.0);
let mut out = vec![];
for (i, p) in cuts.iter().enumerate() {
let own = segs.get(i).map(Vec::as_slice).unwrap_or_default();
// How far along the line each of its segments starts, and the line's length.
let starts: Vec<f64> = own.iter().scan(0.0, |at, s| Some(std::mem::replace(at, *at + s.arclen(1e-3)))).collect();
let total = own.last().zip(starts.last()).map_or(0.0, |(s, at)| at + s.arclen(1e-3));
for (k, e) in ends(&p.sp).into_iter().enumerate() {
let near = grid.near(e, tolerance).into_iter().any(|(j, s)| {
let Some(seg) = segs.get(j).and_then(|ss| ss.get(s)) else { return false };
let b = seg.bounding_box();
if e.x < b.x0 - tolerance || e.x > b.x1 + tolerance || e.y < b.y0 - tolerance || e.y > b.y1 + tolerance {
return false;
}
let hit = seg.nearest(e, 1e-9);
if hit.distance_sq.sqrt() > tolerance {
return false;
}
if j != i {
return true;
}
let along = starts.get(s).copied().unwrap_or(0.0) + seg.subsegment(0.0..hit.t).arclen(1e-3);
(if k == 0 { along } else { total - along }) > tolerance
});
if !near {
out.push((i, e));
}
}
}
out
}
/// A point inside `path`, or the middle of its bounds for one too thin to find one in.
fn point_in(path: &PathData) -> Option<Point> {
interior_point(path).or_else(|| path.bounds().map(|b| b.center()))
}
fn contains(bp: &BezPath, p: Point) -> bool {
bp.winding(p) != 0
}
/// The loops that open Cut pieces and the lines across `gaps` make end to end: each chain of them
/// whose every end meets exactly one end of another piece of the chain (within 1e-6), as (index
/// into `cuts` of its first Cut piece, closed path). Pieces that lie on no cycle are left out first.
/// A connected set of the remaining pieces with an end where three or more meet gives the outlines
/// of the faces it encloses instead.
fn chains(cuts: &[&Piece], gaps: &[[Point; 2]]) -> Vec<(usize, BezPath)> {
const NEAR: f64 = 1e-6;
// Cell numbers stay far from the ends of `i64`, so a neighbor's number does not overflow.
let cell = |v: f64| (v / NEAR).round().clamp(-1e15, 1e15) as i64;
let key = |p: Point| (cell(p.x), cell(p.y));
// The ends by node: ends within `NEAR` of a node's first end share it.
let mut nodes: HashMap<(i64, i64), usize> = HashMap::new();
let mut firsts: Vec<Point> = vec![];
let mut node_of = |p: Point| {
let (kx, ky) = key(p);
for dx in -1..=1 {
for dy in -1..=1 {
if let Some(&n) = nodes.get(&(kx.saturating_add(dx), ky.saturating_add(dy)))
&& firsts.get(n).is_some_and(|q| q.distance(p) <= NEAR)
{
return n;
}
}
}
firsts.push(p);
nodes.insert((kx, ky), firsts.len() - 1);
firsts.len() - 1
};
// The open Cut pieces (with their index into `cuts`) and the gap lines, each with its segments.
let pieces = cuts
.iter()
.enumerate()
.filter(|(_, p)| ends(&p.sp).len() == 2)
.map(|(i, p)| (Some(i), PathData::single(p.sp.clone()).to_bezpath().segments().collect()));
let lines = gaps.iter().map(|g| (None, vec![PathSeg::Line(Line::new(g[0], g[1]))]));
let items: Vec<(Option<usize>, Vec<PathSeg>)> = pieces.chain(lines).collect();
// (index into `items`, start node, end node) of each, and the pieces at each node.
let open: Vec<(usize, usize, usize)> =
items.iter().enumerate().filter_map(|(k, (_, segs))| Some((k, node_of(segs.first()?.start()), node_of(segs.last()?.end())))).collect();
let mut at: HashMap<usize, Vec<usize>> = HashMap::new();
for (k, &(_, a, b)) in open.iter().enumerate() {
at.entry(a).or_default().push(k);
at.entry(b).or_default().push(k);
}
// A piece that lies on no cycle of pieces (a slit, a line from another one's side, a cut that
// joins two loops) is no part of a loop: such pieces are dropped, so that a slit at a loop's
// corner does not stop the loop.
let live: Vec<bool> = bridges(firsts.len(), &open).into_iter().map(|b| !b).collect();
for ks in at.values_mut() {
ks.retain(|&k| live.get(k) == Some(&true));
}
// The connected pieces of what is left, by node. In a piece where some node joins more than two
// pieces (a window with a cut across it), the loop is the outline of the faces the piece
// encloses; the other pieces are walked end to end below.
let mut group: Vec<usize> = (0..firsts.len()).collect();
for (k, &(_, a, b)) in open.iter().enumerate() {
if live.get(k) == Some(&true) {
let (ra, rb) = (root_of(&mut group, a), root_of(&mut group, b));
if let Some(slot) = group.get_mut(ra) {
*slot = rb;
}
}
}
let mut branched: HashSet<usize> = HashSet::new();
for (&n, ks) in &at {
if !ks.is_empty() && ks.len() != 2 {
branched.insert(root_of(&mut group, n));
}
}
let mut used: Vec<bool> = live.iter().map(|l| !l).collect();
let mut out = vec![];
let mut joined: HashMap<usize, Vec<usize>> = HashMap::new();
for (k, &(_, a, _)) in open.iter().enumerate() {
let r = root_of(&mut group, a);
if used.get(k) == Some(&false) && branched.contains(&r) {
joined.entry(r).or_default().push(k);
if let Some(u) = used.get_mut(k) {
*u = true;
}
}
}
let mut joined: Vec<Vec<usize>> = joined.into_values().collect();
joined.sort_unstable();
for ks in joined {
let Some(first_cut) = ks.iter().filter_map(|&k| open.get(k).and_then(|&(j, _, _)| items.get(j)).and_then(|(i, _)| *i)).min() else {
continue;
};
let shapes: Vec<Shape> = ks
.iter()
.filter_map(|&k| open.get(k).and_then(|&(j, _, _)| items.get(j)))
.map(|(_, segs)| Shape::new(PathData::from_bezpath(&BezPath::from_path_segments(segs.iter().copied())), FillRule::NonZero, 0))
.collect();
out.extend(enclosed_loops(&shapes).into_iter().map(|bp| (first_cut, bp)));
}
for start in 0..open.len() {
if used.get(start) != Some(&false) {
continue;
}
// Walk from the start piece's first end until the chain comes back to it, or stops.
let Some(&(_, first_node, _)) = open.get(start) else { continue };
let (mut k, mut from, mut walk) = (start, first_node, vec![]);
let closed = loop {
let Some(&(_, a, b)) = open.get(k) else { break false };
if used.get(k) != Some(&false) {
break false;
}
if let Some(u) = used.get_mut(k) {
*u = true;
}
let forward = a == from;
walk.push((k, forward));
let to = if forward { b } else { a };
if to == first_node {
break true;
}
let next = at.get(&to).filter(|ks| ks.len() == 2).and_then(|ks| ks.iter().copied().find(|&j| j != k));
match next {
Some(j) => (k, from) = (j, to),
None => break false,
}
};
if !closed || at.get(&first_node).is_none_or(|ks| ks.len() != 2) {
continue;
}
let mut bp = BezPath::new();
let mut first_cut = None;
for (n, &(k, forward)) in walk.iter().enumerate() {
let Some((i, segs)) = open.get(k).and_then(|&(j, _, _)| items.get(j)) else { continue };
first_cut = first_cut.or(*i);
let segs: Vec<PathSeg> = if forward { segs.clone() } else { segs.iter().rev().map(|s| s.reverse()).collect() };
for (m, s) in segs.iter().enumerate() {
if n == 0 && m == 0 {
bp.move_to(s.start());
}
match *s {
PathSeg::Line(l) => bp.line_to(l.p1),
PathSeg::Quad(q) => bp.quad_to(q.p1, q.p2),
PathSeg::Cubic(c) => bp.curve_to(c.p1, c.p2, c.p3),
}
}
}
bp.close_path();
if let Some(i) = first_cut {
out.push((i, bp));
}
}
out
}
/// The loops of a connected set of open Cut pieces `shapes` where some end joins three pieces or
/// more: the outline of all the faces they enclose, and for each group of faces that meet only other
/// faces and are bounded by pieces that meet end to end (a window joined to an outline by two slits,
/// not the middle cell of cut lines that cross), the group's outline, as the pieces of a chain that
/// closes count as one closed Cut line.
fn enclosed_loops(shapes: &[Shape]) -> Vec<BezPath> {
let Some(map) = adjacency(shapes, DEFAULT_PRECISION) else { return vec![] };
let mut inner = vec![true; map.faces.len()];
for e in &map.edges {
for (a, b) in [(e.left, e.right), (e.right, e.left)] {
if b.is_none()
&& let Some(slot) = a.and_then(|f| inner.get_mut(f))
{
*slot = false;
}
}
}
let mut group: Vec<usize> = (0..map.faces.len()).collect();
for e in &map.edges {
if let (Some(a), Some(b)) = (e.left, e.right)
&& a != b
&& inner.get(a) == Some(&true)
&& inner.get(b) == Some(&true)
{
let (ra, rb) = (root_of(&mut group, a), root_of(&mut group, b));
if let Some(slot) = group.get_mut(ra) {
*slot = rb;
}
}
}
let mut sets: HashMap<usize, Vec<usize>> = HashMap::new();
for f in (0..map.faces.len()).filter(|&f| inner.get(f) == Some(&true)) {
sets.entry(root_of(&mut group, f)).or_default().push(f);
}
// A group is a loop when its boundary edges come from pieces that lie on that boundary alone,
// that is, pieces that meet end to end round it; pieces of lines that cross it go on past it.
let mut edges_of: HashMap<usize, Vec<usize>> = HashMap::new();
for (i, e) in map.edges.iter().enumerate() {
for &s in &e.sources {
edges_of.entry(s).or_default().push(i);
}
}
let side = |g: &mut Vec<usize>, f: Option<usize>| f.filter(|&f| inner.get(f) == Some(&true)).map(|f| root_of(g, f));
let mut boundary: HashMap<usize, HashSet<usize>> = HashMap::new();
for (i, e) in map.edges.iter().enumerate() {
let (l, r) = (side(&mut group, e.left), side(&mut group, e.right));
if l != r {
for root in [l, r].into_iter().flatten() {
boundary.entry(root).or_default().insert(i);
}
}
}
let whole = |root: &usize| {
boundary.get(root).is_some_and(|edges| {
edges
.iter()
.filter_map(|&i| map.edges.get(i))
.flat_map(|e| &e.sources)
.all(|s| edges_of.get(s).is_some_and(|all| all.iter().all(|i| edges.contains(i))))
})
};
let mut sets: Vec<(usize, Vec<usize>)> = sets.into_iter().filter(|(root, _)| whole(root)).collect();
sets.push((usize::MAX, (0..map.faces.len()).collect()));
sets.sort_unstable();
let mut out = vec![];
for (_, set) in sets {
let faces: Vec<(&PathData, FillRule)> = set.iter().filter_map(|&f| map.faces.get(f)).map(|f| (&f.path, FillRule::NonZero)).collect();
if !faces.is_empty() {
out.extend(unite_all(&faces).subpaths.into_iter().map(|sp| PathData::single(sp).to_bezpath()));
}
}
out
}
/// The node that stands for `v`'s set in `group` (a disjoint-set forest), halving the path on the way.
fn root_of(group: &mut [usize], mut v: usize) -> usize {
while let Some(&up) = group.get(v) {
if up == v {
break;
}
let next = group.get(up).copied().unwrap_or(up);
if let Some(slot) = group.get_mut(v) {
*slot = next;
}
v = next;
}
v
}
/// Which of `edges` ((id, end node, end node), nodes below `nodes`) lie on no cycle: the bridges of
/// the graph, found depth first without recursion.
fn bridges(nodes: usize, edges: &[(usize, usize, usize)]) -> Vec<bool> {
let mut adj: Vec<Vec<(usize, usize)>> = vec![vec![]; nodes];
for (k, &(_, a, b)) in edges.iter().enumerate() {
adj.get_mut(a).into_iter().for_each(|l| l.push((b, k)));
adj.get_mut(b).into_iter().for_each(|l| l.push((a, k)));
}
let mut bridge = vec![false; edges.len()];
let (mut disc, mut low) = (vec![usize::MAX; nodes], vec![0usize; nodes]);
let mut timer = 0usize;
for s in 0..nodes {
if disc.get(s) != Some(&usize::MAX) {
continue;
}
let mut stamp = |v: usize, disc: &mut Vec<usize>, low: &mut Vec<usize>| {
disc.get_mut(v).into_iter().for_each(|d| *d = timer);
low.get_mut(v).into_iter().for_each(|l| *l = timer);
timer += 1;
};
stamp(s, &mut disc, &mut low);
// (node, the edge it was reached by, the next of its edges to follow)
let mut stack: Vec<(usize, Option<usize>, usize)> = vec![(s, None, 0)];
while let Some(&(v, by, i)) = stack.last() {
if let Some(&(w, e)) = adj.get(v).and_then(|l| l.get(i)) {
if let Some(top) = stack.last_mut() {
top.2 += 1;
}
if Some(e) == by {
continue;
}
match disc.get(w).copied() {
Some(usize::MAX) => {
stamp(w, &mut disc, &mut low);
stack.push((w, Some(e), 0));
}
Some(d) => {
if let Some(l) = low.get_mut(v) {
*l = (*l).min(d);
}
}
None => {}
}
} else {
stack.pop();
let low_v = low.get(v).copied().unwrap_or(0);
if let Some(&(u, _, _)) = stack.last() {
if let Some(l) = low.get_mut(u) {
*l = (*l).min(low_v);
}
if disc.get(u).is_some_and(|&d| low_v > d)
&& let Some(b) = by.and_then(|e| bridge.get_mut(e))
{
*b = true;
}
}
}
}
}
bridge
}
/// The material the Cut lines leave: the faces of their planar map, which are material, which are
/// holes, and the blanks (connected pieces with material).
struct Material {
map: Adjacency,
/// For each face of `map`: a point inside it, whether it is material, whether it is a hole.
points: Vec<Option<Point>>,
material: Vec<bool>,
hole: Vec<bool>,
/// The pieces of `map` that are blanks, in order, and each one's outline.
blanks: Vec<usize>,
bounds: Vec<BezPath>,
/// For each piece of `map`, the blank (index into `blanks`) it is part of: its own, or for a
/// piece that lies in a blank's material (a window), that blank.
owner: Vec<Option<usize>>,
/// The faces of each piece of `map`, and its edges.
faces_by_piece: Vec<Vec<usize>>,
edges_by_piece: Vec<Vec<usize>>,
/// Each face's outer boundary and its whole path (with its holes), and the faces by where they
/// are.
outer: Vec<BezPath>,
whole: Vec<BezPath>,
face_cells: Cells<usize>,
/// The blanks by where their outlines are (built once every piece is classified).
bound_cells: Cells<usize>,
}
/// A loop among the Cut lines: its path and its area.
type Loop = (BezPath, f64);
impl Material {
/// The material of `cuts` with the lines across `gaps`, mapped as `shapes` (the cuts, then the
/// gap lines).
fn new(cuts: &[&Piece], gaps: &[[Point; 2]], shapes: Vec<Shape>) -> Option<Self> {
let map = adjacency(&shapes, DEFAULT_PRECISION)?;
let points: Vec<Option<Point>> = map.faces.iter().map(|f| point_in(&f.path)).collect();
let pieces = map.faces.iter().map(|f| f.piece + 1).chain(map.edges.iter().map(|e| e.piece + 1)).max().unwrap_or(0);
let mut faces_by_piece = vec![vec![]; pieces];
for (f, face) in map.faces.iter().enumerate() {
if let Some(list) = faces_by_piece.get_mut(face.piece) {
list.push(f);
}
}
// The piece each input is part of, from the edges it lies on.
let mut piece_of_input: Vec<Option<usize>> = vec![None; shapes.len()];
let mut edges_by_piece = vec![vec![]; pieces];
for (e, edge) in map.edges.iter().enumerate() {
if let Some(list) = edges_by_piece.get_mut(edge.piece) {
list.push(e);
}
for &s in &edge.sources {
if let Some(slot) = piece_of_input.get_mut(s).filter(|p| p.is_none()) {
*slot = Some(edge.piece);
}
}
}
let mut loops: Vec<Vec<Loop>> = vec![vec![]; pieces];
for (i, p) in cuts.iter().enumerate().filter(|(_, p)| is_loop(&p.sp)) {
let Some(list) = piece_of_input.get(i).copied().flatten().and_then(|piece| loops.get_mut(piece)) else { continue };
let bp = PathData::single(SubPath::of(p.sp.anchors.clone(), true)).to_bezpath();
let area = bp.area().abs();
list.push((bp, area));
}
// Loops drawn as open pieces end to end, such as a slot of four lines.
for (i, bp) in chains(cuts, gaps) {
let Some(list) = piece_of_input.get(i).copied().flatten().and_then(|piece| loops.get_mut(piece)) else { continue };
let area = bp.area().abs();
list.push((bp, area));
}
// Each piece's outer boundary and a point of it.
let mut outlines: Vec<Option<(BezPath, Option<Point>)>> = vec![None; pieces];
for o in &map.outlines {
if let Some(slot) = outlines.get_mut(o.piece).filter(|s| s.is_none()) {
*slot = Some((o.path.to_bezpath(), o.path.subpaths.first().and_then(|sp| sp.anchors.first()).map(|a| a.p)));
}
}
// Outer pieces first: the face a piece lies in belongs to a piece with a larger outline.
let mut order: Vec<(usize, f64, Option<Point>)> =
outlines.iter().enumerate().map(|(p, o)| (p, o.as_ref().map_or(0.0, |o| o.0.area().abs()), o.as_ref().and_then(|o| o.1))).collect();
order.sort_by(|a, b| b.1.total_cmp(&a.1));
let outer: Vec<BezPath> =
map.faces.iter().map(|f| f.path.subpaths.first().map(|sp| PathData::single(sp.clone()).to_bezpath()).unwrap_or_default()).collect();
let whole: Vec<BezPath> = map.faces.iter().map(|f| f.path.to_bezpath()).collect();
let face_cells = Cells::new(outer.iter().enumerate().map(|(f, bp)| (bp.bounding_box(), f)).collect(), 0.0, 256.0);
let faces = map.faces.len();
let mut m = Material {
map,
points,
material: vec![false; faces],
hole: vec![false; faces],
blanks: vec![],
bounds: vec![],
owner: vec![None; pieces],
faces_by_piece,
edges_by_piece,
outer,
whole,
face_cells,
bound_cells: Cells::new(vec![], 0.0, 256.0),
};
for (piece, _, first) in order {
match first.and_then(|q| m.around(piece, q)) {
// A piece in a blank's material is a hole in it, a window.
Some(f) if m.material.get(f) == Some(&true) => {
let owner = m.map.faces.get(f).and_then(|x| m.owner.get(x.piece)).copied().flatten();
for g in m.faces_by_piece.get(piece).cloned().unwrap_or_default() {
let usable = m.points.get(g).copied().flatten().is_some();
if let Some(h) = m.hole.get_mut(g) {
*h = usable;
}
}
if let Some(o) = m.owner.get_mut(piece) {
*o = owner;
}
}
_ => {
let own = loops.get(piece).map(Vec::as_slice).unwrap_or_default();
let fallback = outlines.get(piece).cloned().flatten().map(|o| o.0);
m.classify(piece, own, fallback);
}
}
}
m.bound_cells = Cells::new(m.bounds.iter().enumerate().map(|(b, bp)| (bp.bounding_box(), b)).collect(), 0.0, 256.0);
Some(m)
}
/// The face of another piece than `piece` whose outer boundary holds `q`, a point of its
/// outline, the one with the smallest outer boundary when several do. The boundaries are
/// compared, not the faces' own areas, which leave out the holes in them.
fn around(&self, piece: usize, q: Point) -> Option<usize> {
let outer_area = |f: usize| self.outer.get(f).map_or(f64::INFINITY, |bp| bp.area().abs());
self.face_cells
.near(q, 0.0)
.into_iter()
.filter(|&f| self.map.faces.get(f).is_some_and(|x| x.piece != piece))
.filter(|&f| self.outer.get(f).is_some_and(|bp| contains(bp, q)))
.min_by(|&a, &b| outer_area(a).total_cmp(&outer_area(b)))
}
fn area(&self, f: usize) -> f64 {
self.map.faces.get(f).map_or(f64::INFINITY, |x| x.area)
}
/// Which faces of `piece` are material and which are holes, by its own loops `loops`; with
/// material, the piece is a blank. A loop that holds the same faces as a larger one (a loop
/// drawn twice) counts once. Its outlines are its largest loop and each smaller loop that shares
/// no face with a larger outline (two outlines joined by a cut line); its other loops cut
/// material out. When the outlines and the loops that cut out do not cover every face (an
/// outline drawn as open lines), every loop cuts out and the blank is bounded by `fallback`, its
/// outer boundary.
fn classify(&mut self, piece: usize, loops: &[Loop], fallback: Option<BezPath>) {
let faces = self.faces_by_piece.get(piece).cloned().unwrap_or_default();
let mut by_area: Vec<&Loop> = loops.iter().collect();
by_area.sort_by(|a, b| b.1.total_cmp(&a.1));
let points = &self.points;
let unusable = |f: usize| points.get(f).copied().flatten().is_none();
// The piece's faces by their points, so that each loop tests only the faces near it.
let at: Vec<(Rect, usize)> =
faces.iter().enumerate().filter_map(|(k, &f)| points.get(f).copied().flatten().map(|p| (Rect::from_points(p, p), k))).collect();
let extent = at.iter().map(|(r, _)| *r).reduce(|a, b| a.union(b));
let near = Cells::new(at, 0.0, 256.0);
// Each loop with the faces of the piece it holds (positions in `faces`, ascending); loops
// that hold none, and loops that hold the same faces as a larger one, are left out.
let mut seen: HashSet<Vec<usize>> = HashSet::new();
let mut own: Vec<(&BezPath, Vec<usize>)> = vec![];
for l in by_area {
let b = l.0.bounding_box().inflate(1e-6, 1e-6);
// Only the part of the loop's bounds where faces are is looked up, a few hundred cells
// across at most.
let Some(q) = extent.map(|e| b.intersect(e)).filter(|q| q.width() >= 0.0 && q.height() >= 0.0) else { continue };
let holds: Vec<usize> = near
.near(q.center(), q.width().max(q.height()) / 2.0)
.into_iter()
.filter(|&k| faces.get(k).and_then(|&f| points.get(f).copied().flatten()).is_some_and(|p| b.contains(p) && contains(&l.0, p)))
.collect();
if !holds.is_empty() && seen.insert(holds.clone()) {
own.push((&l.0, holds));
}
}
// Outlines go largest first; a loop holding a face an outline holds cuts out instead.
let (mut outlines, mut others): (Vec<usize>, Vec<usize>) = (vec![], vec![]);
let mut in_an_outline = vec![false; faces.len()];
let mut held = vec![false; faces.len()];
for (i, (_, holds)) in own.iter().enumerate() {
holds.iter().for_each(|&k| held.get_mut(k).into_iter().for_each(|h| *h = true));
if holds.iter().any(|&k| in_an_outline.get(k) == Some(&true)) {
others.push(i);
} else {
holds.iter().for_each(|&k| in_an_outline.get_mut(k).into_iter().for_each(|h| *h = true));
outlines.push(i);
}
}
let covered = faces.iter().enumerate().all(|(k, &f)| held.get(k) == Some(&true) || unusable(f));
if !covered {
outlines.clear();
others = (0..own.len()).collect();
}
let mut cut = vec![false; faces.len()];
for (_, holds) in others.iter().filter_map(|&i| own.get(i)) {
holds.iter().for_each(|&k| cut.get_mut(k).into_iter().for_each(|c| *c = true));
}
let mut any = false;
for (k, &f) in faces.iter().enumerate() {
let in_outline = outlines.is_empty() || in_an_outline.get(k) == Some(&true);
let cut_out = cut.get(k) == Some(&true);
let material = !unusable(f) && in_outline && !cut_out;
any |= material;
if let Some(m) = self.material.get_mut(f) {
*m = material;
}
if let Some(h) = self.hole.get_mut(f) {
*h = !unusable(f) && in_outline && cut_out;
}
}
self.open_notches(piece, fallback.as_ref());
if any {
let bound = if outlines.is_empty() {
fallback
} else {
let mut all = BezPath::new();
outlines.iter().filter_map(|&o| own.get(o)).for_each(|o| all.extend(o.0.elements().iter().copied()));
Some(all)
};
if let Some(o) = self.owner.get_mut(piece) {
*o = Some(self.blanks.len());
}
self.blanks.push(piece);
self.bounds.push(bound.unwrap_or_default());
}
}
/// Faces of `piece` cut out that meet the outside, directly or through other faces cut out, are
/// a notch, not a hole: they stop being holes. The outside is a usable face that is neither
/// material nor a hole (the part of a slot beyond the outline), or the side with no face of an
/// edge on the piece's outer boundary `outline` (elsewhere a side with no face is a sliver).
fn open_notches(&mut self, piece: usize, outline: Option<&BezPath>) {
let edges = self.edges_by_piece.get(piece).cloned().unwrap_or_default();
let hole = |s: &Self, f: Option<usize>| f.is_some_and(|f| s.hole.get(f) == Some(&true));
let open = |s: &Self, f: Option<usize>| {
f.is_some_and(|f| s.hole.get(f) != Some(&true) && s.material.get(f) != Some(&true) && s.points.get(f).copied().flatten().is_some())
};
// Whether `edge` lies on the piece's outer boundary `outline` (its middle within 1e-6 of
// it): its side with no face is then the outside, not a sliver.
let on_outline = |edge: &vectorcraft_pathops::MapEdge| {
let Some(outline) = outline else { return false };
let segs: Vec<PathSeg> = edge.path.to_bezpath().segments().collect();
let Some(mid) = segs.get(segs.len() / 2).map(|s| s.eval(0.5)) else { return false };
outline.segments().any(|s| s.nearest(mid, 1e-9).distance_sq <= 1e-12)
};
let mut next: HashMap<usize, Vec<usize>> = HashMap::new();
let mut queue = vec![];
for edge in edges.iter().filter_map(|&e| self.map.edges.get(e)) {
for (a, b) in [(edge.left, edge.right), (edge.right, edge.left)] {
let Some(f) = a.filter(|_| a != b && hole(self, a)) else { continue };
if open(self, b) || (b.is_none() && on_outline(edge)) {
queue.push(f);
} else if let Some(g) = b.filter(|_| hole(self, b)) {
next.entry(f).or_default().push(g);
}
}
}
while let Some(f) = queue.pop() {
match self.hole.get_mut(f) {
Some(h) if *h => *h = false,
_ => continue,
}
queue.extend(next.get(&f).into_iter().flatten().copied());
}
}
/// The face of the Cut lines' map that holds `p`, the smallest when several do.
fn face_at(&self, p: Point) -> Option<usize> {
self.face_cells
.near(p, 0.0)
.into_iter()
.filter(|&f| self.whole.get(f).is_some_and(|bp| contains(bp, p)))
.min_by(|&a, &b| self.area(a).total_cmp(&self.area(b)))
}
/// Whether `p` lies inside the outline of a blank.
fn in_a_blank(&self, p: Point) -> bool {
self.bound_cells.near(p, 0.0).into_iter().any(|b| self.bounds.get(b).is_some_and(|bp| contains(bp, p)))
}
/// The blank (index into `blanks`) face `f` is part of.
fn blank_of(&self, f: usize) -> Option<usize> {
let piece = self.map.faces.get(f)?.piece;
self.owner.get(piece).copied().flatten()
}
}
/// What a face of the full map is.
#[derive(Clone, Copy, PartialEq)]
enum Place {
/// Panel `panel` of blank `blank`.
Panel {
blank: usize,
panel: usize,
},
/// A hole of a blank.
Hole,
Outside,
}
/// A piece of crease between two panels of one blank.
struct HingePiece {
path: PathData,
lines: Vec<usize>,
}
/// A hinge piece by the (blank, panel, panel) it lies between.
type PlacedPiece = ((usize, usize, usize), HingePiece);
struct Context<'a> {
lines: &'a [FoldLine],
pieces: &'a [Piece],
/// The fold line of each input of the Cut lines' map, in order; the gap lines come after them.
cut_lines: &'a [usize],
material: &'a Material,
full: &'a Adjacency,
tolerance: f64,
}
impl Context<'_> {
/// The fold line that input `i` of the full map is part of; `None` for the gap lines.
fn line_of(&self, i: usize) -> Option<usize> {
self.pieces.get(i).map(|p| p.line)
}
fn kind_of(&self, i: usize) -> LineKind {
self.line_of(i).and_then(|l| self.lines.get(l)).map_or(LineKind::Cut, |l| l.kind)
}
fn key(&self, line: usize) -> u64 {
self.lines.get(line).map_or(0, |l| l.key)
}
fn keys(&self, lines: impl IntoIterator<Item = usize>) -> Vec<u64> {
lines.into_iter().map(|l| self.key(l)).collect()
}
fn build(&self, issues: &mut Vec<Issue>) -> Vec<Blank> {
let mut blanks: Vec<Blank> = vec![Blank::default(); self.material.blanks.len()];
// Hole faces that share an edge are one hole (a cut line across a window splits it in two
// faces): they are grouped, and each group's faces are united.
let m = self.material;
let is_hole = |f: usize| m.hole.get(f) == Some(&true);
let mut group: Vec<usize> = (0..m.map.faces.len()).collect();
let root = |group: &mut Vec<usize>, mut f: usize| {
while let Some(&g) = group.get(f) {
if g == f {
break;
}
let up = group.get(g).copied().unwrap_or(g);
if let Some(slot) = group.get_mut(f) {
*slot = up;
}
f = up;
}
f
};
for e in &m.map.edges {
if let (Some(a), Some(b)) = (e.left, e.right)
&& a != b
&& is_hole(a)
&& is_hole(b)
{
let (ra, rb) = (root(&mut group, a), root(&mut group, b));
if let Some(slot) = group.get_mut(ra) {
*slot = rb;
}
}
}
let mut by_group: HashMap<usize, Vec<usize>> = HashMap::new();
for f in (0..m.map.faces.len()).filter(|&f| is_hole(f)) {
by_group.entry(root(&mut group, f)).or_default().push(f);
}
let mut groups: Vec<Vec<usize>> = by_group.into_values().collect();
groups.sort_unstable();
for faces in groups {
let Some(b) = faces.first().and_then(|&f| m.blank_of(f)).and_then(|b| blanks.get_mut(b)) else { continue };
let paths: Vec<&PathData> = faces.iter().filter_map(|&f| m.map.faces.get(f).map(|x| &x.path)).collect();
let hole = match paths.as_slice() {
[one] => (*one).clone(),
_ => unite_all(&paths.iter().map(|p| (*p, FillRule::NonZero)).collect::<Vec<_>>()),
};
b.holes.push(hole);
}
let places = self.places(&mut blanks);
if blanks.iter().any(|b| b.panels.len() > MAX_PANELS) {
issues.push(Issue::new(IssueCode::TooComplex, vec![], None));
return vec![];
}
let (pieces, outside) = self.edges(&places, issues);
let hinged = self.hinges(&mut blanks, pieces, issues);
self.creases(&places, &hinged, &outside, issues);
self.slivers(issues);
self.nested(issues);
self.loose_panels(&blanks, &places, issues);
blanks
}
/// What each face of the full map is, adding the panels to `blanks`.
fn places(&self, blanks: &mut [Blank]) -> Vec<Place> {
self.full
.faces
.iter()
.map(|face| {
let Some(c) = point_in(&face.path).and_then(|p| self.material.face_at(p)) else { return Place::Outside };
let Some(blank) = self.material.blank_of(c) else { return Place::Outside };
if self.material.material.get(c) == Some(&true) {
let Some(b) = blanks.get_mut(blank) else { return Place::Outside };
b.panels.push(Panel { outline: face.path.clone(), area: face.area });
Place::Panel { blank, panel: b.panels.len() - 1 }
} else if self.material.hole.get(c) == Some(&true) {
Place::Hole
} else {
Place::Outside
}
})
.collect()
}
fn place(&self, places: &[Place], f: Option<usize>) -> Place {
f.and_then(|f| places.get(f)).copied().unwrap_or(Place::Outside)
}
/// Overlaps, dangling creases and creases in holes, from the full map's edges โ the hinge
/// pieces, by (blank, panel, panel), and how long each line runs outside every blank.
fn edges(&self, places: &[Place], issues: &mut Vec<Issue>) -> (Vec<PlacedPiece>, Vec<f64>) {
let mut pieces = vec![];
let mut outside = vec![0.0; self.lines.len()];
let mut seen: HashSet<(IssueCode, Vec<u64>)> = HashSet::new();
let mut report = |issues: &mut Vec<Issue>, code: IssueCode, keys: Vec<u64>| {
let issue = Issue::new(code, keys, None);
if seen.insert((code, issue.keys.clone())) {
issues.push(issue);
}
};
for e in &self.full.edges {
let cut = e.sources.iter().any(|&s| self.kind_of(s) == LineKind::Cut);
let creases: Vec<usize> = e.sources.iter().filter(|&&s| self.kind_of(s) != LineKind::Cut).filter_map(|&s| self.line_of(s)).collect();
let mut by_line: Vec<usize> = e.sources.iter().filter_map(|&s| self.line_of(s)).collect();
by_line.sort_unstable();
by_line.dedup();
if cut && !creases.is_empty() {
report(issues, IssueCode::CutOverCrease, self.keys(by_line.iter().copied()));
continue;
}
// Two subpaths on the same edge, from two lines or from one line's own subpaths (a
// compound path); the gap lines are left out. Past the check above they are all Cut lines
// or all lines that fold.
let mut drawn: Vec<usize> = e.sources.iter().copied().filter(|&s| self.line_of(s).is_some()).collect();
drawn.sort_unstable();
drawn.dedup();
if drawn.len() >= 2 {
let mut duplicates: Vec<usize> = drawn.iter().filter_map(|&s| self.line_of(s)).collect();
duplicates.sort_unstable();
duplicates.dedup();
report(issues, IssueCode::Duplicate, self.keys(duplicates));
}
if creases.is_empty() {
continue;
}
match (self.place(places, e.left), self.place(places, e.right)) {
(Place::Panel { blank, panel: a }, Place::Panel { blank: other, panel: b }) if blank == other && a != b => {
pieces.push(((blank, a.min(b), a.max(b)), HingePiece { path: e.path.clone(), lines: creases }));
}
(Place::Panel { .. }, Place::Panel { .. }) if e.left == e.right => {
report(issues, IssueCode::DanglingCrease, self.keys(creases));
}
(Place::Hole, _) | (_, Place::Hole) => report(issues, IssueCode::Ambiguous, self.keys(creases)),
_ => {
// A side with no face can also be a sliver inside a blank: the edge counts when
// its middle lies in a face of the Cut lines that is neither material nor a hole
// (a notch), or in no face and outside every blank.
let segs: Vec<PathSeg> = e.path.to_bezpath().segments().collect();
let Some(mid) = segs.get(segs.len() / 2).map(|s| s.eval(0.5)) else { continue };
let m = self.material;
let away = match m.face_at(mid) {
Some(f) => m.material.get(f) != Some(&true) && m.hole.get(f) != Some(&true),
None => !m.in_a_blank(mid),
};
if !away {
continue;
}
let length: f64 = segs.iter().map(|s| s.arclen(1e-3)).sum();
for &line in &creases {
if let Some(o) = outside.get_mut(line) {
*o += length;
}
}
}
}
}
(pieces, outside)
}
/// The hinges `pieces` make, added to `blanks` โ the lines with a hinge.
fn hinges(&self, blanks: &mut [Blank], mut pieces: Vec<PlacedPiece>, issues: &mut Vec<Issue>) -> Vec<usize> {
pieces.sort_by_key(|p| p.0);
let mut hinged = vec![];
let mut start = 0;
while start < pieces.len() {
let pair = pieces.get(start).map(|p| p.0);
let end = pieces.iter().skip(start).position(|p| Some(p.0) != pair).map_or(pieces.len(), |n| start + n);
let group: Vec<&HingePiece> = pieces.get(start..end).unwrap_or_default().iter().map(|p| &p.1).collect();
start = end;
let Some((blank, a, b)) = pair else { break };
let lines: Vec<usize> = group.iter().flat_map(|p| p.lines.iter().copied()).collect();
match self.hinge(&group, a, b) {
Some(h) => {
if !h.straight {
issues.push(Issue::new(IssueCode::NotStraight, h.keys.clone(), None));
}
hinged.extend(lines);
if let Some(bl) = blanks.get_mut(blank) {
bl.hinges.push(h);
}
}
None => issues.push(Issue::new(IssueCode::NoSplit, self.keys(lines.iter().copied()), None)),
}
}
hinged.sort_unstable();
hinged.dedup();
hinged
}
/// The hinge between panels `a` and `b` made of `group`, along its longest piece; `None` when
/// its pieces are shorter than the tolerance in all, or span less than it.
fn hinge(&self, group: &[&HingePiece], a: usize, b: usize) -> Option<Hinge> {
let chord = |p: &HingePiece| {
let sp = p.path.subpaths.first()?;
Some((sp.anchors.first()?.p, sp.anchors.last()?.p))
};
let ((p0, p1), longest) =
group.iter().filter_map(|p| Some((chord(p)?, p))).max_by(|(x, _), (y, _)| x.0.distance(x.1).total_cmp(&y.0.distance(y.1)))?;
let angle = longest.lines.iter().filter_map(|&l| self.lines.get(l)?.kind.fold_angle()).next().unwrap_or(90.0);
let len = p0.distance(p1);
// The longest piece only sets the direction; the length check is on the whole hinge below.
if len.is_nan() || len <= 1e-9 {
return None;
}
let d = (p1 - p0) / len;
// Each segment turned so the line through `p0` along `d` is the x axis: the exact bounds
// give how far it strays from the line (y) and its extent along it (x).
let turn = Affine::rotate(-d.y.atan2(d.x)) * Affine::translate(-p0.to_vec2());
let mut straight = true;
let (mut lo, mut hi) = (f64::INFINITY, f64::NEG_INFINITY);
for p in group {
for seg in p.path.to_bezpath().segments() {
let b = (turn * seg).bounding_box();
straight &= b.y0.abs() <= self.tolerance && b.y1.abs() <= self.tolerance;
lo = lo.min(b.x0);
hi = hi.max(b.x1);
}
}
// The pieces' own length, not the span from the first to the last, which takes in the gaps
// between pieces that lie apart.
let length: f64 = group.iter().map(|p| p.path.to_bezpath().segments().map(|s| s.arclen(1e-3)).sum::<f64>()).sum();
if !(lo.is_finite() && hi.is_finite()) || hi - lo < self.tolerance || length.is_nan() || length < self.tolerance {
return None;
}
let mut lines: Vec<usize> = group.iter().flat_map(|p| p.lines.iter().copied()).collect();
lines.sort_unstable();
lines.dedup();
let mut keys = self.keys(lines);
keys.sort_unstable();
keys.dedup();
Some(Hinge { a, b, from: p0 + d * lo, to: p0 + d * hi, keys, straight, angle })
}
/// Creases with no hinge: outside every blank, or dividing no two panels; and creases beside a
/// panel that run `outside` every blank (by line) for the tolerance or more.
fn creases(&self, places: &[Place], hinged: &[usize], outside: &[f64], issues: &mut Vec<Issue>) {
// A line drawn twice is still checked for where it lies.
let named: HashSet<u64> = issues
.iter()
.filter(|i| !matches!(i.code, IssueCode::LooseEnd | IssueCode::Gap | IssueCode::Duplicate))
.flat_map(|i| i.keys.iter().copied())
.collect();
// Whether each line is drawn (has a usable subpath), and whether one of its edges touches a
// panel.
let mut drawn = vec![false; self.lines.len()];
for p in self.pieces {
if let Some(d) = drawn.get_mut(p.line) {
*d = true;
}
}
let mut on_panel = vec![false; self.lines.len()];
for e in &self.full.edges {
if [e.left, e.right].into_iter().any(|f| matches!(self.place(places, f), Place::Panel { .. })) {
for line in e.sources.iter().filter_map(|&s| self.line_of(s)) {
if let Some(on) = on_panel.get_mut(line) {
*on = true;
}
}
}
}
for (line, l) in self.lines.iter().enumerate() {
if l.kind == LineKind::Cut || drawn.get(line) != Some(&true) {
continue;
}
let beside = on_panel.get(line) == Some(&true);
if hinged.binary_search(&line).is_err() && !named.contains(&l.key) {
issues.push(Issue::new(if beside { IssueCode::NoSplit } else { IssueCode::Outside }, vec![l.key], None));
}
if beside && outside.get(line).is_some_and(|&o| o >= self.tolerance) {
issues.push(Issue::new(IssueCode::Outside, vec![l.key], None));
}
}
}
/// Slivers of the full map inside a blank.
fn slivers(&self, issues: &mut Vec<Issue>) {
for s in &self.full.slivers {
let Some(p) = point_in(s) else { continue };
if self.material.in_a_blank(p) {
issues.push(Issue::new(IssueCode::Sliver, vec![], Some(p)));
}
}
}
/// Blanks that lie inside a hole of another blank.
fn nested(&self, issues: &mut Vec<Issue>) {
let m = self.material;
for (bi, &piece) in m.blanks.iter().enumerate() {
let faces = m.faces_by_piece.get(piece).map(Vec::as_slice).unwrap_or_default();
let Some(p) = faces.iter().find(|&&f| m.material.get(f) == Some(&true)).and_then(|&f| m.points.get(f).copied().flatten()) else {
continue;
};
let in_hole =
m.face_cells.near(p, 0.0).into_iter().any(|f| {
m.hole.get(f) == Some(&true) && m.blank_of(f).is_some_and(|b| b != bi) && m.outer.get(f).is_some_and(|bp| contains(bp, p))
});
if in_hole {
let edges = m.edges_by_piece.get(piece).map(Vec::as_slice).unwrap_or_default();
let lines = edges.iter().filter_map(|&e| m.map.edges.get(e)).flat_map(|e| e.sources.iter().filter_map(|&s| self.cut_lines.get(s)));
issues.push(Issue::new(IssueCode::Ambiguous, self.keys(lines.copied()), Some(p)));
}
}
}
/// Panels joined to their blank's base panel (the largest; on a tie, the one whose inside point is
/// highest on the page, then leftmost) by no chain of hinges.
fn loose_panels(&self, blanks: &[Blank], places: &[Place], issues: &mut Vec<Issue>) {
// The edges beside each panel, by (blank, panel), gathered once.
let mut beside: HashMap<(usize, usize), Vec<usize>> = HashMap::new();
for (i, e) in self.full.edges.iter().enumerate() {
for f in [e.left, e.right] {
if let Place::Panel { blank, panel } = self.place(places, f) {
let list = beside.entry((blank, panel)).or_default();
if list.last() != Some(&i) {
list.push(i);
}
}
}
}
for (bi, b) in blanks.iter().enumerate() {
let Some(base) = base_panel(&b.panels) else { continue };
let mut reached = vec![false; b.panels.len()];
let mut queue = vec![base];
if let Some(r) = reached.get_mut(base) {
*r = true;
}
while let Some(p) = queue.pop() {
for h in b.hinges.iter().filter(|h| h.a == p || h.b == p) {
let other = if h.a == p { h.b } else { h.a };
if let Some(r) = reached.get_mut(other).filter(|r| !**r) {
*r = true;
queue.push(other);
}
}
}
for (pi, panel) in b.panels.iter().enumerate().filter(|(i, _)| reached.get(*i) == Some(&false)) {
let edges = beside.get(&(bi, pi)).map(Vec::as_slice).unwrap_or_default();
let lines = edges.iter().filter_map(|&e| self.full.edges.get(e));
let keys = lines.flat_map(|e| e.sources.iter().filter_map(|&s| self.line_of(s))).map(|l| self.key(l)).collect();
issues.push(Issue::new(IssueCode::LoosePanel, keys, point_in(&panel.outline)));
}
}
}
}
/// The base panel of `panels`: the largest by area; panels whose areas differ by less than 1e-9 of
/// the larger tie, and the tie goes to the one whose inside point is highest on the page, then
/// leftmost.
pub fn base_panel(panels: &[Panel]) -> Option<usize> {
let top = panels.iter().map(|p| p.area).fold(f64::NEG_INFINITY, f64::max);
if !top.is_finite() {
return None;
}
panels
.iter()
.enumerate()
.filter(|(_, p)| top - p.area <= 1e-9 * top.abs())
.filter_map(|(i, p)| Some((i, point_in(&p.outline)?)))
.min_by(|a, b| a.1.y.total_cmp(&b.1.y).then(a.1.x.total_cmp(&b.1.x)))
.map(|(i, _)| i)
}
mod pose;
pub mod raster;
pub use pose::{Folded, FoldedHinge, FoldedPanel, MAX_POLYGON_POINTS, Pose, fold, panel_at, pick, polygon};
#[cfg(test)]
mod tests;
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.