dotloom_engine/
query.rs

1//! Spatial queries: hit testing, area selection and snapping.
2//!
3//! All queries use the spatial index to collect nearby candidates first, so a
4//! pointer move never scans every entity. Radii are in model units; hosts convert
5//! screen tolerances with the current zoom (`ScreenTolerance::to_model`).
6
7use std::collections::BTreeSet;
8
9use dotloom_document::EntityId;
10use dotloom_geometry::{Aabb, AnchorKind, Curve, FlattenTolerance, ModelTolerance, Point, intersect::intersect};
11use serde::{Deserialize, Serialize};
12
13use crate::{Engine, eval::Ctx};
14
15/// A hit.
16#[derive(Debug, Clone, Copy, PartialEq, Serialize, Deserialize)]
17pub struct Hit {
18    /// Entity.
19    pub entity: EntityId,
20    /// Distance from the query point to the outline (0 inside filled regions).
21    pub distance: f64,
22}
23
24/// Area selection mode.
25#[derive(Debug, Clone, Copy, PartialEq, Eq, Default, Serialize, Deserialize)]
26#[serde(rename_all = "camelCase")]
27pub enum SelectMode {
28    /// Entities fully inside the rectangle.
29    #[default]
30    Window,
31    /// Entities touching the rectangle.
32    Crossing,
33}
34
35/// Snap kinds in priority order.
36#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
37#[serde(rename_all = "camelCase")]
38pub enum SnapKind {
39    /// Endpoint / vertex / corner.
40    Endpoint,
41    /// Curve–curve intersection.
42    Intersection,
43    /// Center / centroid.
44    Center,
45    /// Midpoint.
46    Midpoint,
47    /// Circle quadrant.
48    Quadrant,
49    /// Other named anchor (insert points, plugin anchors).
50    Anchor,
51    /// Closest point on a curve.
52    Nearest,
53    /// Grid point.
54    Grid,
55}
56
57/// Margin (fraction of the snap radius) a same-kind candidate must win by to
58/// replace the previous snap.
59pub const HYSTERESIS: f64 = 0.3;
60
61/// Snap options.
62#[derive(Debug, Clone, Copy, PartialEq, Serialize, Deserialize)]
63#[serde(rename_all = "camelCase", default)]
64pub struct SnapOptions {
65    /// Endpoints, vertices, corners.
66    pub endpoint: bool,
67    /// Midpoints.
68    pub midpoint: bool,
69    /// Centers.
70    pub center: bool,
71    /// Quadrants.
72    pub quadrant: bool,
73    /// Intersections.
74    pub intersection: bool,
75    /// Other anchors.
76    pub anchor: bool,
77    /// Nearest point on curves.
78    pub nearest: bool,
79    /// Grid.
80    pub grid: bool,
81    /// Grid spacing override (mm).
82    pub grid_spacing: Option<f64>,
83}
84
85impl Default for SnapOptions {
86    fn default() -> Self {
87        Self {
88            endpoint: true,
89            midpoint: true,
90            center: true,
91            quadrant: true,
92            intersection: true,
93            anchor: true,
94            nearest: true,
95            grid: false,
96            grid_spacing: None,
97        }
98    }
99}
100
101/// A snap result.
102#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
103#[serde(rename_all = "camelCase")]
104pub struct Snap {
105    /// Snapped point.
106    pub point: Point,
107    /// Kind.
108    pub kind: SnapKind,
109    /// Entity providing the snap.
110    pub entity: Option<EntityId>,
111    /// Anchor name (anchor snaps).
112    pub anchor: Option<String>,
113    /// Second entity (intersections).
114    pub other: Option<EntityId>,
115}
116
117/// A snap query.
118#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
119#[serde(rename_all = "camelCase")]
120pub struct SnapQuery {
121    /// Pointer position (model).
122    pub point: Point,
123    /// Snap radius (model units).
124    pub radius: f64,
125    /// Options.
126    #[serde(default)]
127    pub options: SnapOptions,
128    /// Entities to ignore (e.g. the one being drawn or dragged).
129    #[serde(default)]
130    pub exclude: Vec<EntityId>,
131    /// Previous result for hysteresis.
132    #[serde(default)]
133    pub previous: Option<Snap>,
134}
135
136fn anchor_kind(k: AnchorKind) -> SnapKind {
137    match k {
138        AnchorKind::Endpoint | AnchorKind::Vertex | AnchorKind::Corner | AnchorKind::Node => SnapKind::Endpoint,
139        AnchorKind::Midpoint => SnapKind::Midpoint,
140        AnchorKind::Center | AnchorKind::Centroid => SnapKind::Center,
141        AnchorKind::Quadrant => SnapKind::Quadrant,
142        AnchorKind::Insert => SnapKind::Anchor,
143    }
144}
145
146impl Engine {
147    fn visible_candidates(&self, ids: Vec<EntityId>, exclude: &BTreeSet<EntityId>) -> Vec<EntityId> {
148        ids.into_iter()
149            .filter(|id| !exclude.contains(id))
150            .filter(|id| {
151                self.doc.entity(*id).is_some_and(|e| !e.hidden && self.doc.layer(e.layer).is_some_and(|l| l.visible))
152            })
153            .collect()
154    }
155
156    /// Entities under `point` within `radius`, nearest first (ties: topmost first).
157    pub fn hit_test(&mut self, point: Point, radius: f64) -> Vec<Hit> {
158        if !point.is_finite() || (radius.is_nan() || radius < 0.0) {
159            return Vec::new();
160        }
161        let ids = self.visible_candidates(self.index.query_point(point, radius), &BTreeSet::new());
162        let ctx = Ctx { view: &self.doc, registry: &self.registry };
163        let mut hits: Vec<(Hit, usize)> = Vec::new();
164        for id in ids {
165            let ev = self.cache.get(ctx, id);
166            let mut best = f64::INFINITY;
167            for s in ev.shapes() {
168                if s.is_region()
169                    && s.contains_point(point, FlattenTolerance(radius.max(1e-9) * 0.25))
170                    && has_fill(&self.doc, id)
171                {
172                    best = 0.0;
173                } else {
174                    best = best.min(s.distance_to(point));
175                }
176            }
177            if best <= radius {
178                let z = self.doc.order_index(id).unwrap_or(0);
179                hits.push((Hit { entity: id, distance: best }, z));
180            }
181        }
182        hits.sort_by(|a, b| a.0.distance.total_cmp(&b.0.distance).then(b.1.cmp(&a.1)));
183        hits.into_iter().map(|(h, _)| h).collect()
184    }
185
186    /// Area selection.
187    pub fn select_in_rect(&mut self, rect: Aabb, mode: SelectMode) -> Vec<EntityId> {
188        let ids = self.visible_candidates(self.index.query_rect(rect), &BTreeSet::new());
189        let ctx = Ctx { view: &self.doc, registry: &self.registry };
190        let mut out = Vec::new();
191        for id in ids {
192            let ev = self.cache.get(ctx, id);
193            let ok = match mode {
194                SelectMode::Window => rect.contains(ev.bbox),
195                SelectMode::Crossing => {
196                    rect.contains(ev.bbox) || ev.shapes().any(|s| s.intersects_rect(rect, ModelTolerance::DEFAULT))
197                }
198            };
199            if ok {
200                out.push(id);
201            }
202        }
203        out
204    }
205
206    /// Snap a point. Hysteresis (`previous`) limits flicker between candidates: the
207    /// previous snap is kept within 1.5 × radius unless a better kind appears or a
208    /// same-kind candidate is closer by more than [`HYSTERESIS`] × radius.
209    ///
210    /// The result is a proposal: committing it still goes through the
211    /// solver and independent checks, so a snap can never commit a hard-rule violation.
212    pub fn snap(&mut self, q: &SnapQuery) -> Option<Snap> {
213        if !q.point.is_finite() || (q.radius.is_nan() || q.radius <= 0.0) {
214            return None;
215        }
216        let exclude: BTreeSet<EntityId> = q.exclude.iter().copied().collect();
217        let ids = self.visible_candidates(self.index.query_point(q.point, q.radius), &exclude);
218        let ctx = Ctx { view: &self.doc, registry: &self.registry };
219        let o = q.options;
220        let mut cands: Vec<Snap> = Vec::new();
221        let mut curves: Vec<(EntityId, Curve)> = Vec::new();
222        for id in ids.iter().take(64) {
223            let ev = self.cache.get(ctx, *id);
224            for a in &ev.anchors {
225                let kind = anchor_kind(a.kind);
226                let on = match kind {
227                    SnapKind::Endpoint => o.endpoint,
228                    SnapKind::Midpoint => o.midpoint,
229                    SnapKind::Center => o.center,
230                    SnapKind::Quadrant => o.quadrant,
231                    SnapKind::Anchor => o.anchor,
232                    _ => false,
233                };
234                if on && a.point.distance(q.point) <= q.radius {
235                    cands.push(Snap {
236                        point: a.point,
237                        kind,
238                        entity: Some(*id),
239                        anchor: Some(a.name.to_string()),
240                        other: None,
241                    });
242                }
243            }
244            for s in ev.shapes() {
245                for c in s.curves() {
246                    if o.nearest {
247                        let (_, p) = c.closest(q.point);
248                        if p.distance(q.point) <= q.radius {
249                            cands.push(Snap {
250                                point: p,
251                                kind: SnapKind::Nearest,
252                                entity: Some(*id),
253                                anchor: None,
254                                other: None,
255                            });
256                        }
257                    }
258                    if curves.len() < 64 {
259                        curves.push((*id, c));
260                    }
261                }
262            }
263        }
264        if o.intersection {
265            for i in 0..curves.len() {
266                for j in i + 1..curves.len() {
267                    let (Some((ea, ca)), Some((eb, cb))) = (curves.get(i), curves.get(j)) else { continue };
268                    if ea == eb {
269                        continue;
270                    }
271                    for p in intersect(ca, cb, ModelTolerance::DEFAULT).points {
272                        if p.point.distance(q.point) <= q.radius {
273                            cands.push(Snap {
274                                point: p.point,
275                                kind: SnapKind::Intersection,
276                                entity: Some(*ea),
277                                anchor: None,
278                                other: Some(*eb),
279                            });
280                        }
281                    }
282                }
283            }
284        }
285        if o.grid {
286            let g = o.grid_spacing.unwrap_or(self.doc.settings.grid.spacing);
287            if g > 0.0 && g.is_finite() {
288                let p = Point::new((q.point.x / g).round() * g, (q.point.y / g).round() * g);
289                if p.distance(q.point) <= q.radius {
290                    cands.push(Snap { point: p, kind: SnapKind::Grid, entity: None, anchor: None, other: None });
291                }
292            }
293        }
294        let best = cands
295            .into_iter()
296            .min_by(|a, b| a.kind.cmp(&b.kind).then(a.point.distance(q.point).total_cmp(&b.point.distance(q.point))));
297        // Hysteresis: keep the previous snap while it stays close, unless a candidate
298        // of higher priority appears or one of the same priority is clearly closer.
299        let prev_d = q.previous.as_ref().map_or(f64::INFINITY, |p| p.point.distance(q.point));
300        if let Some(prev) = &q.previous
301            && prev_d <= q.radius * 1.5
302            && best.as_ref().is_none_or(|b| {
303                b.kind > prev.kind
304                    || (b.kind == prev.kind && b.point.distance(q.point) + q.radius * HYSTERESIS >= prev_d)
305            })
306            && prev.entity.is_none_or(|e| self.doc.entity(e).is_some() && !exclude.contains(&e))
307            && self.snap_still_valid(prev)
308        {
309            return Some(prev.clone());
310        }
311        best
312    }
313
314    fn snap_still_valid(&mut self, s: &Snap) -> bool {
315        match (s.entity, &s.anchor) {
316            (Some(e), Some(a)) => {
317                let ctx = Ctx { view: &self.doc, registry: &self.registry };
318                self.cache
319                    .get(ctx, e)
320                    .anchor(a)
321                    .is_some_and(|p| p.distance(s.point) <= 1e-9 * (1.0 + p.to_vector().length()))
322            }
323            _ => true,
324        }
325    }
326}
327
328fn has_fill(doc: &dotloom_document::Document, id: EntityId) -> bool {
329    doc.entity(id).is_some_and(|e| e.style.fill.is_some() || !e.type_id.namespace().eq("dotloom"))
330}
dotloom_engine/query.rs

dotloom_engine/
query.rs
