geop_core_sketch/

sketch.rs

//! Sketch entities and constraints: design data, in any [`Scalar`] — the
//! values a file holds, read as sharp scalars and written as their
//! midpoints.
//!
//! Points are the only entities with positions of their own; lines, arcs and
//! splines reference points by [`PointId`], so two curves that share an
//! endpoint share the *same* point and stay connected by construction.
//! Separately drawn points are joined with [`Constraint::Coincident`], which
//! the solver treats the same way (the two points become one set of
//! variables), so connectivity is always structural — never inferred from
//! two positions happening to be close.
//!
//! A point or curve can be *fixed*: given from outside the sketch rather
//! than solved for — the sketch's own origin and axes, or an edge of the
//! part projected into its plane. The solver never moves it, and every
//! constraint on it is measured against it as it is.

use std::collections::{BTreeMap, BTreeSet};

use geop_core_math::{
    geop_error::{GeopError, GeopResult},
    scalars::{Scalar, as_f64},
    union_find::UnionFind,
    vector::Vector2,
};

use serde::{Deserialize, Serialize};

macro_rules! define_ids {
    ($($(#[$doc:meta])* $name:ident => $prefix:literal),* $(,)?) => {
        $(
            $(#[$doc])*
            #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord, Serialize)]
            #[serde(transparent)]
            pub struct $name(pub u64);

            /// The id as it appears in a topological name, e.g. `p3`.
            impl std::fmt::Display for $name {
                fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
                    write!(f, concat!($prefix, "{}"), self.0)
                }
            }

            /// The id as [`std::fmt::Display`] writes it, `p3`, read back.
            impl std::str::FromStr for $name {
                type Err = GeopError;

                fn from_str(text: &str) -> GeopResult<Self> {
                    (text.strip_prefix($prefix))
                        .and_then(|id| id.parse().ok())
                        .map($name)
                        .ok_or_else(|| {
                            GeopError::new(format!(concat!("{:?} is no id `", $prefix, "<n>`"), text))
                        })
                }
            }

            impl<'de> Deserialize<'de> for $name {
                fn deserialize<D: serde::Deserializer<'de>>(d: D) -> Result<Self, D::Error> {
                    d.deserialize_any(IdVisitor).map($name)
                }
            }
        )*
    };
}

/// Reads an id from a number, or from the string a JSON object key holds it
/// as. Serde's derived `u64` accepts the key string only when it knows the
/// target type up front, not when the map was first buffered — as it is
/// inside a `#[serde(flatten)]`ed or internally tagged container, where a
/// sketch naturally ends up.
struct IdVisitor;

impl serde::de::Visitor<'_> for IdVisitor {
    type Value = u64;

    fn expecting(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        f.write_str("a non-negative integer id, as a number or a string")
    }

    fn visit_u64<E: serde::de::Error>(self, v: u64) -> Result<u64, E> {
        Ok(v)
    }

    fn visit_i64<E: serde::de::Error>(self, v: i64) -> Result<u64, E> {
        u64::try_from(v).map_err(|_| E::custom(format!("id {v} is negative")))
    }

    fn visit_str<E: serde::de::Error>(self, v: &str) -> Result<u64, E> {
        v.parse()
            .map_err(|_| E::custom(format!("{v:?} is not an integer id")))
    }
}

define_ids!(
    /// Key of [`Sketch::points`].
    PointId => "p",
    /// Key of [`Sketch::curves`].
    CurveId => "c",
    /// Key of [`Sketch::constraints`].
    ConstraintId => "k",
);

pub(crate) fn is_false(b: &bool) -> bool {
    !*b
}

/// What a curve or a constraint of a sketch — planar, or a 3-D
/// [`crate::space::Sketch3d`] — refers to.
pub(crate) trait Uses {
    /// The points it refers to directly.
    fn points(&self) -> Vec<PointId>;
    /// The curves it refers to.
    fn curves(&self) -> Vec<CurveId> {
        Vec::new()
    }
    /// The two points it makes one, if it is a coincidence.
    fn coincident(&self) -> Option<(PointId, PointId)> {
        None
    }
}

/// Removes `points`, `curves` and `constraints` from a sketch whose
/// entities are `all_points`, `all_curves` and `all_constraints`, and
/// everything that depends on them: a curve on a removed point, a
/// constraint on any removed entity, and a point nothing uses any more
/// because of it — a lone point drawn on purpose stays. Everything else
/// keeps its id. Returns the curves removed.
pub(crate) fn remove<P, C: Uses, K: Uses>(
    all_points: &mut BTreeMap<PointId, P>,
    all_curves: &mut BTreeMap<CurveId, C>,
    all_constraints: &mut BTreeMap<ConstraintId, K>,
    points: &[PointId],
    curves: &[CurveId],
    constraints: &[ConstraintId],
) -> BTreeSet<CurveId> {
    let dead_curves: BTreeSet<CurveId> = all_curves
        .iter()
        .filter(|(id, c)| curves.contains(id) || c.points().iter().any(|p| points.contains(p)))
        .map(|(&id, _)| id)
        .collect();
    let dead_constraints: BTreeSet<ConstraintId> = all_constraints
        .iter()
        .filter(|(id, c)| {
            constraints.contains(id)
                || c.points().iter().any(|p| points.contains(p))
                || c.curves().iter().any(|k| dead_curves.contains(k))
        })
        .map(|(&id, _)| id)
        .collect();
    let mut used_before = BTreeSet::new();
    let mut used_after = BTreeSet::new();
    for (id, c) in all_curves.iter() {
        for p in c.points() {
            used_before.insert(p);
            if !dead_curves.contains(id) {
                used_after.insert(p);
            }
        }
    }
    for (id, c) in all_constraints.iter() {
        for p in c.points() {
            used_before.insert(p);
            if !dead_constraints.contains(id) {
                used_after.insert(p);
            }
        }
    }
    all_points.retain(|p, _| {
        let only_used_before = used_before.contains(p) && !used_after.contains(p);
        !(points.contains(p) || only_used_before)
    });
    all_curves.retain(|id, _| !dead_curves.contains(id));
    all_constraints.retain(|id, _| !dead_constraints.contains(id));
    dead_curves
}

/// Union-find representative of each of `points` under the coincidences
/// of `constraints`: points with the same representative are one point.
/// The lowest id represents its class, so the representative does not
/// depend on constraint order.
pub(crate) fn point_classes<P, K: Uses>(
    points: &BTreeMap<PointId, P>,
    constraints: &BTreeMap<ConstraintId, K>,
) -> BTreeMap<PointId, PointId> {
    let ids: Vec<PointId> = points.keys().copied().collect();
    let index: BTreeMap<PointId, usize> = ids.iter().enumerate().map(|(i, &id)| (id, i)).collect();
    // The lowest index represents a class, and the ids are in order: so
    // does the lowest id.
    let mut classes = UnionFind::new(ids.len());
    for (a, b) in constraints.values().filter_map(Uses::coincident) {
        classes.union(index[&a], index[&b]);
    }
    (ids.iter().enumerate())
        .map(|(i, &id)| (id, ids[classes.find(i)]))
        .collect()
}

#[derive(Clone, Copy, Debug, PartialEq, Serialize, Deserialize)]
pub struct Point {
    #[serde(with = "as_f64")]
    pub x: Scalar,
    #[serde(with = "as_f64")]
    pub y: Scalar,
    /// Given rather than solved for: the solver never moves it (see the
    /// module docs).
    #[serde(default, skip_serializing_if = "is_false")]
    pub fixed: bool,
}

impl Point {
    pub fn xy(&self) -> Vector2 {
        Vector2::from_array([self.x, self.y])
    }
}

#[derive(Clone, Debug, PartialEq, Serialize, Deserialize)]
#[serde(tag = "type")]
pub enum CurveKind {
    Line {
        start: PointId,
        end: PointId,
    },
    /// A circular arc from `start` to `end`, turning counter-clockwise by
    /// `sweep` radians (clockwise if negative, `|sweep| < 2π`). Equivalent to
    /// giving its curvature `2 sin(sweep / 2) / |end - start|` — see
    /// [`crate::geometry`] for why the sweep is what is stored and solved.
    Arc {
        start: PointId,
        end: PointId,
        #[serde(with = "as_f64")]
        sweep: Scalar,
    },
    Circle {
        center: PointId,
        #[serde(with = "as_f64")]
        radius: Scalar,
    },
    /// A clamped B-spline through its first and last control points: as
    /// drawn, uniform and non-rational of degree
    /// `min(3, control_points.len() - 1)`; taken from elsewhere — an edge of
    /// the part projected into the plane — any NURBS (see [`SplineShape`]).
    Spline {
        control_points: Vec<PointId>,
        #[serde(default, skip_serializing_if = "Option::is_none")]
        shape: Option<SplineShape>,
    },
    /// The outlines of `text`'s glyphs in the sketch font (see
    /// [`crate::text`]): its first baseline from `anchor` on, its capitals
    /// `height` tall, turned counter-clockwise by `angle` radians. Each of
    /// a glyph's closed contours is a loop of the profile — an `o` an
    /// outline and a hole in it. Only its anchor is solved for: a text is
    /// placed by constraining that point, and takes no constraint itself.
    Text {
        anchor: PointId,
        text: String,
        #[serde(with = "as_f64")]
        height: Scalar,
        #[serde(with = "as_f64")]
        angle: Scalar,
    },
}

/// The shape of a [`CurveKind::Spline`] beyond its control points, for one
/// that is not the uniform non-rational spline a drawn one is: its degree,
/// its clamped knot vector (`control_points + degree + 1` knots) and one
/// weight per control point.
#[derive(Clone, Debug, PartialEq, Serialize, Deserialize)]
pub struct SplineShape {
    pub degree: usize,
    #[serde(with = "as_f64::vec")]
    pub knots: Vec<Scalar>,
    #[serde(with = "as_f64::vec")]
    pub weights: Vec<Scalar>,
}

#[derive(Clone, Debug, PartialEq, Serialize, Deserialize)]
pub struct Curve {
    #[serde(flatten)]
    pub kind: CurveKind,
    /// Construction geometry takes part in constraints but not in profiles
    /// (e.g. a revolve axis or a symmetry line).
    #[serde(default)]
    pub construction: bool,
    /// Given rather than solved for, like its points, which are all fixed:
    /// an arc's sweep or a circle's radius too (see the module docs).
    #[serde(default, skip_serializing_if = "is_false")]
    pub fixed: bool,
}

impl Uses for Curve {
    fn points(&self) -> Vec<PointId> {
        Curve::points(self)
    }
}

impl Curve {
    /// The points this curve is defined by.
    pub fn points(&self) -> Vec<PointId> {
        match &self.kind {
            CurveKind::Line { start, end } | CurveKind::Arc { start, end, .. } => {
                vec![*start, *end]
            }
            CurveKind::Circle { center, .. } => vec![*center],
            CurveKind::Spline { control_points, .. } => control_points.clone(),
            CurveKind::Text { anchor, .. } => vec![*anchor],
        }
    }

    /// `(start, end)` for an open curve, `None` for a circle or a text.
    pub fn endpoints(&self) -> Option<(PointId, PointId)> {
        match &self.kind {
            CurveKind::Line { start, end } | CurveKind::Arc { start, end, .. } => {
                Some((*start, *end))
            }
            CurveKind::Circle { .. } | CurveKind::Text { .. } => None,
            CurveKind::Spline { control_points, .. } => {
                Some((control_points[0], *control_points.last()?))
            }
        }
    }
}

/// The typical CAD sketch constraints. Distances and lengths are in sketch
/// units, angles in radians.
#[derive(Clone, Debug, PartialEq, Serialize, Deserialize)]
#[serde(tag = "type")]
pub enum Constraint {
    /// `a` and `b` are the same point.
    Coincident {
        a: PointId,
        b: PointId,
    },
    /// `point` lies on `curve` (a line's infinite extension, an arc's full
    /// circle, or a circle).
    PointOnCurve {
        point: PointId,
        curve: CurveId,
    },
    Horizontal {
        line: CurveId,
    },
    Vertical {
        line: CurveId,
    },
    Parallel {
        a: CurveId,
        b: CurveId,
    },
    Perpendicular {
        a: CurveId,
        b: CurveId,
    },
    /// Two lines on one infinite line.
    Collinear {
        a: CurveId,
        b: CurveId,
    },
    /// Two curves meet tangentially: at a shared endpoint if they have one
    /// (lines, arcs and splines), else a line touching a circle/arc, or two
    /// circles/arcs touching each other.
    Tangent {
        a: CurveId,
        b: CurveId,
    },
    /// Equal length (two lines) or equal radius (two circles/arcs).
    Equal {
        a: CurveId,
        b: CurveId,
    },
    /// Two circles/arcs share a center.
    Concentric {
        a: CurveId,
        b: CurveId,
    },
    /// `point` is the center of a circle or arc.
    Center {
        point: PointId,
        curve: CurveId,
    },
    /// `point` is the midpoint of a line or arc.
    Midpoint {
        point: PointId,
        curve: CurveId,
    },
    /// `a` and `b` are mirror images across `line`.
    Symmetric {
        a: PointId,
        b: PointId,
        line: CurveId,
    },
    /// `point` stays at `(x, y)`.
    Fix {
        point: PointId,
        #[serde(with = "as_f64")]
        x: Scalar,
        #[serde(with = "as_f64")]
        y: Scalar,
    },
    Distance {
        a: PointId,
        b: PointId,
        #[serde(with = "as_f64")]
        value: Scalar,
    },
    /// `b.x - a.x = value`.
    DistanceX {
        a: PointId,
        b: PointId,
        #[serde(with = "as_f64")]
        value: Scalar,
    },
    /// `b.y - a.y = value`.
    DistanceY {
        a: PointId,
        b: PointId,
        #[serde(with = "as_f64")]
        value: Scalar,
    },
    PointLineDistance {
        point: PointId,
        line: CurveId,
        #[serde(with = "as_f64")]
        value: Scalar,
    },
    /// Length of a line or arc.
    Length {
        curve: CurveId,
        #[serde(with = "as_f64")]
        value: Scalar,
    },
    /// Radius of a circle or arc.
    Radius {
        curve: CurveId,
        #[serde(with = "as_f64")]
        value: Scalar,
    },
    /// Diameter of a circle or arc.
    Diameter {
        curve: CurveId,
        #[serde(with = "as_f64")]
        value: Scalar,
    },
    /// The counter-clockwise angle from line `a`'s direction to line `b`'s.
    Angle {
        a: CurveId,
        b: CurveId,
        #[serde(with = "as_f64")]
        value: Scalar,
    },
    /// `b` is `a` moved the way `by` carries its start onto its end: along
    /// a line, shifted by it; round an arc, turned about the arc's center
    /// by its sweep. How a pattern's copies follow what they copy (see
    /// [`crate::copies`]).
    Moved {
        a: PointId,
        b: PointId,
        by: CurveId,
    },
    /// Two arcs turn by the same angle: an arc whose ends are the images of
    /// another's, under a motion or a reflection, is then its image.
    EqualSweep {
        a: CurveId,
        b: CurveId,
    },
    /// `b` runs `value` from `a`: two parallel lines `value` apart, or two
    /// concentric circles/arcs whose radii differ by `value` (see
    /// [`crate::offset`]).
    Offset {
        a: CurveId,
        b: CurveId,
        #[serde(with = "as_f64")]
        value: Scalar,
    },
    /// The point `on` along the spline `b` lies the radius of the circle
    /// `by` from the point `at` along the spline `a`, along `a`'s normal
    /// there — or, `across`, only that far across it: anywhere on the line
    /// `a`'s offset runs along there. Each as a fraction of the spline's
    /// domain. The offset of a spline is no spline: a spline fitted through
    /// such points is held to it (see [`crate::offset`]).
    OffsetAt {
        a: CurveId,
        #[serde(with = "as_f64")]
        at: Scalar,
        b: CurveId,
        #[serde(with = "as_f64")]
        on: Scalar,
        by: CurveId,
        #[serde(default, skip_serializing_if = "is_false")]
        across: bool,
    },
}

impl Uses for Constraint {
    fn points(&self) -> Vec<PointId> {
        Constraint::points(self)
    }

    fn curves(&self) -> Vec<CurveId> {
        Constraint::curves(self)
    }

    fn coincident(&self) -> Option<(PointId, PointId)> {
        match *self {
            Constraint::Coincident { a, b } => Some((a, b)),
            _ => None,
        }
    }
}

impl Constraint {
    /// The dimension it holds, if it holds one — an angle in radians: what
    /// a dialog edits.
    pub fn value(&self) -> Option<Scalar> {
        use Constraint::*;
        match *self {
            Distance { value, .. }
            | DistanceX { value, .. }
            | DistanceY { value, .. }
            | PointLineDistance { value, .. }
            | Length { value, .. }
            | Radius { value, .. }
            | Diameter { value, .. }
            | Offset { value, .. }
            | Angle { value, .. } => Some(value),
            _ => None,
        }
    }

    /// Gives its dimension the value `v` — an angle in radians; nothing for
    /// one without.
    pub fn set_value(&mut self, v: Scalar) {
        use Constraint::*;
        match self {
            Distance { value, .. }
            | DistanceX { value, .. }
            | DistanceY { value, .. }
            | PointLineDistance { value, .. }
            | Length { value, .. }
            | Radius { value, .. }
            | Diameter { value, .. }
            | Offset { value, .. }
            | Angle { value, .. } => *value = v,
            _ => {}
        }
    }

    /// The points this constraint refers to directly (curves aside).
    pub fn points(&self) -> Vec<PointId> {
        use Constraint::*;
        match *self {
            Coincident { a, b }
            | Distance { a, b, .. }
            | DistanceX { a, b, .. }
            | DistanceY { a, b, .. }
            | Symmetric { a, b, .. }
            | Moved { a, b, .. } => vec![a, b],
            PointOnCurve { point, .. }
            | Midpoint { point, .. }
            | Center { point, .. }
            | Fix { point, .. }
            | PointLineDistance { point, .. } => vec![point],
            _ => Vec::new(),
        }
    }

    /// The curves this constraint refers to.
    pub fn curves(&self) -> Vec<CurveId> {
        use Constraint::*;
        match *self {
            PointOnCurve { curve, .. }
            | Midpoint { curve, .. }
            | Center { curve, .. }
            | Length { curve, .. }
            | Radius { curve, .. }
            | Diameter { curve, .. } => vec![curve],
            Horizontal { line }
            | Vertical { line }
            | PointLineDistance { line, .. }
            | Symmetric { line, .. }
            | Moved { by: line, .. } => vec![line],
            Parallel { a, b }
            | Perpendicular { a, b }
            | Collinear { a, b }
            | Tangent { a, b }
            | Equal { a, b }
            | Concentric { a, b }
            | Angle { a, b, .. }
            | EqualSweep { a, b }
            | Offset { a, b, .. } => vec![a, b],
            OffsetAt { a, b, by, .. } => vec![a, b, by],
            _ => Vec::new(),
        }
    }
}

/// Every point's `[x, y]`, by [`PointId`]: the sketch's own positions, as
/// drawn (see [`Sketch::positions`]).
pub type Positions = BTreeMap<PointId, Vector2>;

/// A sketch's geometry as the kernel builds on it: every point, and every
/// arc's sweep and circle's radius. Solved (see [`Sketch::enclose`]), each
/// encloses the exact solution of the sketch's constraints; as drawn (see
/// [`Enclosure::as_drawn`]), each is the sketch's own value, sharp. A rigid
/// motion of either is one too (see [`crate::ProfileLoop::to_nurbs`]).
#[derive(Clone, Debug, PartialEq)]
pub struct Enclosure {
    pub points: BTreeMap<PointId, Vector2>,
    /// An arc's sweep, a circle's radius.
    pub params: BTreeMap<CurveId, Scalar>,
}

impl Enclosure {
    /// `sketch`'s geometry exactly as drawn: the sketch's own values.
    pub fn as_drawn(sketch: &Sketch) -> Self {
        Enclosure {
            points: sketch.points.iter().map(|(&id, p)| (id, p.xy())).collect(),
            params: sketch
                .curves
                .iter()
                .filter_map(|(&id, c)| match c.kind {
                    CurveKind::Arc { sweep, .. } => Some((id, sweep)),
                    CurveKind::Circle { radius, .. } => Some((id, radius)),
                    _ => None,
                })
                .collect(),
        }
    }
}

/// A constraint sketch.
///
/// Every entity is keyed by a stable id rather than stored by position: an id
/// is handed out once, by the `add_*` methods, and never reused — not even
/// after the entity is removed. That is what lets anything outside the sketch
/// (a constraint, a profile, a topological name of the solid extruded from
/// it) keep referring to "that line" while the sketch is edited around it.
/// The maps are ordered, so a serialized sketch is deterministic and diffs
/// line by line.
#[derive(Clone, Debug, Default, PartialEq, Serialize, Deserialize)]
pub struct Sketch {
    pub points: BTreeMap<PointId, Point>,
    pub curves: BTreeMap<CurveId, Curve>,
    pub constraints: BTreeMap<ConstraintId, Constraint>,
    /// The id the next added entity gets; greater than every id in use. One
    /// counter for all three kinds, so an id `add_*` hands out is unique
    /// across the sketch.
    pub next_id: u64,
}

impl Sketch {
    pub fn new() -> Self {
        Self::default()
    }

    pub fn point(&self, id: PointId) -> GeopResult<&Point> {
        self.points
            .get(&id)
            .ok_or_else(|| GeopError::new(format!("sketch has no point {id}")))
    }

    pub fn curve(&self, id: CurveId) -> GeopResult<&Curve> {
        self.curves
            .get(&id)
            .ok_or_else(|| GeopError::new(format!("sketch has no curve {id}")))
    }

    /// Every point's `[x, y]`.
    pub fn positions(&self) -> Positions {
        self.points.iter().map(|(&id, p)| (id, p.xy())).collect()
    }

    fn fresh_id(&mut self) -> u64 {
        let id = self.next_id;
        self.next_id += 1;
        id
    }

    pub fn add_point(&mut self, x: Scalar, y: Scalar) -> PointId {
        let id = PointId(self.fresh_id());
        self.points.insert(id, Point { x, y, fixed: false });
        id
    }

    /// A point at `at`, as drawn.
    pub fn new_point_at(&mut self, at: [f64; 2]) -> PointId {
        self.add_point(Scalar::from_f64(at[0]), Scalar::from_f64(at[1]))
    }

    /// A point given from outside the sketch, at `(x, y)` (see the module
    /// docs).
    pub fn add_fixed_point(&mut self, x: Scalar, y: Scalar) -> PointId {
        let id = PointId(self.fresh_id());
        self.points.insert(id, Point { x, y, fixed: true });
        id
    }

    /// Adds a curve of `kind`, profile geometry, solved for.
    pub fn add_curve(&mut self, kind: CurveKind) -> CurveId {
        let id = CurveId(self.fresh_id());
        self.curves.insert(
            id,
            Curve {
                kind,
                construction: false,
                fixed: false,
            },
        );
        id
    }

    pub fn add_line(&mut self, start: PointId, end: PointId) -> CurveId {
        self.add_curve(CurveKind::Line { start, end })
    }

    /// An arc from `start` to `end`, turning counter-clockwise by `sweep`
    /// radians (clockwise if negative).
    pub fn add_arc(&mut self, start: PointId, end: PointId, sweep: Scalar) -> CurveId {
        self.add_curve(CurveKind::Arc { start, end, sweep })
    }

    pub fn add_circle(&mut self, center: PointId, radius: Scalar) -> CurveId {
        self.add_curve(CurveKind::Circle { center, radius })
    }

    pub fn add_spline(&mut self, control_points: Vec<PointId>) -> CurveId {
        self.add_curve(CurveKind::Spline {
            control_points,
            shape: None,
        })
    }

    /// A text: `text`, its baseline from `anchor`, its capitals `height`
    /// tall, turned by `angle` radians (see [`CurveKind::Text`]).
    pub fn add_text(
        &mut self,
        anchor: PointId,
        text: impl Into<String>,
        height: Scalar,
        angle: Scalar,
    ) -> CurveId {
        self.add_curve(CurveKind::Text {
            anchor,
            text: text.into(),
            height,
            angle,
        })
    }

    pub fn set_construction(&mut self, curve: CurveId, construction: bool) {
        if let Some(c) = self.curves.get_mut(&curve) {
            c.construction = construction;
        }
    }

    pub fn constrain(&mut self, constraint: Constraint) -> ConstraintId {
        let id = ConstraintId(self.fresh_id());
        self.constraints.insert(id, constraint);
        id
    }

    /// Removes `points`, `curves` and `constraints`, and everything that
    /// depends on them (see [`remove`]).
    pub fn remove(&mut self, points: &[PointId], curves: &[CurveId], constraints: &[ConstraintId]) {
        let (all_points, all_curves) = (&mut self.points, &mut self.curves);
        remove(
            all_points,
            all_curves,
            &mut self.constraints,
            points,
            curves,
            constraints,
        );
    }

    /// Check every reference and every constraint's operand kinds, so the
    /// solver and profile code can rely on them.
    pub fn validate(&self) -> GeopResult<()> {
        let max_id = [
            self.points.keys().last().map(|id| id.0),
            self.curves.keys().last().map(|id| id.0),
            self.constraints.keys().last().map(|id| id.0),
        ];
        if let Some(max_id) = max_id.into_iter().flatten().max()
            && max_id >= self.next_id
        {
            return Err(GeopError::new(format!(
                "sketch uses id {max_id}, but its next_id is only {}: new entities would reuse ids",
                self.next_id
            )));
        }
        for (&i, curve) in &self.curves {
            for p in curve.points() {
                let point = self
                    .point(p)
                    .map_err(|e| e.with_context(format!("curve {i}")))?;
                if curve.fixed && !point.fixed {
                    return Err(GeopError::new(format!(
                        "curve {i} is fixed, but its point {p} is not"
                    )));
                }
            }
            match &curve.kind {
                CurveKind::Line { start, end } | CurveKind::Arc { start, end, .. }
                    if start == end =>
                {
                    return Err(GeopError::new(format!(
                        "curve {i} starts and ends at the same point"
                    )));
                }
                CurveKind::Arc { sweep, .. }
                    if !sweep.is_finite()
                        || !sweep.abs().definitely_less(Scalar::TWO.mul(Scalar::PI)) =>
                {
                    return Err(GeopError::new(format!(
                        "arc {i} has sweep {sweep:?}, which is not definitely within (-2π, 2π)"
                    )));
                }
                CurveKind::Spline { control_points, .. } if control_points.len() < 2 => {
                    return Err(GeopError::new(format!(
                        "spline {i} needs at least 2 control points"
                    )));
                }
                CurveKind::Spline {
                    control_points,
                    shape: Some(shape),
                } => {
                    let n = control_points.len();
                    if shape.degree == 0
                        || shape.degree >= n
                        || shape.knots.len() != n + shape.degree + 1
                        || shape.weights.len() != n
                        || !shape
                            .weights
                            .iter()
                            .all(|w| w.definitely_greater(Scalar::ZERO))
                    {
                        return Err(GeopError::new(format!(
                            "spline {i} of {n} control points has an inconsistent shape: {shape:?}"
                        )));
                    }
                }
                CurveKind::Text { height, angle, .. }
                    if !height.is_finite()
                        || !height.definitely_greater(Scalar::ZERO)
                        || !angle.is_finite() =>
                {
                    return Err(GeopError::new(format!(
                        "text {i} is {height:?} tall, turned by {angle:?}: a text is definitely taller than nothing, and turned by a finite angle"
                    )));
                }
                _ => {}
            }
        }
        for (&i, c) in &self.constraints {
            self.validate_constraint(c)
                .map_err(|e| e.with_context(format!("constraint {i} = {c:?}")))?;
        }
        Ok(())
    }

    /// Whether `c` could be a constraint of the sketch: its points and
    /// curves are there, and of the kinds it constrains.
    pub fn validate_constraint(&self, c: &Constraint) -> GeopResult<()> {
        use Constraint::*;
        for p in c.points() {
            self.point(p)?;
        }
        let kind = |id: CurveId| self.curve(id).map(|c| &c.kind);
        for curve in c.curves() {
            if matches!(kind(curve)?, CurveKind::Text { .. }) {
                return Err(GeopError::new(format!(
                    "curve {curve} is a text, which takes no constraint: constrain the point it is placed at"
                )));
            }
        }
        let is_line = |id| Ok::<_, GeopError>(matches!(kind(id)?, CurveKind::Line { .. }));
        let is_round = |id| {
            Ok::<_, GeopError>(matches!(
                kind(id)?,
                CurveKind::Arc { .. } | CurveKind::Circle { .. }
            ))
        };
        let need = |ok: bool, what: &str| {
            if ok {
                Ok(())
            } else {
                Err(GeopError::new(format!("operands must be {what}")))
            }
        };
        match c {
            Coincident { .. }
            | Distance { .. }
            | DistanceX { .. }
            | DistanceY { .. }
            | Fix { .. } => Ok(()),
            PointOnCurve { curve, .. } => need(
                !matches!(kind(*curve)?, CurveKind::Spline { .. }),
                "a point and a line, arc or circle",
            ),
            Horizontal { line } | Vertical { line } => need(is_line(*line)?, "a line"),
            Parallel { a, b }
            | Perpendicular { a, b }
            | Collinear { a, b }
            | Angle { a, b, .. } => need(is_line(*a)? && is_line(*b)?, "two lines"),
            Tangent { a, b } => {
                let shared = self.shared_endpoint(*a, *b)?.is_some();
                let two_lines = is_line(*a)? && is_line(*b)?;
                let a_circle = matches!(kind(*a)?, CurveKind::Circle { .. });
                let b_circle = matches!(kind(*b)?, CurveKind::Circle { .. });
                let ok = shared && !(two_lines || a_circle || b_circle)
                    || !shared
                        && (is_round(*a)? && (is_round(*b)? || is_line(*b)?)
                            || is_line(*a)? && is_round(*b)?);
                need(
                    ok,
                    "curves sharing an endpoint (not two lines), a line and a circle/arc, or two circles/arcs",
                )
            }
            Equal { a, b } | Offset { a, b, .. } => need(
                is_line(*a)? && is_line(*b)? || is_round(*a)? && is_round(*b)?,
                "two lines or two circles/arcs",
            ),
            Concentric { a, b } => need(is_round(*a)? && is_round(*b)?, "two circles/arcs"),
            Center { curve, .. } => need(is_round(*curve)?, "a point and a circle or arc"),
            Midpoint { curve, .. } => need(
                matches!(
                    kind(*curve)?,
                    CurveKind::Line { .. } | CurveKind::Arc { .. }
                ),
                "a point and a line or arc",
            ),
            Symmetric { line, .. } => need(is_line(*line)?, "two points and a line"),
            PointLineDistance { line, .. } => need(is_line(*line)?, "a point and a line"),
            Length { curve, .. } => need(
                matches!(
                    kind(*curve)?,
                    CurveKind::Line { .. } | CurveKind::Arc { .. }
                ),
                "a line or arc",
            ),
            Radius { curve, .. } | Diameter { curve, .. } => {
                need(is_round(*curve)?, "a circle or arc")
            }
            Moved { by, .. } => need(
                matches!(kind(*by)?, CurveKind::Line { .. } | CurveKind::Arc { .. }),
                "two points and a line or arc",
            ),
            EqualSweep { a, b } => need(
                matches!(kind(*a)?, CurveKind::Arc { .. })
                    && matches!(kind(*b)?, CurveKind::Arc { .. }),
                "two arcs",
            ),
            OffsetAt { a, b, by, .. } => need(
                matches!(kind(*a)?, CurveKind::Spline { .. })
                    && matches!(kind(*b)?, CurveKind::Spline { .. })
                    && matches!(kind(*by)?, CurveKind::Circle { .. }),
                "two splines and a circle",
            ),
        }
    }

    /// Union-find representative of every point under
    /// [`Constraint::Coincident`]: points with the same representative are
    /// one point.
    pub fn point_classes(&self) -> BTreeMap<PointId, PointId> {
        point_classes(&self.points, &self.constraints)
    }

    /// Every point the constraints put on the infinite line through the line
    /// `line`: its endpoints, points constrained onto it
    /// ([`Constraint::PointOnCurve`], a [`Constraint::Midpoint`] of it, an
    /// endpoint of a [`Constraint::Collinear`] partner), and any point
    /// coincident with one of those.
    ///
    /// Structural, like all connectivity here: a point that merely happens
    /// to lie on the line is not reported.
    pub fn on_line(&self, line: CurveId) -> GeopResult<BTreeSet<PointId>> {
        let CurveKind::Line { start, end } = self.curve(line)?.kind else {
            return Err(GeopError::new(format!("curve {line} is not a line")));
        };
        let class = self.point_classes();
        let mut on = BTreeSet::new();
        let mut mark = |p: PointId| {
            on.insert(class[&p]);
        };
        mark(start);
        mark(end);
        for c in self.constraints.values() {
            match *c {
                Constraint::PointOnCurve { point, curve }
                | Constraint::Midpoint { point, curve }
                    if curve == line =>
                {
                    mark(point)
                }
                Constraint::Collinear { a, b } if a == line || b == line => {
                    let other = if a == line { b } else { a };
                    for p in self.curve(other)?.points() {
                        mark(p);
                    }
                }
                _ => {}
            }
        }
        Ok(class
            .iter()
            .filter(|(_, rep)| on.contains(rep))
            .map(|(&p, _)| p)
            .collect())
    }

    /// Whether a [`Constraint::Tangent`] ties the curves `a` and `b`.
    pub fn tangent(&self, a: CurveId, b: CurveId) -> bool {
        self.constraints.values().any(|c| {
            matches!(*c, Constraint::Tangent { a: x, b: y } if (x, y) == (a, b) || (x, y) == (b, a))
        })
    }

    /// Which ends `(a_at_end, b_at_end)` of open curves `a` and `b` are the
    /// same point, if any (`false` = start, `true` = end).
    pub fn shared_endpoint(&self, a: CurveId, b: CurveId) -> GeopResult<Option<(bool, bool)>> {
        let (Some((a0, a1)), Some((b0, b1))) =
            (self.curve(a)?.endpoints(), self.curve(b)?.endpoints())
        else {
            return Ok(None);
        };
        let class = self.point_classes();
        let same = |p: PointId, q: PointId| class[&p] == class[&q];
        Ok([(false, false), (false, true), (true, false), (true, true)]
            .into_iter()
            .find(|&(ea, eb)| same(if ea { a1 } else { a0 }, if eb { b1 } else { b0 })))
    }
}