geop_core_sketch/
plain.rs

1//! Plane geometry in plain numbers: where a tool places what it builds, and
2//! where the pointer meets the sketch. Only ever a free choice — a position
3//! the solver then makes exact, a suggestion of which piece of a curve is
4//! meant — never a result the kernel reasons about: what the sketch *is* is
5//! its design data, and what that means comes from its solver.
6
7use std::f64::consts::{PI, TAU};
8
9use geop_core_math::vector::Vector2;
10
11use crate::sketch::{CurveId, CurveKind, PointId, Sketch};
12
13pub use geop_core_math::plain::{
14    P2, add, bounds, cross2 as cross, distance, dot, normalize as unit, scale, sub,
15};
16
17/// `v` turned a quarter counter-clockwise.
18pub fn perp(v: P2) -> P2 {
19    [-v[1], v[0]]
20}
21
22/// `v` turned counter-clockwise by `angle`.
23pub fn rotate(v: P2, angle: f64) -> P2 {
24    let (s, c) = angle.sin_cos();
25    [v[0] * c - v[1] * s, v[0] * s + v[1] * c]
26}
27
28/// `angle` brought into `(-π, π]`.
29pub fn wrap(angle: f64) -> f64 {
30    let a = (angle + PI).rem_euclid(TAU) - PI;
31    if a == -PI { PI } else { a }
32}
33
34/// The counter-clockwise angle from `a` to `b`, in `(-π, π]`.
35pub fn angle_between(a: P2, b: P2) -> f64 {
36    cross(a, b).atan2(dot(a, b))
37}
38
39/// The angle from `from` round to `to`, followed on from `previous`, the
40/// sweep it was before (none if zero): within half a turn of it, so that a
41/// sweep dragged round goes on past half a turn.
42pub fn swept(previous: f64, from: P2, to: P2) -> f64 {
43    let raw = angle_between(from, to);
44    if previous == 0.0 {
45        raw
46    } else {
47        previous + wrap(raw - previous)
48    }
49}
50
51/// `p` mirrored across the line through `a` and `b`.
52pub fn reflect(p: P2, a: P2, b: P2) -> P2 {
53    let Some(u) = unit(sub(b, a)) else {
54        return p;
55    };
56    let q = sub(p, a);
57    let along = scale(u, dot(q, u));
58    add(a, sub(scale(along, 2.0), q))
59}
60
61/// `v` in plain numbers.
62pub fn of(v: &Vector2) -> P2 {
63    [v[0].to_f64(), v[1].to_f64()]
64}
65
66/// Where the sketch point `p` is drawn.
67pub fn xy(sketch: &Sketch, p: PointId) -> P2 {
68    of(&sketch.points[&p].xy())
69}
70
71/// Where the segments from `a` to `b` and from `c` to `d` cross, if they
72/// do.
73pub fn segments_cross(a: P2, b: P2, c: P2, d: P2) -> Option<P2> {
74    let (u, v) = (sub(b, a), sub(d, c));
75    let denom = cross(u, v);
76    if denom == 0.0 {
77        return None;
78    }
79    let w = sub(c, a);
80    let (s, t) = (cross(w, v) / denom, cross(w, u) / denom);
81    ((0.0..=1.0).contains(&s) && (0.0..=1.0).contains(&t)).then(|| add(a, scale(u, s)))
82}
83
84/// The signed sweep of the arc from `s` to `e` through `p`, by the
85/// inscribed angle theorem: counter-clockwise (positive) when `p` lies right
86/// of the chord. Not finite when `p` is on the chord's line.
87pub fn sweep_through(s: P2, e: P2, p: P2) -> f64 {
88    let (a, b) = (sub(s, p), sub(e, p));
89    let phi = cross(a, b).atan2(dot(a, b)).abs();
90    let sign = if cross(sub(e, s), sub(p, s)) < 0.0 {
91        1.0
92    } else {
93        -1.0
94    };
95    sign * (TAU - 2.0 * phi)
96}
97
98/// A line, circle or arc in plain numbers: what intersections are found
99/// on, and where along it a point is.
100#[derive(Clone, Copy, Debug, PartialEq)]
101pub enum Plain {
102    /// From `a` to `b`, or — `infinite` — the whole line through them.
103    Line { a: P2, b: P2, infinite: bool },
104    /// About `center`; an arc's part of it from the angle `start`,
105    /// counter-clockwise by `sweep` (clockwise if negative).
106    Round {
107        center: P2,
108        radius: f64,
109        span: Option<(f64, f64)>,
110    },
111}
112
113impl Plain {
114    /// `curve` of `sketch` as drawn, `infinite` if a line; none for a
115    /// spline or a text, or an arc too straight to have a center.
116    pub fn of(sketch: &Sketch, curve: CurveId, infinite: bool) -> Option<Plain> {
117        let p = |q: PointId| xy(sketch, q);
118        Some(match sketch.curves.get(&curve)?.kind {
119            CurveKind::Line { start, end } => Plain::Line {
120                a: p(start),
121                b: p(end),
122                infinite,
123            },
124            CurveKind::Circle { center, radius } => Plain::Round {
125                center: p(center),
126                radius: radius.to_f64(),
127                span: None,
128            },
129            CurveKind::Arc { start, end, sweep } => Plain::arc(p(start), p(end), sweep.to_f64())?,
130            CurveKind::Spline { .. } | CurveKind::Text { .. } => return None,
131        })
132    }
133
134    /// The arc from `s` to `e` turning by `sweep`; none if too straight to
135    /// have a center.
136    pub fn arc(s: P2, e: P2, sweep: f64) -> Option<Plain> {
137        // As `crate::geometry::Arc::center`: the chord's middle, moved to
138        // its left by `(L / 2) cot(half)`.
139        let chord = sub(e, s);
140        let length = chord[0].hypot(chord[1]);
141        let half = sweep / 2.0;
142        let left = perp(unit(chord)?);
143        let center = add(
144            scale(add(s, e), 0.5),
145            scale(left, length / 2.0 * half.cos() / half.sin()),
146        );
147        let radius = length / (2.0 * half.sin().abs());
148        let from = sub(s, center);
149        (radius.is_finite() && center.iter().all(|v| v.is_finite())).then_some(Plain::Round {
150            center,
151            radius,
152            span: Some((from[1].atan2(from[0]), sweep)),
153        })
154    }
155
156    /// The whole line or circle it lies on.
157    pub fn full(self) -> Plain {
158        match self {
159            Plain::Line { a, b, .. } => Plain::Line {
160                a,
161                b,
162                infinite: true,
163            },
164            Plain::Round { center, radius, .. } => Plain::Round {
165                center,
166                radius,
167                span: None,
168            },
169        }
170    }
171
172    /// Whether it is closed: a circle.
173    pub fn closed(&self) -> bool {
174        matches!(self, Plain::Round { span: None, .. })
175    }
176
177    /// Where `q`, a point of its full line or circle, is along it: from 0
178    /// at its start to 1 at its end — a circle's start the angle 0, turning
179    /// counter-clockwise. Beyond `[0, 1]` for a point of the line or circle
180    /// outside the line's or arc's own part of it.
181    pub fn param(&self, q: P2) -> f64 {
182        match *self {
183            Plain::Line { a, b, .. } => {
184                let d = sub(b, a);
185                dot(sub(q, a), d) / dot(d, d)
186            }
187            Plain::Round {
188                center, span: None, ..
189            } => {
190                let r = sub(q, center);
191                r[1].atan2(r[0]).rem_euclid(TAU) / TAU
192            }
193            Plain::Round {
194                center,
195                span: Some((start, sweep)),
196                ..
197            } => {
198                let r = sub(q, center);
199                ((r[1].atan2(r[0]) - start) * sweep.signum()).rem_euclid(TAU) / sweep.abs()
200            }
201        }
202    }
203
204    /// Where along it — in `[0, 1]`, as [`Plain::param`] — it comes
205    /// nearest `q`.
206    pub fn nearest(&self, q: P2) -> f64 {
207        let t = self.param(q);
208        match *self {
209            Plain::Line { .. } => t.clamp(0.0, 1.0),
210            Plain::Round { span: None, .. } => t,
211            Plain::Round {
212                span: Some((_, sweep)),
213                ..
214            } => {
215                // Past the end, by `turned - sweep`, or still before the
216                // start, by a full turn less `turned`.
217                let turned = t * sweep.abs();
218                if turned <= sweep.abs() {
219                    t
220                } else if turned - sweep.abs() < TAU - turned {
221                    1.0
222                } else {
223                    0.0
224                }
225            }
226        }
227    }
228
229    /// The point `t` along it (see [`Plain::param`]).
230    pub fn at(&self, t: f64) -> P2 {
231        match *self {
232            Plain::Line { a, b, .. } => add(a, scale(sub(b, a), t)),
233            Plain::Round {
234                center,
235                radius,
236                span,
237            } => {
238                let angle = match span {
239                    None => t * TAU,
240                    Some((start, sweep)) => start + t * sweep,
241                };
242                add(center, [radius * angle.cos(), radius * angle.sin()])
243            }
244        }
245    }
246
247    /// Its unit direction of travel at `t` along it (see [`Plain::param`]).
248    pub fn tangent(&self, t: f64) -> P2 {
249        match *self {
250            Plain::Line { a, b, .. } => unit(sub(b, a)).unwrap_or([1.0, 0.0]),
251            Plain::Round { span, .. } => {
252                let (angle, turn) = match span {
253                    None => (t * TAU, 1.0),
254                    Some((start, sweep)) => (start + t * sweep, sweep.signum()),
255                };
256                scale([-angle.sin(), angle.cos()], turn)
257            }
258        }
259    }
260
261    /// Its part from `t0` to `t1` along it (see [`Plain::param`]): of a
262    /// line, the segment; of an arc or circle, the arc.
263    pub fn part(&self, t0: f64, t1: f64) -> Plain {
264        match *self {
265            Plain::Line { .. } => Plain::Line {
266                a: self.at(t0),
267                b: self.at(t1),
268                infinite: false,
269            },
270            Plain::Round {
271                center,
272                radius,
273                span,
274            } => {
275                let (start, sweep) = span.unwrap_or((0.0, TAU));
276                Plain::Round {
277                    center,
278                    radius,
279                    span: Some((start + t0 * sweep, (t1 - t0) * sweep)),
280                }
281            }
282        }
283    }
284
285    /// The polyline from `t0` to `t1` along it (see [`Plain::param`]).
286    pub fn polyline(&self, t0: f64, t1: f64) -> Vec<P2> {
287        let steps = match self {
288            Plain::Line { .. } => 1,
289            Plain::Round { span, .. } => {
290                let turn = span.map_or(1.0, |(_, sweep)| sweep.abs() / TAU);
291                ((64.0 * turn * (t1 - t0).abs()).ceil() as usize).max(1)
292            }
293        };
294        (0..=steps)
295            .map(|i| self.at(t0 + (t1 - t0) * i as f64 / steps as f64))
296            .collect()
297    }
298
299    /// Whether `q`, a point of its full line or circle, lies on it.
300    pub fn holds(&self, q: P2) -> bool {
301        match *self {
302            Plain::Line { infinite: true, .. } | Plain::Round { span: None, .. } => true,
303            _ => (0.0..=1.0).contains(&self.param(q)),
304        }
305    }
306
307    /// Where the full lines and circles of `self` and `other` cross, kept
308    /// where both actually run. Curves `touching` — tangent by constraint —
309    /// meet at one point, where the two crossings close to coincide are
310    /// taken as one.
311    pub fn crossings(&self, other: &Plain, touching: bool) -> Vec<P2> {
312        let found = match (self, other) {
313            (Plain::Line { a, b, .. }, Plain::Line { a: c, b: d, .. }) => {
314                let (u, v) = (sub(*b, *a), sub(*d, *c));
315                let denom = cross(u, v);
316                if denom == 0.0 {
317                    Vec::new()
318                } else {
319                    vec![add(*a, scale(u, cross(sub(*c, *a), v) / denom))]
320                }
321            }
322            (Plain::Line { a, b, .. }, Plain::Round { center, radius, .. })
323            | (Plain::Round { center, radius, .. }, Plain::Line { a, b, .. }) => {
324                // `a + t u` at `radius` from `center`.
325                let u = sub(*b, *a);
326                let f = sub(*a, *center);
327                let (qa, qb, qc) = (dot(u, u), 2.0 * dot(f, u), dot(f, f) - radius * radius);
328                let disc = qb * qb - 4.0 * qa * qc;
329                if qa == 0.0 {
330                    Vec::new()
331                } else if touching {
332                    vec![add(*a, scale(u, -qb / (2.0 * qa)))]
333                } else if disc < 0.0 {
334                    Vec::new()
335                } else {
336                    let root = disc.sqrt();
337                    [-1.0, 1.0]
338                        .map(|sign| add(*a, scale(u, (-qb + sign * root) / (2.0 * qa))))
339                        .to_vec()
340                }
341            }
342            (
343                Plain::Round {
344                    center: c0,
345                    radius: r0,
346                    ..
347                },
348                Plain::Round {
349                    center: c1,
350                    radius: r1,
351                    ..
352                },
353            ) => {
354                let d = sub(*c1, *c0);
355                let dist = d[0].hypot(d[1]);
356                if dist == 0.0 || (!touching && (dist > r0 + r1 || dist < (r0 - r1).abs())) {
357                    Vec::new()
358                } else {
359                    let along = (r0 * r0 - r1 * r1 + dist * dist) / (2.0 * dist);
360                    let base = add(*c0, scale(d, along / dist));
361                    if touching {
362                        vec![base]
363                    } else {
364                        let off = (r0 * r0 - along * along).max(0.0).sqrt();
365                        let n = [-d[1] / dist, d[0] / dist];
366                        [-1.0, 1.0]
367                            .map(|sign| add(base, scale(n, sign * off)))
368                            .to_vec()
369                    }
370                }
371            }
372        };
373        found
374            .into_iter()
375            .filter(|&q| self.holds(q) && other.holds(q))
376            .collect()
377    }
378}
379
380#[cfg(test)]
381mod tests {
382    use super::*;
383
384    /// A half circle through the point above the chord's middle turns
385    /// clockwise, one below it counter-clockwise.
386    #[test]
387    fn sweeps_through_a_point() {
388        let s = sweep_through([-1.0, 0.0], [1.0, 0.0], [0.0, 1.0]);
389        assert!((s + PI).abs() < 1e-12, "{s}");
390        let s = sweep_through([-1.0, 0.0], [1.0, 0.0], [0.0, -1.0]);
391        assert!((s - PI).abs() < 1e-12, "{s}");
392    }
393
394    #[test]
395    fn reflections_and_tangents() {
396        let r = reflect([1.0, 2.0], [0.0, 0.0], [1.0, 1.0]);
397        assert!(distance(r, [2.0, 1.0]) < 1e-12, "{r:?}");
398        // A quarter circle counter-clockwise from (1, 0): leaving upwards,
399        // arriving leftwards.
400        let q = Plain::arc([1.0, 0.0], [0.0, 1.0], PI / 2.0).unwrap();
401        assert!(distance(q.tangent(0.0), [0.0, 1.0]) < 1e-12);
402        assert!(distance(q.tangent(1.0), [-1.0, 0.0]) < 1e-12);
403    }
404}
geop_core_sketch/plain.rs

geop_core_sketch/
plain.rs
