a770fa5a5e5f
loops.rs
//! LOOPS: implied closed loops from loose LINE and ARC chains — perimeter, area and winding for
//! each closed loop, the gap and its location for each open chain, and branch junctions (three or
//! more ends meeting) reported but not resolved. Read-only.
//!
//! Boundaries are often drawn as separate LINEs and ARCs rather than one polyline, so an agent
//! cannot tell whether they form a closed loop or by how much a "closed" outline is open. The
//! endpoint chaining is quadratic in the number of endpoints; past `maxPairs` it reports `capped`
//! and analyzes nothing rather than guess from a partial pairing.
use std::collections::{BTreeMap, BTreeSet};
use cadcraft_doc::{EntityKind, Handle};
use cadcraft_geom::{Arc as GeoArc, EPS, Vec2};
use serde_json::{Value, json};
use super::super::bad;
use crate::{Result, Session};
const CMD: &str = "loops";
/// Endpoint pairs compared before the quadratic chaining gives up (reported as `capped`).
const DEFAULT_PAIR_LIMIT: usize = 1_000_000;
/// The most pairs a caller may ask for: a bounded amount of work however large the drawing.
const MAX_PAIR_LIMIT: usize = 100_000_000;
/// Loops returned, and open chains and junctions kept, by default.
const DEFAULT_LIMIT: usize = 200;
/// The smallest default tolerance, for a drawing at the origin.
const MIN_TOLERANCE: f64 = 1e-12;
pub const PARAMS: &str = "{tolerance?: positive number (default 1e-9 × the extents diagonal), maxPairs? (endpoint pairs compared, default 1000000, at most 100000000), limit? (default 200), offset?} → \
{schema: 1, tolerance, pairTests, pairTestsNeeded, pairLimit, capped, count (all closed loops), returned, offset, truncated, \
loops: [{members: [handle], perimeter, area, winding: ccw|cw}], \
openChains: {count, truncated, chains: [{members, gap, at: [x, y], ends: [[x, y], [x, y]], length}]}, \
junctions: {count, truncated, junctions: [{at: [x, y], ends, members}]}, skipped: {<type>: {count, reason}}}: \
chains LINE and ARC endpoints that meet within the tolerance; junctions (three or more ends meeting) are reported, not resolved";
/// Why a LINE or ARC cannot take part in a chain.
type Skipped = BTreeMap<&'static str, (usize, BTreeSet<&'static str>)>;
/// One chainable entity, oriented as drawn (a line a→b, an arc CCW start→end).
struct Piece {
handle: Handle,
start: Vec2,
end: Vec2,
/// The arc, when the piece is one.
arc: Option<GeoArc>,
}
impl Piece {
fn at(&self, which: usize) -> Vec2 {
if which == 0 { self.start } else { self.end }
}
fn length(&self) -> f64 {
match self.arc {
Some(a) => a.radius * a.sweep(),
None => self.start.dist(self.end),
}
}
}
/// An entity endpoint in the chain graph. Each piece has one at index `2 * piece` and one at
/// `2 * piece + 1`.
#[derive(Clone, Copy)]
struct End {
piece: usize,
at: Vec2,
}
/// A piece traversed one way round a chain.
struct Traversed {
start: Vec2,
end: Vec2,
/// The arc and whether the traversal follows its CCW direction.
arc: Option<(GeoArc, bool)>,
}
pub fn run(s: &mut Session, p: &Value) -> Result<Value> {
let given = |k: &str| p.get(k).filter(|v| !v.is_null());
let count = |k: &str, default: usize| -> Result<usize> {
given(k).map_or(Ok(default), |v| {
v.as_u64().map(|n| usize::try_from(n).unwrap_or(usize::MAX)).ok_or_else(|| bad(CMD, format!("`{k}` must be a whole number, 0 or more")))
})
};
let limit = count("limit", DEFAULT_LIMIT)?;
let offset = count("offset", 0)?;
let pair_limit = count("maxPairs", DEFAULT_PAIR_LIMIT)?.min(MAX_PAIR_LIMIT);
let tolerance = given("tolerance")
.map(|v| v.as_f64().filter(|t| t.is_finite() && *t > 0.0).ok_or_else(|| bad(CMD, "`tolerance` must be a positive number")))
.transpose()?;
let s: &Session = s;
let st = s.state()?;
let d = &st.doc;
let tol = tolerance.unwrap_or_else(|| {
let ext = d.extents(&st.space);
if ext.is_empty() {
return MIN_TOLERANCE;
}
let diag = ext.min.dist(ext.max);
if diag.is_finite() { (diag * 1e-9).max(MIN_TOLERANCE) } else { MIN_TOLERANCE }
});
let mut skipped: Skipped = BTreeMap::new();
let Some(store) = d.space(&st.space) else {
return Ok(empty_report(offset, tol, 0, 0, pair_limit, false, skipped));
};
let pieces: Vec<Piece> = store.iter().filter_map(|e| chainable(e.handle, &e.kind, &mut skipped)).collect();
let mut ends: Vec<End> = Vec::with_capacity(pieces.len().saturating_mul(2));
for (i, piece) in pieces.iter().enumerate() {
ends.push(End { piece: i, at: piece.start });
ends.push(End { piece: i, at: piece.end });
}
let n = ends.len();
let needed = n.saturating_mul(n.saturating_sub(1)) / 2;
if needed > pair_limit {
return Ok(empty_report(offset, tol, 0, needed, pair_limit, true, skipped));
}
// Endpoints closer than the tolerance meet. Transitive components of three or more ends are
// branch junctions; a component of exactly two is a simple joint.
let mut parent = merge_ends(&ends, tol);
let mut groups: BTreeMap<usize, Vec<usize>> = BTreeMap::new();
for i in 0..n {
let root = find(&mut parent, i);
groups.entry(root).or_default().push(i);
}
// Junctions are reported and their pieces left out of the chains: not resolved.
let mut excluded = vec![false; pieces.len()];
let (joints, junctions) = sort_groups(&groups, &ends, &pieces, &mut excluded);
let link = joint_links(joints, &ends, &pieces, &excluded);
let mut visited = vec![false; pieces.len()];
let mut loops: Vec<Value> = Vec::new();
let mut open: Vec<Value> = Vec::new();
// Paths first: a free end marks a chain. What is left with both ends linked is a cycle.
open_chains(&pieces, &excluded, &link, &mut visited, &mut open);
closed_loops(&pieces, &excluded, &link, &mut visited, &mut loops);
let total = loops.len();
let page: Vec<Value> = loops.into_iter().skip(offset).take(limit).collect();
let returned = page.len();
let truncated = returned < total.saturating_sub(offset);
let open_total = open.len();
let open_page: Vec<Value> = open.into_iter().take(limit).collect();
let open_truncated = open_page.len() < open_total;
let junction_total = junctions.len();
let junction_page: Vec<Value> = junctions.into_iter().take(limit).collect();
let junction_truncated = junction_page.len() < junction_total;
Ok(json!({
"schema": 1,
"tolerance": tol,
"pairTests": needed,
"pairTestsNeeded": needed,
"pairLimit": pair_limit,
"capped": false,
"count": total,
"returned": returned,
"offset": offset,
"truncated": truncated,
"loops": page,
"openChains": { "count": open_total, "truncated": open_truncated, "chains": open_page },
"junctions": { "count": junction_total, "truncated": junction_truncated, "junctions": junction_page },
"skipped": skipped_json(skipped),
}))
}
/// A report with nothing analyzed: an empty drawing, or one past the pair cap.
/// Union-find over the ends: ends closer than `tol` share a root. Returns each end's parent.
fn merge_ends(ends: &[End], tol: f64) -> Vec<usize> {
let n = ends.len();
let mut parent: Vec<usize> = (0..n).collect();
for i in 0..n {
let Some(a) = ends.get(i) else { continue };
for j in (i + 1)..n {
let Some(b) = ends.get(j) else { continue };
if a.at.dist(b.at) <= tol {
let (ra, rb) = (find(&mut parent, i), find(&mut parent, j));
if ra != rb
&& let Some(slot) = parent.get_mut(ra)
{
*slot = rb;
}
}
}
}
parent
}
/// Each group of two ends is a joint (end indices); each of three or more is a junction, reported
/// with its pieces marked `excluded`.
fn sort_groups(groups: &BTreeMap<usize, Vec<usize>>, ends: &[End], pieces: &[Piece], excluded: &mut [bool]) -> (Vec<(usize, usize)>, Vec<Value>) {
let mut joints: Vec<(usize, usize)> = Vec::new();
let mut junctions: Vec<Value> = Vec::new();
for group in groups.values() {
match group.as_slice() {
&[a, b] => joints.push((a, b)),
[_, _, ..] => {
let scale = group.len() as f64;
let mut at = Vec2::ZERO;
let mut members: Vec<Handle> = Vec::new();
for &e in group {
let Some(end) = ends.get(e) else { continue };
at += end.at / scale;
let Some(piece) = pieces.get(end.piece) else { continue };
if !members.contains(&piece.handle) {
members.push(piece.handle);
}
if let Some(slot) = excluded.get_mut(end.piece) {
*slot = true;
}
}
junctions.push(json!({
"at": [at.x, at.y],
"ends": group.len(),
"members": members.iter().map(|h| h.hex()).collect::<Vec<_>>(),
}));
}
_ => {}
}
}
(joints, junctions)
}
/// The link each end takes from the joints. A joint into an excluded piece is not a link, and
/// a line whose own ends meet within a huge tolerance is a spur, not a zero-area loop.
fn joint_links(joints: Vec<(usize, usize)>, ends: &[End], pieces: &[Piece], excluded: &[bool]) -> Vec<Option<usize>> {
let mut link: Vec<Option<usize>> = vec![None; ends.len()];
for (a, b) in joints {
let (Some(ea), Some(eb)) = (ends.get(a), ends.get(b)) else { continue };
if ea.piece == eb.piece && pieces.get(ea.piece).is_some_and(|p| p.arc.is_none()) {
continue;
}
if excluded.get(ea.piece).copied().unwrap_or(true) || excluded.get(eb.piece).copied().unwrap_or(true) {
continue;
}
if let Some(slot) = link.get_mut(a) {
*slot = Some(b);
}
if let Some(slot) = link.get_mut(b) {
*slot = Some(a);
}
}
link
}
fn empty_report(offset: usize, tol: f64, pair_tests: usize, pair_tests_needed: usize, pair_limit: usize, capped: bool, skipped: Skipped) -> Value {
json!({
"schema": 1,
"tolerance": tol,
"pairTests": pair_tests,
"pairTestsNeeded": pair_tests_needed,
"pairLimit": pair_limit,
"capped": capped,
"count": 0,
"returned": 0,
"offset": offset,
"truncated": false,
"loops": [],
"openChains": { "count": 0, "truncated": false, "chains": [] },
"junctions": { "count": 0, "truncated": false, "junctions": [] },
"skipped": skipped_json(skipped),
})
}
fn skipped_json(skipped: Skipped) -> Value {
let m: BTreeMap<&str, Value> =
skipped.into_iter().map(|(k, (n, why))| (k, json!({ "count": n, "reason": why.into_iter().collect::<Vec<_>>().join("; ") }))).collect();
json!(m)
}
fn skip(skipped: &mut Skipped, ty: &'static str, why: &'static str) {
let entry = skipped.entry(ty).or_default();
entry.0 += 1;
entry.1.insert(why);
}
/// The piece for a LINE or ARC, or `None` when the entity is not chainable.
fn chainable(handle: Handle, kind: &EntityKind, skipped: &mut Skipped) -> Option<Piece> {
match kind {
EntityKind::Line(l) => {
let (a, b) = (l.a.xy(), l.b.xy());
if !a.is_finite() || !b.is_finite() || a.dist(b) <= EPS {
skip(skipped, "Line", "zero length");
return None;
}
Some(Piece { handle, start: a, end: b, arc: None })
}
EntityKind::Arc(a) => {
let (c, r) = (a.center.xy(), a.radius.abs());
if !c.is_finite() || !a.radius.is_finite() || r <= EPS || !a.start.is_finite() || !a.end.is_finite() {
skip(skipped, "Arc", "degenerate");
return None;
}
let arc = GeoArc::new(c, r, a.start, a.end);
let (start, end) = (arc.start_point(), arc.end_point());
if !start.is_finite() || !end.is_finite() {
skip(skipped, "Arc", "degenerate");
return None;
}
Some(Piece { handle, start, end, arc: Some(arc) })
}
_ => None,
}
}
fn find(parent: &mut [usize], mut x: usize) -> usize {
while let Some(&p) = parent.get(x) {
if p == x {
return x;
}
let gp = parent.get(p).copied().unwrap_or(p);
if let Some(slot) = parent.get_mut(x) {
*slot = gp;
}
x = gp;
}
x
}
/// Walk the cycles left after the open paths from a free end, and report their geometry.
fn closed_loops(pieces: &[Piece], excluded: &[bool], link: &[Option<usize>], visited: &mut [bool], out: &mut Vec<Value>) {
for i in 0..pieces.len() {
if visited.get(i).copied().unwrap_or(true) || excluded.get(i).copied().unwrap_or(true) {
continue;
}
// Only a piece linked at both ends can be in a cycle.
if link.get(i * 2).copied().flatten().is_none() || link.get(i * 2 + 1).copied().flatten().is_none() {
continue;
}
let mut members: Vec<usize> = Vec::new();
let mut forward: Vec<bool> = Vec::new();
let (mut cur, mut entry) = (i, 0usize);
let mut closed = false;
loop {
if visited.get(cur).copied().unwrap_or(true) || members.len() >= pieces.len() {
break;
}
if let Some(slot) = visited.get_mut(cur) {
*slot = true;
}
members.push(cur);
forward.push(entry == 0);
let exit = 1 - entry;
let Some(q) = link.get(cur * 2 + exit).copied().flatten() else { break };
let (next, which) = (q / 2, q % 2);
if next == i && which == 0 {
closed = true;
break;
}
if visited.get(next).copied().unwrap_or(true) {
break;
}
cur = next;
entry = which;
}
if !closed || members.is_empty() {
continue;
}
let segs = traversed(pieces, &members, &forward);
let (perimeter, area, signed) = facts(&segs);
out.push(json!({
"members": members.iter().filter_map(|&m| pieces.get(m)).map(|p| p.handle.hex()).collect::<Vec<_>>(),
"perimeter": perimeter,
"area": area,
"winding": if signed < 0.0 { "cw" } else { "ccw" },
}));
}
}
/// Walk paths from every free end: an open chain, with the gap between its two ends.
fn open_chains(pieces: &[Piece], excluded: &[bool], link: &[Option<usize>], visited: &mut [bool], out: &mut Vec<Value>) {
for i in 0..pieces.len() {
if visited.get(i).copied().unwrap_or(true) || excluded.get(i).copied().unwrap_or(true) {
continue;
}
let Some(entry0) = [0usize, 1].into_iter().find(|w| link.get(i * 2 + w).copied().flatten().is_none()) else { continue };
let mut members: Vec<usize> = Vec::new();
let mut forward: Vec<bool> = Vec::new();
let (mut cur, mut entry) = (i, entry0);
let mut exit = entry0;
loop {
if visited.get(cur).copied().unwrap_or(true) || members.len() >= pieces.len() {
break;
}
if let Some(slot) = visited.get_mut(cur) {
*slot = true;
}
members.push(cur);
forward.push(entry == 0);
exit = 1 - entry;
let Some(q) = link.get(cur * 2 + exit).copied().flatten() else { break };
let (next, which) = (q / 2, q % 2);
if visited.get(next).copied().unwrap_or(true) {
break;
}
cur = next;
entry = which;
}
let (Some(first_piece), Some(last_piece)) = (pieces.get(i), members.last().and_then(|&m| pieces.get(m))) else { continue };
let (first, last) = (first_piece.at(entry0), last_piece.at(exit));
let gap = first.dist(last);
let at = first * 0.5 + last * 0.5;
let length: f64 = members.iter().filter_map(|&m| pieces.get(m)).map(Piece::length).sum();
out.push(json!({
"members": members.iter().filter_map(|&m| pieces.get(m)).map(|p| p.handle.hex()).collect::<Vec<_>>(),
"gap": gap,
"at": [at.x, at.y],
"ends": [[first.x, first.y], [last.x, last.y]],
"length": length,
}));
}
}
fn traversed(pieces: &[Piece], members: &[usize], forward: &[bool]) -> Vec<Traversed> {
members
.iter()
.zip(forward)
.filter_map(|(&m, &fwd)| {
let p = pieces.get(m)?;
Some(Traversed { start: if fwd { p.start } else { p.end }, end: if fwd { p.end } else { p.start }, arc: p.arc.map(|a| (a, fwd)) })
})
.collect()
}
/// Perimeter, unsigned area and signed area (CCW positive, as SHAPES reports winding) of a closed
/// chain of lines and arcs. The closing chord between the last end and the first is the chain's gap
/// and counts in the perimeter, as an open polyline with matching ends does in SHAPES.
fn facts(segs: &[Traversed]) -> (f64, f64, f64) {
let Some(first) = segs.first() else { return (0.0, 0.0, 0.0) };
let perimeter: f64 = segs.iter().map(seg_len).sum::<f64>() + segs.last().map_or(0.0, |last| last.end.dist(first.start));
let signed = signed_area(segs, first.start);
(perimeter, signed.abs(), signed)
}
fn seg_len(t: &Traversed) -> f64 {
match t.arc {
Some((a, _)) => a.radius * a.sweep(),
None => t.start.dist(t.end),
}
}
/// Green's theorem over the closed path, measured about its first point so a small loop far from
/// the origin keeps its area. An arc contributes its exact circular integral, not a tessellation.
fn signed_area(segs: &[Traversed], origin: Vec2) -> f64 {
let mut twice = 0.0;
for t in segs {
match t.arc {
None => twice += (t.start - origin).cross(t.end - origin),
Some((a, forward)) => {
let sweep = a.sweep();
let (from, to, d) = if forward { (a.start, a.start + sweep, sweep) } else { (a.end, a.end - sweep, -sweep) };
let c = a.center - origin;
twice += a.radius * a.radius * d + a.radius * (c.x * (to.sin() - from.sin()) - c.y * (to.cos() - from.cos()));
}
}
}
twice / 2.0
}
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.