dotloom_geometry/
edit.rs

1//! Split, trim and extend for lines, arcs, circles and line/arc polylines.
2//!
3//! Supported classes (anything else returns [`GeometryError::UnsupportedOperation`]):
4//!
5//! | operation | line | arc | circle | open polyline | closed polyline | path/polygon/rect/text |
6//! |-----------|------|-----|--------|---------------|-----------------|------------------------|
7//! | split     | yes  | yes | two points | yes       | yes (opens it)  | no |
8//! | trim      | yes  | yes | yes    | yes           | no              | no |
9//! | extend    | yes  | yes | n/a    | end segments  | n/a             | no |
10
11use core::f64::consts::TAU;
12
13use serde::{Deserialize, Serialize};
14
15use crate::{
16    Aabb, Arc, Circle, Curve, GeoResult, GeometryError, ModelTolerance, Point, Polyline, Segment, Shape,
17    intersect::intersect, normalize_angle,
18};
19
20/// Which end of an open curve.
21#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
22#[serde(rename_all = "camelCase")]
23pub enum CurveEnd {
24    /// The start point.
25    Start,
26    /// The end point.
27    End,
28}
29
30/// An open chain of line/arc pieces with a global parameter `u ∈ [0, n]`.
31#[derive(Debug, Clone)]
32struct Chain {
33    pieces: Vec<Curve>,
34    /// Original shape kind for rebuilding.
35    origin: ChainOrigin,
36}
37
38#[derive(Debug, Clone, Copy, PartialEq)]
39enum ChainOrigin {
40    Line,
41    Arc,
42    Polyline,
43}
44
45impl Chain {
46    fn from_shape(s: &Shape, op: &'static str) -> GeoResult<Self> {
47        match s {
48            Shape::Line(l) => Ok(Self { pieces: vec![Curve::Line(*l)], origin: ChainOrigin::Line }),
49            Shape::Arc(a) => Ok(Self { pieces: vec![Curve::Arc(*a)], origin: ChainOrigin::Arc }),
50            Shape::Polyline(p) if !p.closed => Ok(Self { pieces: s.curves(), origin: ChainOrigin::Polyline }),
51            other => Err(GeometryError::UnsupportedOperation { operation: op, shape: other.kind().name() }),
52        }
53    }
54
55    fn n(&self) -> f64 {
56        self.pieces.len() as f64
57    }
58
59    fn closest_u(&self, p: Point) -> f64 {
60        let mut best = (f64::INFINITY, 0.0);
61        for (i, c) in self.pieces.iter().enumerate() {
62            let (t, q) = c.closest(p);
63            let d = q.distance_sq(p);
64            if d < best.0 {
65                best = (d, i as f64 + t);
66            }
67        }
68        best.1
69    }
70
71    fn point_at_u(&self, u: f64) -> Point {
72        let (i, t) = self.split_u(u);
73        self.pieces.get(i).map_or(Point::ORIGIN, |c| c.point_at(t))
74    }
75
76    fn split_u(&self, u: f64) -> (usize, f64) {
77        let n = self.pieces.len();
78        if n == 0 {
79            return (0, 0.0);
80        }
81        let u = u.clamp(0.0, n as f64);
82        let i = (u.floor() as usize).min(n - 1);
83        (i, u - i as f64)
84    }
85
86    /// Sub-chain between global parameters.
87    fn sub(&self, u0: f64, u1: f64) -> Vec<Curve> {
88        let mut out = Vec::new();
89        let (i0, t0) = self.split_u(u0);
90        let (i1, t1) = self.split_u(u1);
91        for i in i0..=i1 {
92            let Some(c) = self.pieces.get(i) else { continue };
93            let a = if i == i0 { t0 } else { 0.0 };
94            let b = if i == i1 { t1 } else { 1.0 };
95            if b - a <= 1e-15 {
96                continue;
97            }
98            out.push(sub_curve(c, a, b));
99        }
100        out
101    }
102
103    fn rebuild(&self, pieces: Vec<Curve>) -> Option<Shape> {
104        if pieces.is_empty() {
105            return None;
106        }
107        if pieces.len() == 1
108            && let Some(c) = pieces.first()
109        {
110            match (*c, self.origin) {
111                (Curve::Line(l), ChainOrigin::Line) => return Some(Shape::Line(l)),
112                (Curve::Arc(a), ChainOrigin::Arc) => return Some(Shape::Arc(a)),
113                _ => {}
114            }
115        }
116        Some(Shape::Polyline(curves_to_polyline(&pieces)))
117    }
118}
119
120fn sub_curve(c: &Curve, a: f64, b: f64) -> Curve {
121    match *c {
122        Curve::Line(s) => Curve::Line(Segment::new(s.point_at(a), s.point_at(b))),
123        Curve::Arc(arc) => Curve::Arc(arc.subarc(a, b)),
124        Curve::Circle(ci) => Arc::new(ci.center, ci.radius, a * TAU, (b - a) * TAU).map_or(*c, Curve::Arc),
125        Curve::Cubic(cb) => Curve::Cubic(cb.subsegment(a, b)),
126    }
127}
128
129fn curves_to_polyline(pieces: &[Curve]) -> Polyline {
130    let mut points = Vec::with_capacity(pieces.len() + 1);
131    let mut bulges = Vec::with_capacity(pieces.len());
132    if let Some(f) = pieces.first() {
133        points.push(f.start());
134    }
135    for c in pieces {
136        points.push(c.end());
137        bulges.push(match c {
138            Curve::Arc(a) => a.bulge(),
139            _ => 0.0,
140        });
141    }
142    if bulges.iter().all(|b| *b == 0.0) {
143        bulges.clear();
144    }
145    Polyline { points, bulges, closed: false }
146}
147
148/// Split a shape at the point on it closest to `at`.
149///
150/// Lines, arcs and open polylines yield two shapes; a closed polyline yields one open
151/// polyline that starts and ends at the split point. Circles need two points: see
152/// [`split_circle`].
153pub fn split_at(shape: &Shape, at: Point, tol: ModelTolerance) -> GeoResult<Vec<Shape>> {
154    if let Shape::Polyline(p) = shape
155        && p.closed
156    {
157        return split_closed_polyline(shape, p, at);
158    }
159    let chain = Chain::from_shape(shape, "split")?;
160    let u = chain.closest_u(at);
161    let p = chain.point_at_u(u);
162    if p.distance(chain.point_at_u(0.0)) <= tol.at_scale(p.to_vector().length())
163        || p.distance(chain.point_at_u(chain.n())) <= tol.at_scale(p.to_vector().length())
164    {
165        return Err(GeometryError::InvalidArgument("split point coincides with an endpoint"));
166    }
167    let a = chain.rebuild(chain.sub(0.0, u));
168    let b = chain.rebuild(chain.sub(u, chain.n()));
169    Ok(a.into_iter().chain(b).collect())
170}
171
172fn split_closed_polyline(shape: &Shape, p: &Polyline, at: Point) -> GeoResult<Vec<Shape>> {
173    let pieces = shape.curves();
174    if pieces.is_empty() {
175        return Err(GeometryError::Degenerate("empty polyline"));
176    }
177    let chain = Chain { pieces, origin: ChainOrigin::Polyline };
178    let u = chain.closest_u(at);
179    let mut curves = chain.sub(u, chain.n());
180    curves.extend(chain.sub(0.0, u));
181    let _ = p;
182    Ok(vec![Shape::Polyline(curves_to_polyline(&curves))])
183}
184
185/// Split a circle into two arcs at the points closest to `a` and `b`.
186pub fn split_circle(c: Circle, a: Point, b: Point, tol: ModelTolerance) -> GeoResult<[Arc; 2]> {
187    let (aa, pa) = c.closest(a);
188    let (ab, pb) = c.closest(b);
189    if pa.distance(pb) <= tol.at_scale(c.radius) {
190        return Err(GeometryError::InvalidArgument("split points coincide"));
191    }
192    let s1 = normalize_angle(ab - aa);
193    Ok([Arc::new(c.center, c.radius, aa, s1)?, Arc::new(c.center, c.radius, ab, TAU - s1)?])
194}
195
196/// Intersection parameters of `chain` with all cutter shapes, sorted and deduplicated.
197fn cut_params(chain: &Chain, cutters: &[Shape], tol: ModelTolerance) -> Vec<f64> {
198    let mut us = Vec::new();
199    for (i, piece) in chain.pieces.iter().enumerate() {
200        for cutter in cutters {
201            for cc in cutter.curves() {
202                let r = intersect(piece, &cc, tol);
203                if r.overlap {
204                    continue;
205                }
206                for p in r.points {
207                    us.push(i as f64 + p.t_a);
208                }
209            }
210        }
211    }
212    us.sort_by(f64::total_cmp);
213    us.dedup_by(|a, b| (*a - *b).abs() < 1e-12);
214    us
215}
216
217/// Trim: remove the piece of `target` between the cutting intersections that
218/// surround `pick`. Returns the remaining pieces (possibly none).
219pub fn trim(target: &Shape, cutters: &[Shape], pick: Point, tol: ModelTolerance) -> GeoResult<Vec<Shape>> {
220    if let Shape::Circle(c) = target {
221        return trim_circle(*c, cutters, pick, tol).map(|a| vec![Shape::Arc(a)]);
222    }
223    let chain = Chain::from_shape(target, "trim")?;
224    let n = chain.n();
225    let cuts: Vec<f64> = cut_params(&chain, cutters, tol).into_iter().filter(|u| *u > 1e-9 && *u < n - 1e-9).collect();
226    if cuts.is_empty() {
227        return Err(GeometryError::NoBoundary("no cutting edge intersects the target"));
228    }
229    let up = chain.closest_u(pick);
230    let lo = cuts.iter().copied().filter(|u| *u <= up).fold(0.0, f64::max);
231    let hi = cuts.iter().copied().filter(|u| *u > up).fold(n, f64::min);
232    let mut out = Vec::new();
233    if lo > 0.0 {
234        out.extend(chain.rebuild(chain.sub(0.0, lo)));
235    }
236    if hi < n {
237        out.extend(chain.rebuild(chain.sub(hi, n)));
238    }
239    Ok(out)
240}
241
242fn trim_circle(c: Circle, cutters: &[Shape], pick: Point, tol: ModelTolerance) -> GeoResult<Arc> {
243    let curve = Curve::Circle(c);
244    let mut angles: Vec<f64> = Vec::new();
245    for cutter in cutters {
246        for cc in cutter.curves() {
247            let r = intersect(&curve, &cc, tol);
248            if !r.overlap {
249                angles.extend(r.points.iter().map(|p| normalize_angle(p.t_a * TAU)));
250            }
251        }
252    }
253    angles.sort_by(f64::total_cmp);
254    angles.dedup_by(|a, b| (*a - *b).abs() < 1e-12);
255    if angles.len() < 2 {
256        return Err(GeometryError::NoBoundary("trimming a circle needs two intersections"));
257    }
258    let (pa, _) = c.closest(pick);
259    // Gap containing the pick angle: from the last angle ≤ pa to the first > pa (cyclic).
260    let lo = angles.iter().copied().rev().find(|a| *a <= pa);
261    let hi = angles.iter().copied().find(|a| *a > pa);
262    let (gap_start, gap_end) = match (lo, hi) {
263        (Some(l), Some(h)) => (l, h),
264        _ => (angles.last().copied().unwrap_or(0.0), angles.first().copied().unwrap_or(0.0)),
265    };
266    // Keep from gap_end CCW to gap_start.
267    let sweep = normalize_angle(gap_start - gap_end);
268    Arc::new(c.center, c.radius, gap_end, if sweep == 0.0 { TAU } else { sweep })
269}
270
271/// Extend one end of a line/arc/open polyline to the nearest boundary.
272pub fn extend(target: &Shape, end: CurveEnd, boundaries: &[Shape], tol: ModelTolerance) -> GeoResult<Shape> {
273    match target {
274        Shape::Line(l) => extend_line(*l, end, boundaries, tol).map(Shape::Line),
275        Shape::Arc(a) => extend_arc(*a, end, boundaries, tol).map(Shape::Arc),
276        Shape::Polyline(p) if !p.closed && p.points.len() >= 2 => {
277            let last = p.segment_count().saturating_sub(1);
278            let idx = if end == CurveEnd::Start { 0 } else { last };
279            let seg = p.segment(idx).ok_or(GeometryError::Degenerate("polyline segment"))?;
280            let mut q = p.clone();
281            match seg {
282                Curve::Line(l) => {
283                    let e = extend_line(l, end, boundaries, tol)?;
284                    if end == CurveEnd::Start {
285                        if let Some(f) = q.points.first_mut() {
286                            *f = e.a;
287                        }
288                    } else if let Some(l) = q.points.last_mut() {
289                        *l = e.b;
290                    }
291                }
292                Curve::Arc(a) => {
293                    let e = extend_arc(a, end, boundaries, tol)?;
294                    if let Some(b) = q.bulges.get_mut(idx) {
295                        *b = e.bulge();
296                    }
297                    if end == CurveEnd::Start {
298                        if let Some(f) = q.points.first_mut() {
299                            *f = e.start_point();
300                        }
301                    } else if let Some(l) = q.points.last_mut() {
302                        *l = e.end_point();
303                    }
304                }
305                _ => {
306                    return Err(GeometryError::UnsupportedOperation { operation: "extend", shape: "polyline segment" });
307                }
308            }
309            Ok(Shape::Polyline(q))
310        }
311        other => Err(GeometryError::UnsupportedOperation { operation: "extend", shape: other.kind().name() }),
312    }
313}
314
315fn reach(target: Aabb, boundaries: &[Shape]) -> f64 {
316    let all = boundaries.iter().fold(target, |b, s| b.union(s.bbox()));
317    all.size().length() * 2.0 + 1.0
318}
319
320fn extend_line(l: Segment, end: CurveEnd, boundaries: &[Shape], tol: ModelTolerance) -> GeoResult<Segment> {
321    let dir = l.direction().ok_or(GeometryError::Degenerate("zero-length line"))?;
322    let (from, dir) = match end {
323        CurveEnd::End => (l.b, dir),
324        CurveEnd::Start => (l.a, -dir),
325    };
326    let far = from + dir * reach(l.bbox(), boundaries);
327    let ray = Curve::Line(Segment::new(from, far));
328    let min_t = tol.at_scale(from.to_vector().length()) / from.distance(far).max(f64::MIN_POSITIVE);
329    let mut best: Option<(f64, Point)> = None;
330    for b in boundaries {
331        for bc in b.curves() {
332            for p in intersect(&ray, &bc, tol).points {
333                if p.t_a > min_t && best.is_none_or(|(t, _)| p.t_a < t) {
334                    best = Some((p.t_a, p.point));
335                }
336            }
337        }
338    }
339    let (_, p) = best.ok_or(GeometryError::NoBoundary("no boundary in the extension direction"))?;
340    Ok(match end {
341        CurveEnd::End => Segment::new(l.a, p),
342        CurveEnd::Start => Segment::new(p, l.b),
343    })
344}
345
346fn extend_arc(a: Arc, end: CurveEnd, boundaries: &[Shape], tol: ModelTolerance) -> GeoResult<Arc> {
347    let circle = Curve::Circle(Circle { center: a.center, radius: a.radius });
348    let dirsign = a.sweep.signum();
349    let end_angle = match end {
350        CurveEnd::End => a.end_angle(),
351        CurveEnd::Start => a.start,
352    };
353    let max_extra = TAU - a.sweep.abs();
354    let eps = tol.at_scale(a.radius) / a.radius;
355    let mut best: Option<f64> = None;
356    for b in boundaries {
357        for bc in b.curves() {
358            let r = intersect(&circle, &bc, tol);
359            if r.overlap {
360                continue;
361            }
362            for p in r.points {
363                let ang = p.t_a * TAU;
364                // Angular distance travelled beyond the end in the extension direction.
365                let extra = match end {
366                    CurveEnd::End => normalize_angle((ang - end_angle) * dirsign),
367                    CurveEnd::Start => normalize_angle((end_angle - ang) * dirsign),
368                };
369                if extra > eps && extra < max_extra - eps && best.is_none_or(|e| extra < e) {
370                    best = Some(extra);
371                }
372            }
373        }
374    }
375    let extra = best.ok_or(GeometryError::NoBoundary("no boundary along the arc"))?;
376    Ok(match end {
377        CurveEnd::End => Arc { sweep: a.sweep + dirsign * extra, ..a },
378        CurveEnd::Start => Arc { start: a.start - dirsign * extra, sweep: a.sweep + dirsign * extra, ..a },
379    })
380}
381
382#[cfg(test)]
383mod tests {
384    use super::*;
385    use core::f64::consts::PI;
386
387    fn tol() -> ModelTolerance {
388        ModelTolerance::DEFAULT
389    }
390
391    fn line(ax: f64, ay: f64, bx: f64, by: f64) -> Shape {
392        Shape::Line(Segment::new(Point::new(ax, ay), Point::new(bx, by)))
393    }
394
395    #[test]
396    fn split_line() {
397        let parts = split_at(&line(0.0, 0.0, 10.0, 0.0), Point::new(4.0, 1.0), tol()).unwrap();
398        assert_eq!(parts, vec![line(0.0, 0.0, 4.0, 0.0), line(4.0, 0.0, 10.0, 0.0)]);
399        assert!(split_at(&line(0.0, 0.0, 10.0, 0.0), Point::new(0.0, 0.0), tol()).is_err());
400    }
401
402    #[test]
403    fn split_arc_keeps_circle() {
404        let a = Shape::Arc(Arc::new(Point::ORIGIN, 2.0, 0.0, PI).unwrap());
405        let parts = split_at(&a, Point::new(0.0, 5.0), tol()).unwrap();
406        assert_eq!(parts.len(), 2);
407        for p in &parts {
408            let Shape::Arc(x) = p else { unreachable!() };
409            assert!((x.radius - 2.0).abs() < 1e-12);
410            assert!((x.sweep - PI / 2.0).abs() < 1e-12);
411        }
412    }
413
414    #[test]
415    fn trim_middle_of_line() {
416        let target = line(0.0, 0.0, 10.0, 0.0);
417        let cutters = [line(3.0, -1.0, 3.0, 1.0), line(7.0, -1.0, 7.0, 1.0)];
418        let r = trim(&target, &cutters, Point::new(5.0, 0.2), tol()).unwrap();
419        assert_eq!(r, vec![line(0.0, 0.0, 3.0, 0.0), line(7.0, 0.0, 10.0, 0.0)]);
420        let end = trim(&target, &cutters, Point::new(9.0, 0.0), tol()).unwrap();
421        assert_eq!(end, vec![line(0.0, 0.0, 7.0, 0.0)]);
422        assert!(matches!(
423            trim(&target, &[line(20.0, -1.0, 20.0, 1.0)], Point::new(5.0, 0.0), tol()),
424            Err(GeometryError::NoBoundary(_))
425        ));
426    }
427
428    #[test]
429    fn trim_circle_between_two_lines() {
430        let c = Shape::Circle(Circle::new(Point::ORIGIN, 1.0).unwrap());
431        let cutter = line(-2.0, 0.0, 2.0, 0.0);
432        let r = trim(&c, &[cutter], Point::new(0.0, 1.0), tol()).unwrap();
433        let Shape::Arc(a) = &r[0] else { unreachable!() };
434        // Upper half removed: lower half remains.
435        assert!(a.mid_point().distance(Point::new(0.0, -1.0)) < 1e-9);
436        assert!((a.sweep.abs() - PI).abs() < 1e-9);
437    }
438
439    #[test]
440    fn extend_line_to_boundary() {
441        let l = line(0.0, 0.0, 2.0, 0.0);
442        let close = |s: &Shape, ax: f64, bx: f64| {
443            let Shape::Line(l) = s else { return false };
444            l.a.distance(Point::new(ax, 0.0)) < 1e-12 && l.b.distance(Point::new(bx, 0.0)) < 1e-12
445        };
446        let r = extend(&l, CurveEnd::End, &[line(5.0, -1.0, 5.0, 1.0)], tol()).unwrap();
447        assert!(close(&r, 0.0, 5.0), "{r:?}");
448        let r2 = extend(&l, CurveEnd::Start, &[line(-3.0, -1.0, -3.0, 1.0), line(5.0, -1.0, 5.0, 1.0)], tol()).unwrap();
449        assert!(close(&r2, -3.0, 2.0), "{r2:?}");
450        assert!(extend(&l, CurveEnd::End, &[line(-3.0, -1.0, -3.0, 1.0)], tol()).is_err());
451    }
452
453    #[test]
454    fn extend_arc_to_line() {
455        let a = Shape::Arc(Arc::new(Point::ORIGIN, 1.0, 0.0, PI / 4.0).unwrap());
456        let r = extend(&a, CurveEnd::End, &[line(0.0, 0.0, 0.0, 3.0)], tol()).unwrap();
457        let Shape::Arc(x) = r else { unreachable!() };
458        assert!((x.sweep - PI / 2.0).abs() < 1e-9);
459    }
460
461    #[test]
462    fn polyline_trim_and_split() {
463        let pl =
464            Shape::Polyline(Polyline::open(vec![Point::new(0.0, 0.0), Point::new(10.0, 0.0), Point::new(10.0, 10.0)]));
465        let parts = split_at(&pl, Point::new(10.0, 5.0), tol()).unwrap();
466        assert_eq!(parts.len(), 2);
467        let Shape::Polyline(first) = &parts[0] else { unreachable!() };
468        assert_eq!(first.points.last().copied(), Some(Point::new(10.0, 5.0)));
469        let r = trim(&pl, &[line(5.0, -1.0, 5.0, 1.0)], Point::new(1.0, 0.0), tol()).unwrap();
470        assert_eq!(r.len(), 1);
471        let Shape::Polyline(rest) = &r[0] else { unreachable!() };
472        assert_eq!(rest.points.first().copied(), Some(Point::new(5.0, 0.0)));
473    }
474
475    #[test]
476    fn closed_polyline_split_opens_it() {
477        let sq = Shape::Polyline(Polyline::closed(vec![
478            Point::new(0.0, 0.0),
479            Point::new(1.0, 0.0),
480            Point::new(1.0, 1.0),
481            Point::new(0.0, 1.0),
482        ]));
483        let r = split_at(&sq, Point::new(0.5, 0.0), tol()).unwrap();
484        let Shape::Polyline(p) = &r[0] else { unreachable!() };
485        assert!(!p.closed);
486        assert_eq!(p.points.first(), p.points.last());
487        assert!((r[0].length() - 4.0).abs() < 1e-12);
488    }
489
490    #[test]
491    fn unsupported_classes_report_capability_errors() {
492        let rect = Shape::Rect(crate::Rect { origin: Point::ORIGIN, width: 1.0, height: 1.0 });
493        assert!(matches!(split_at(&rect, Point::ORIGIN, tol()), Err(GeometryError::UnsupportedOperation { .. })));
494    }
495}
dotloom_geometry/edit.rs

dotloom_geometry/
edit.rs
