Skip to main content

ggplot_rs/geom/
repel.rs

1//! Repelling text labels — `geom_text_repel` / `geom_label_repel` (R's
2//! ggrepel).
3//!
4//! Labels start at their data point (plus an optional nudge) and are pushed
5//! apart by a deterministic, seeded relaxation until they no longer overlap
6//! each other or the labelled points; a spring pulls each label back towards
7//! its point and every label stays inside the panel. Labels that still overlap
8//! more than `max_overlaps` other labels/points are dropped (reported as a
9//! render warning, like ggrepel's "unlabeled data points"). A segment connects
10//! a label to its point when it ended up farther away than
11//! `min_segment_length`.
12//!
13//! The layout runs in pixel space at draw time (text extents depend on the
14//! rendered size), costs O(n log n + overlapping pairs) per iteration thanks to
15//! a sweep over sorted box edges, and is bounded by `max_iter` and `max_time`.
16//! Above `max_labels` labels the simulation is skipped (greedy non-overlapping
17//! placement instead) with a warning.
18
19use crate::aes::Aesthetic;
20use crate::coord::Coord;
21use crate::data::{DataFrame, Value};
22use crate::position::identity::PositionIdentity;
23use crate::position::Position;
24use crate::render::backend::{
25    DrawBackend, FontFace, LineStyle, Linetype, RectStyle, TextAnchor, TextStyle,
26};
27use crate::render::{Rect, RenderError};
28use crate::scale::ScaleSet;
29use crate::stat::identity::StatIdentity;
30use crate::stat::Stat;
31use crate::theme::Theme;
32
33use super::{Geom, GeomParams};
34
35/// Axis along which labels may move.
36#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
37pub enum RepelDirection {
38    /// Move freely (default).
39    #[default]
40    Both,
41    /// Only horizontally.
42    X,
43    /// Only vertically.
44    Y,
45    /// Only downwards from the target (#513), for labels hanging from the
46    /// top of a panel: no relaxation — in x order, each label moves down to
47    /// the first slot clear of the labels before it, so a crowded row
48    /// stacks in reading order. Points and lines are not avoided.
49    Down,
50}
51
52/// Shared layout parameters of [`GeomTextRepel`] / [`GeomLabelRepel`].
53#[derive(Clone, Debug)]
54pub struct RepelParams {
55    /// Padding (px) around each label's box when testing for overlaps
56    /// (ggrepel `box.padding`).
57    pub box_padding: f64,
58    /// Padding (px) around each data point (ggrepel `point.padding`); also
59    /// the gap left between a segment and its point.
60    pub point_padding: f64,
61    /// Radius (px) of the data points labels must avoid (match the point
62    /// layer's size; `GeomPoint`'s default is 3).
63    pub point_size: f64,
64    /// Horizontal nudge of the starting position, in data units (numeric x).
65    pub nudge_x: f64,
66    /// Vertical nudge of the starting position, in data units (numeric y).
67    pub nudge_y: f64,
68    /// Strength of the repulsion between overlapping boxes.
69    pub force: f64,
70    /// Strength of the spring pulling a label back to its point.
71    pub force_pull: f64,
72    /// Maximum relaxation iterations.
73    pub max_iter: usize,
74    /// Wall-clock bound for the relaxation (a safety net — the layout is
75    /// deterministic as long as it converges or hits `max_iter` first).
76    /// Ignored on `wasm32`, which has no monotonic clock.
77    pub max_time: std::time::Duration,
78    /// Drop labels that still overlap more than this many other labels or
79    /// points after the layout (ggrepel `max.overlaps`, default 10).
80    pub max_overlaps: usize,
81    /// Draw a segment when the label box is farther than this (px) from its
82    /// point (ggrepel `min.segment.length`).
83    pub min_segment_length: f64,
84    /// Seed of the tie-breaking jitter; equal seeds give equal layouts.
85    pub seed: u64,
86    /// Movement axis.
87    pub direction: RepelDirection,
88    /// Where the label box starts relative to its point, as `GeomText`'s
89    /// `hjust` (#513): 0 = its left edge at the point, 0.5 = centred
90    /// (default), 1 = its right edge.
91    pub hjust: f64,
92    /// As [`Self::hjust`], vertically: 0 = the box's bottom at the point.
93    pub vjust: f64,
94    /// Text halo colour (ggrepel's `bg.colour`, as `GeomText::bg_colour`),
95    /// so a label stays readable over marks; `None` (default) draws none.
96    pub bg_colour: Option<(u8, u8, u8)>,
97    /// Text halo radius in px (ggrepel's `bg.r`).
98    pub bg_r: f64,
99    /// Above this many labels the force layout is skipped (it is O(n²) in
100    /// the worst case) and labels are placed greedily, dropping overlaps.
101    pub max_labels: usize,
102    /// Segment colour; `None` = the label's text colour.
103    pub segment_color: Option<(u8, u8, u8)>,
104    /// Segment width (px).
105    pub segment_width: f64,
106    /// Straight lines labels keep clear of, as `(slope, intercept)` in the
107    /// same (scale) space as [`crate::geom::refline::GeomAbline`] — pass the
108    /// plot's ablines so a label isn't drawn across one.
109    pub avoid_ablines: Vec<(f64, f64)>,
110}
111
112impl Default for RepelParams {
113    fn default() -> Self {
114        RepelParams {
115            box_padding: 3.0,
116            point_padding: 2.0,
117            point_size: 3.0,
118            nudge_x: 0.0,
119            nudge_y: 0.0,
120            force: 1.0,
121            force_pull: 1.0,
122            max_iter: 2000,
123            max_time: std::time::Duration::from_millis(500),
124            max_overlaps: 10,
125            min_segment_length: 12.0,
126            seed: 42,
127            direction: RepelDirection::Both,
128            hjust: 0.5,
129            vjust: 0.5,
130            bg_colour: None,
131            bg_r: 0.0,
132            max_labels: 500,
133            segment_color: None,
134            segment_width: 0.6,
135            avoid_ablines: Vec::new(),
136        }
137    }
138}
139
140macro_rules! repel_builders {
141    ($t:ty) => {
142        impl $t {
143            /// Padding (px) around label boxes when testing overlaps.
144            pub fn box_padding(mut self, px: f64) -> Self {
145                self.repel.box_padding = px;
146                self
147            }
148            /// Padding (px) around the labelled points.
149            pub fn point_padding(mut self, px: f64) -> Self {
150                self.repel.point_padding = px;
151                self
152            }
153            /// Radius (px) of the points to avoid.
154            pub fn point_size(mut self, px: f64) -> Self {
155                self.repel.point_size = px;
156                self
157            }
158            /// Nudge the starting position (data units).
159            pub fn nudge(mut self, x: f64, y: f64) -> Self {
160                self.repel.nudge_x = x;
161                self.repel.nudge_y = y;
162                self
163            }
164            /// Repulsion strength.
165            pub fn force(mut self, force: f64) -> Self {
166                self.repel.force = force;
167                self
168            }
169            /// Spring strength back to the point.
170            pub fn force_pull(mut self, force: f64) -> Self {
171                self.repel.force_pull = force;
172                self
173            }
174            /// Maximum iterations.
175            pub fn max_iter(mut self, n: usize) -> Self {
176                self.repel.max_iter = n;
177                self
178            }
179            /// Wall-clock bound of the layout.
180            pub fn max_time(mut self, t: std::time::Duration) -> Self {
181                self.repel.max_time = t;
182                self
183            }
184            /// Drop labels overlapping more than `n` labels/points.
185            pub fn max_overlaps(mut self, n: usize) -> Self {
186                self.repel.max_overlaps = n;
187                self
188            }
189            /// Minimum label–point distance (px) that gets a segment.
190            pub fn min_segment_length(mut self, px: f64) -> Self {
191                self.repel.min_segment_length = px;
192                self
193            }
194            /// Seed of the deterministic tie-breaking jitter.
195            pub fn seed(mut self, seed: u64) -> Self {
196                self.repel.seed = seed;
197                self
198            }
199            /// Restrict movement to one axis.
200            pub fn direction(mut self, d: RepelDirection) -> Self {
201                self.repel.direction = d;
202                self
203            }
204            /// Where the box starts relative to its point (`GeomText`'s
205            /// `hjust` / `vjust`; 0.5 = centred).
206            pub fn justify(mut self, hjust: f64, vjust: f64) -> Self {
207                self.repel.hjust = hjust;
208                self.repel.vjust = vjust;
209                self
210            }
211            /// A halo of `colour` and radius `r` px around the text.
212            pub fn halo(mut self, colour: (u8, u8, u8), r: f64) -> Self {
213                self.repel.bg_colour = Some(colour);
214                self.repel.bg_r = r;
215                self
216            }
217            /// Label-count cap of the force layout.
218            pub fn max_labels(mut self, n: usize) -> Self {
219                self.repel.max_labels = n;
220                self
221            }
222            /// Keep labels clear of the line `y = intercept + slope * x`
223            /// (scale space, like `geom_abline`).
224            pub fn avoid_abline(mut self, slope: f64, intercept: f64) -> Self {
225                self.repel.avoid_ablines.push((slope, intercept));
226                self
227            }
228            /// Segment colour.
229            pub fn segment_color(mut self, color: (u8, u8, u8)) -> Self {
230                self.repel.segment_color = Some(color);
231                self
232            }
233        }
234    };
235}
236
237/// Text labels repelled away from each other and from their points
238/// (`ggrepel::geom_text_repel`). Requires `x`, `y`, `label`; an empty / `NA`
239/// label is not drawn but its point is still avoided (as in ggrepel).
240pub struct GeomTextRepel {
241    pub size: f64,
242    pub color: (u8, u8, u8),
243    pub alpha: f64,
244    pub fontface: FontFace,
245    pub repel: RepelParams,
246}
247
248impl Default for GeomTextRepel {
249    fn default() -> Self {
250        GeomTextRepel {
251            size: 10.0,
252            color: (0, 0, 0),
253            alpha: 1.0,
254            fontface: FontFace::Plain,
255            repel: RepelParams::default(),
256        }
257    }
258}
259
260repel_builders!(GeomTextRepel);
261
262/// Boxed labels repelled away from each other and from their points
263/// (`ggrepel::geom_label_repel`).
264pub struct GeomLabelRepel {
265    pub size: f64,
266    pub color: (u8, u8, u8),
267    pub fill: (u8, u8, u8),
268    pub alpha: f64,
269    /// Inner padding (px) between text and box border.
270    pub label_padding: f64,
271    pub fontface: FontFace,
272    pub repel: RepelParams,
273}
274
275impl Default for GeomLabelRepel {
276    fn default() -> Self {
277        GeomLabelRepel {
278            size: 10.0,
279            color: (0, 0, 0),
280            fill: (255, 255, 255),
281            alpha: 0.9,
282            label_padding: 3.0,
283            fontface: FontFace::Plain,
284            repel: RepelParams::default(),
285        }
286    }
287}
288
289repel_builders!(GeomLabelRepel);
290
291/// Axis-aligned label box: centre and half extents (px).
292#[derive(Clone, Copy, Debug)]
293struct LabelBox {
294    cx: f64,
295    cy: f64,
296    hw: f64,
297    hh: f64,
298}
299
300impl LabelBox {
301    fn overlaps(&self, o: &LabelBox, pad: f64) -> bool {
302        (self.cx - o.cx).abs() < self.hw + o.hw + 2.0 * pad
303            && (self.cy - o.cy).abs() < self.hh + o.hh + 2.0 * pad
304    }
305
306    /// Distance from `(x, y)` to the box (0 inside).
307    fn dist_to(&self, x: f64, y: f64) -> f64 {
308        let dx = ((x - self.cx).abs() - self.hw).max(0.0);
309        let dy = ((y - self.cy).abs() - self.hh).max(0.0);
310        dx.hypot(dy)
311    }
312
313    /// Closest point of the box border/interior to `(x, y)`.
314    fn closest(&self, x: f64, y: f64) -> (f64, f64) {
315        (
316            x.clamp(self.cx - self.hw, self.cx + self.hw),
317            y.clamp(self.cy - self.hh, self.cy + self.hh),
318        )
319    }
320}
321
322/// Result of a layout: final boxes, which labels were kept, and how many
323/// were dropped for exceeding `max_overlaps`.
324pub(crate) struct RepelLayout {
325    boxes: Vec<LabelBox>,
326    kept: Vec<bool>,
327    dropped: usize,
328    /// The force layout was skipped because there were too many labels.
329    capped: bool,
330}
331
332/// Lay out `labels` (anchor point, half extents incl. any label padding) so
333/// they avoid each other and `points`, inside `panel`. Pure and
334/// deterministic for a given `params.seed` (unless `max_time` cuts it short).
335#[cfg(test)]
336pub(crate) fn layout(
337    anchors: &[(f64, f64)],
338    targets: &[(f64, f64)],
339    half: &[(f64, f64)],
340    points: &[(f64, f64)],
341    panel: &Rect,
342    p: &RepelParams,
343) -> RepelLayout {
344    layout_with_lines(anchors, targets, half, points, &[], panel, p)
345}
346
347/// Does the segment `a`–`b` pass through `bx` grown by `pad` (Liang–Barsky)?
348fn segment_hits_box(a: (f64, f64), b: (f64, f64), bx: &LabelBox, pad: f64) -> bool {
349    let (dx, dy) = (b.0 - a.0, b.1 - a.1);
350    let (mut t0, mut t1) = (0.0f64, 1.0f64);
351    for (q, d, lo, hi) in [
352        (a.0, dx, bx.cx - bx.hw - pad, bx.cx + bx.hw + pad),
353        (a.1, dy, bx.cy - bx.hh - pad, bx.cy + bx.hh + pad),
354    ] {
355        if d == 0.0 {
356            if q < lo || q > hi {
357                return false;
358            }
359            continue;
360        }
361        let (mut ta, mut tb) = ((lo - q) / d, (hi - q) / d);
362        if ta > tb {
363            std::mem::swap(&mut ta, &mut tb);
364        }
365        t0 = t0.max(ta);
366        t1 = t1.min(tb);
367        if t0 > t1 {
368            return false;
369        }
370    }
371    true
372}
373
374/// [`layout`], also keeping boxes clear of `lines` (pixel segments): a box a
375/// segment crosses is pushed along the segment's normal, to the side its
376/// centre is on.
377pub(crate) fn layout_with_lines(
378    anchors: &[(f64, f64)],
379    targets: &[(f64, f64)],
380    half: &[(f64, f64)],
381    points: &[(f64, f64)],
382    lines: &[Seg],
383    panel: &Rect,
384    p: &RepelParams,
385) -> RepelLayout {
386    let lines: Vec<Seg> = lines
387        .iter()
388        .copied()
389        .filter(|(a, b)| {
390            [a.0, a.1, b.0, b.1].iter().all(|v| v.is_finite()) && (a.0 != b.0 || a.1 != b.1)
391        })
392        .collect();
393    let n = anchors.len();
394    let finite = |v: f64, d: f64| if v.is_finite() { v } else { d };
395    let box_pad = finite(p.box_padding, 0.0).max(0.0);
396    let pt_r = finite(p.point_size, 0.0).max(0.0) + finite(p.point_padding, 0.0).max(0.0);
397    let force = finite(p.force, 1.0).clamp(0.0, 100.0);
398    let pull = finite(p.force_pull, 1.0).clamp(0.0, 100.0);
399    let (x0, x1) = (panel.x, panel.x + panel.width);
400    let (y0, y1) = (panel.y, panel.y + panel.height);
401    let clamp_box = |b: &mut LabelBox| {
402        // A box wider than the panel is centred on it.
403        b.cx = if 2.0 * b.hw >= x1 - x0 {
404            (x0 + x1) / 2.0
405        } else {
406            b.cx.clamp(x0 + b.hw, x1 - b.hw)
407        };
408        b.cy = if 2.0 * b.hh >= y1 - y0 {
409            (y0 + y1) / 2.0
410        } else {
411            b.cy.clamp(y0 + b.hh, y1 - b.hh)
412        };
413    };
414
415    // #475: whether a box already touches the panel edge it would be pushed
416    // towards (`sign` < 0: left / up), so the push would be clamped away.
417    let blocked = |b: &LabelBox, along_x: bool, sign: f64| {
418        let eps = 1e-6;
419        if along_x {
420            (sign < 0.0 && b.cx - b.hw <= x0 + eps) || (sign > 0.0 && b.cx + b.hw >= x1 - eps)
421        } else {
422            (sign < 0.0 && b.cy - b.hh <= y0 + eps) || (sign > 0.0 && b.cy + b.hh >= y1 - eps)
423        }
424    };
425
426    let mut rng = crate::rng::SplitMix64::new(p.seed);
427    let mut boxes: Vec<LabelBox> = (0..n)
428        .map(|i| {
429            let mut b = LabelBox {
430                cx: targets[i].0 + rng.range_f64(-0.5, 0.5),
431                cy: targets[i].1 + rng.range_f64(-0.5, 0.5),
432                hw: half[i].0,
433                hh: half[i].1,
434            };
435            clamp_box(&mut b);
436            b
437        })
438        .collect();
439
440    let capped = n > p.max_labels;
441    let (move_x, move_y) = match p.direction {
442        RepelDirection::Both => (1.0, 1.0),
443        RepelDirection::X => (1.0, 0.0),
444        RepelDirection::Y | RepelDirection::Down => (0.0, 1.0),
445    };
446
447    // Points sorted by x for range queries.
448    let mut pts: Vec<(f64, f64)> = points
449        .iter()
450        .copied()
451        .filter(|(x, y)| x.is_finite() && y.is_finite())
452        .collect();
453    pts.sort_by(|a, b| a.0.total_cmp(&b.0));
454    let points_near = |pts: &[(f64, f64)], lo: f64, hi: f64| {
455        let start = pts.partition_point(|q| q.0 < lo);
456        let end = pts.partition_point(|q| q.0 <= hi);
457        start..end.max(start)
458    };
459
460    if !capped && p.direction == RepelDirection::Down {
461        // #513: no relaxation — in x order, each label starts at its target
462        // and moves down past the placed labels it overlaps, to the first
463        // free slot (first fit), so a crowded row stacks in reading order.
464        let mut order: Vec<usize> = (0..n).collect();
465        order.sort_by(|&a, &b| targets[a].0.total_cmp(&targets[b].0).then(a.cmp(&b)));
466        let mut placed: Vec<usize> = Vec::with_capacity(n);
467        for &i in &order {
468            let mut b = LabelBox {
469                cx: targets[i].0,
470                cy: targets[i].1,
471                hw: half[i].0,
472                hh: half[i].1,
473            };
474            clamp_box(&mut b);
475            loop {
476                let below = placed
477                    .iter()
478                    .filter(|&&j| b.overlaps(&boxes[j], box_pad))
479                    .map(|&j| boxes[j].cy + boxes[j].hh + b.hh + 2.0 * box_pad)
480                    .reduce(f64::max);
481                let Some(y) = below.filter(|y| y.is_finite()) else {
482                    break;
483                };
484                let was = b.cy;
485                b.cy = y;
486                clamp_box(&mut b);
487                // at the bottom edge: left overlapping (max_overlaps decides)
488                if b.cy <= was {
489                    break;
490                }
491            }
492            boxes[i] = b;
493            placed.push(i);
494        }
495    } else if !capped && n > 0 {
496        #[cfg(not(target_arch = "wasm32"))]
497        let started = std::time::Instant::now();
498        let mut order: Vec<usize> = (0..n).collect();
499        let mut delta = vec![(0.0f64, 0.0f64); n];
500        let mut hit = vec![false; n];
501        // The spring is active for the first three quarters; the rest only
502        // separates, so the layout ends in a non-overlapping state whenever
503        // one is reachable.
504        let pull_until = p.max_iter - p.max_iter / 4;
505        // Largest step per iteration, against overshooting when many
506        // overlaps add up.
507        let max_step = 12.0;
508        // #475: the final phase keeps pushing labels that are clear of every
509        // other label off the points / lines they cover, and remembers the
510        // label-overlap-free layout that covers the fewest of them (that
511        // push can make two labels touch again before the phase ends).
512        let mut best: Option<(usize, Vec<LabelBox>)> = None;
513        for iter in 0..p.max_iter {
514            #[cfg(not(target_arch = "wasm32"))]
515            if iter % 16 == 15 && started.elapsed() >= p.max_time {
516                break;
517            }
518            for d in delta.iter_mut() {
519                *d = (0.0, 0.0);
520            }
521            hit.iter_mut().for_each(|h| *h = false);
522            let mut overlaps = 0usize;
523
524            // Box–box: sweep over boxes sorted by their left edge.
525            order.sort_by(|&a, &b| {
526                (boxes[a].cx - boxes[a].hw).total_cmp(&(boxes[b].cx - boxes[b].hw))
527            });
528            for (oi, &i) in order.iter().enumerate() {
529                let bi = boxes[i];
530                for &j in &order[oi + 1..] {
531                    let bj = boxes[j];
532                    if bj.cx - bj.hw - box_pad >= bi.cx + bi.hw + box_pad {
533                        break;
534                    }
535                    if !bi.overlaps(&bj, box_pad) {
536                        continue;
537                    }
538                    overlaps += 1;
539                    hit[i] = true;
540                    hit[j] = true;
541                    let (dx, dy) = (bi.cx - bj.cx, bi.cy - bj.cy);
542                    let ox = bi.hw + bj.hw + 2.0 * box_pad - dx.abs();
543                    let oy = bi.hh + bj.hh + 2.0 * box_pad - dy.abs();
544                    let sx = if dx == 0.0 {
545                        tie(&mut rng)
546                    } else {
547                        dx.signum()
548                    };
549                    let sy = if dy == 0.0 {
550                        tie(&mut rng)
551                    } else {
552                        dy.signum()
553                    };
554                    // Separate along the axis of least overlap (respecting the
555                    // allowed direction).
556                    let mut along_x = match p.direction {
557                        RepelDirection::X => true,
558                        RepelDirection::Y | RepelDirection::Down => false,
559                        RepelDirection::Both => ox * move_x <= oy * move_y,
560                    };
561                    let s = |x: bool| if x { sx } else { sy };
562                    // #475: a box pinned to the panel edge it would move
563                    // towards leaves the whole move to the other one; both
564                    // pinned on that axis, separate along the other.
565                    let pinned = |x: bool| (blocked(&bi, x, s(x)), blocked(&bj, x, -s(x)));
566                    if p.direction == RepelDirection::Both && pinned(along_x) == (true, true) {
567                        along_x = !along_x;
568                    }
569                    let (pi, pj) = pinned(along_x);
570                    let (ki, kj) = match (pi, pj) {
571                        (true, false) => (0.0, force),
572                        (false, true) => (force, 0.0),
573                        _ => (0.5 * force, 0.5 * force),
574                    };
575                    if along_x {
576                        delta[i].0 += sx * ox * ki;
577                        delta[j].0 -= sx * ox * kj;
578                    } else {
579                        delta[i].1 += sy * oy * ki;
580                        delta[j].1 -= sy * oy * kj;
581                    }
582                }
583            }
584
585            let label_overlaps = overlaps;
586            let final_phase = iter >= pull_until;
587            // Labels in an overlap with another label (the final phase moves
588            // those only apart from each other).
589            let label_hit = if final_phase { hit.clone() } else { Vec::new() };
590            let free = |i: usize| !final_phase || !label_hit[i];
591
592            // Box–point: push labels off every data point they cover. In the
593            // final phase only labels clear of every other label are pushed
594            // (a point that cannot be avoided must not keep two labels
595            // overlapping), at half strength.
596            let point_force = if final_phase { 0.5 * force } else { force };
597            for i in 0..n {
598                if point_force == 0.0 {
599                    break;
600                }
601                if !free(i) {
602                    continue;
603                }
604                let b = boxes[i];
605                let r = pt_r + box_pad;
606                for q in &pts[points_near(&pts, b.cx - b.hw - r, b.cx + b.hw + r)] {
607                    let (dx, dy) = (b.cx - q.0, b.cy - q.1);
608                    let ox = b.hw + r - dx.abs();
609                    let oy = b.hh + r - dy.abs();
610                    if ox <= 0.0 || oy <= 0.0 {
611                        continue;
612                    }
613                    overlaps += 1;
614                    hit[i] = true;
615                    let sx = if dx == 0.0 {
616                        tie(&mut rng)
617                    } else {
618                        dx.signum()
619                    };
620                    let sy = if dy == 0.0 {
621                        tie(&mut rng)
622                    } else {
623                        dy.signum()
624                    };
625                    let mut along_x = match p.direction {
626                        RepelDirection::X => true,
627                        RepelDirection::Y | RepelDirection::Down => false,
628                        RepelDirection::Both => ox <= oy,
629                    };
630                    let (mut sx, mut sy, mut ox, mut oy) = (sx, sy, ox, oy);
631                    // #475: off a point towards a panel edge the box already
632                    // touches, the clamp would cancel the push and pin the
633                    // label on the point: go along the other axis, else
634                    // across to the point's other side.
635                    if blocked(&b, along_x, if along_x { sx } else { sy }) {
636                        let other = !along_x;
637                        if p.direction == RepelDirection::Both
638                            && !blocked(&b, other, if other { sx } else { sy })
639                        {
640                            along_x = other;
641                        } else if along_x {
642                            sx = -sx;
643                            ox = 2.0 * (b.hw + r) - ox;
644                        } else {
645                            sy = -sy;
646                            oy = 2.0 * (b.hh + r) - oy;
647                        }
648                    }
649                    if along_x {
650                        delta[i].0 += sx * ox * point_force;
651                    } else {
652                        delta[i].1 += sy * oy * point_force;
653                    }
654                }
655            }
656
657            // Box–line: push a label a line crosses off it, along the line's
658            // normal (the same phases as the points).
659            for i in 0..n {
660                if point_force == 0.0 {
661                    break;
662                }
663                if !free(i) {
664                    continue;
665                }
666                let b = boxes[i];
667                for &(a, e) in &lines {
668                    if !segment_hits_box(a, e, &b, box_pad) {
669                        continue;
670                    }
671                    overlaps += 1;
672                    hit[i] = true;
673                    let (lx, ly) = (e.0 - a.0, e.1 - a.1);
674                    let len = lx.hypot(ly);
675                    let (nx, ny) = (-ly / len, lx / len);
676                    let d = (b.cx - a.0) * nx + (b.cy - a.1) * ny;
677                    let side = if d == 0.0 { tie(&mut rng) } else { d.signum() };
678                    let need = b.hw * nx.abs() + b.hh * ny.abs() + box_pad - d.abs();
679                    if need > 0.0 {
680                        delta[i].0 += side * nx * need * point_force;
681                        delta[i].1 += side * ny * need * point_force;
682                    }
683                }
684            }
685
686            if final_phase && label_overlaps == 0 {
687                let covered = overlaps - label_overlaps;
688                if best.as_ref().is_none_or(|(c, _)| covered < *c) {
689                    best = Some((covered, boxes.clone()));
690                }
691                if covered == 0 {
692                    break;
693                }
694            }
695
696            // Spring back towards the target, then move and clamp.
697            let mut moved = 0.0f64;
698            for i in 0..n {
699                let b = &mut boxes[i];
700                // Pull back only labels that are currently free, so the spring
701                // never holds two labels in a residual overlap.
702                let k = if iter < pull_until && !hit[i] {
703                    0.1 * pull
704                } else {
705                    0.0
706                };
707                let sx = (targets[i].0 - b.cx) * k;
708                let sy = (targets[i].1 - b.cy) * k;
709                let cap = |v: f64| {
710                    if v.is_finite() {
711                        v.clamp(-max_step, max_step)
712                    } else {
713                        0.0
714                    }
715                };
716                let (mx, my) = (cap(delta[i].0 + sx) * move_x, cap(delta[i].1 + sy) * move_y);
717                let (px, py) = (b.cx, b.cy);
718                b.cx += mx;
719                b.cy += my;
720                clamp_box(b);
721                moved = moved.max((b.cx - px).abs() + (b.cy - py).abs());
722            }
723            if (overlaps == 0 && moved < 0.05)
724                || (final_phase && label_overlaps == 0 && moved < 0.05)
725            {
726                break;
727            }
728        }
729        // The best label-overlap-free state of the final phase (its
730        // overlaps were counted, unlike those of the state after the last
731        // move).
732        if let Some((_, b)) = best {
733            boxes = b;
734        }
735    }
736
737    // Drop labels that still overlap too much: each label counts overlaps
738    // with already-kept labels and with points other than its own.
739    let mut kept = vec![false; n];
740    let mut dropped = 0usize;
741    let mut kept_boxes: Vec<LabelBox> = Vec::new();
742    let limit = if capped { 0 } else { p.max_overlaps };
743    for i in 0..n {
744        let b = boxes[i];
745        let mut count = kept_boxes.iter().filter(|o| b.overlaps(o, 0.0)).count();
746        // Without a layout, covered points are not held against a label.
747        if count <= limit && !capped {
748            let r = pt_r;
749            count += pts[points_near(&pts, b.cx - b.hw - r, b.cx + b.hw + r)]
750                .iter()
751                .filter(|q| {
752                    !(q.0 == anchors[i].0 && q.1 == anchors[i].1)
753                        && (q.0 - b.cx).abs() < b.hw + r
754                        && (q.1 - b.cy).abs() < b.hh + r
755                })
756                .count();
757        }
758        if count > limit {
759            dropped += 1;
760        } else {
761            kept[i] = true;
762            kept_boxes.push(b);
763        }
764    }
765
766    RepelLayout {
767        boxes,
768        kept,
769        dropped,
770        capped,
771    }
772}
773
774/// Deterministic ±1 for coincident centres.
775fn tie(rng: &mut crate::rng::SplitMix64) -> f64 {
776    if rng.next_u64() & 1 == 0 {
777        -1.0
778    } else {
779        1.0
780    }
781}
782
783/// A pixel line segment (start, end).
784type Seg = ((f64, f64), (f64, f64));
785
786/// One label to place.
787struct Item {
788    row: usize,
789    anchor: (f64, f64),
790    target: (f64, f64),
791    text: String,
792}
793
794/// Shared draw routine; `label` = `Some((fill, padding))` draws boxes.
795#[allow(clippy::too_many_arguments)]
796fn draw_repel(
797    name: &str,
798    data: &DataFrame,
799    coord: &dyn Coord,
800    scales: &ScaleSet,
801    theme: &Theme,
802    backend: &mut dyn DrawBackend,
803    size: f64,
804    color: (u8, u8, u8),
805    alpha: f64,
806    face: FontFace,
807    label: Option<((u8, u8, u8), f64)>,
808    p: &RepelParams,
809) -> Result<(), RenderError> {
810    let x_col = data
811        .column("x")
812        .ok_or(RenderError::MissingAesthetic("x".into()))?;
813    let y_col = data
814        .column("y")
815        .ok_or(RenderError::MissingAesthetic("y".into()))?;
816    let label_col = data
817        .column("label")
818        .ok_or(RenderError::MissingAesthetic("label".into()))?;
819    let color_col = data.column("color");
820    let fill_col = data.column("fill");
821
822    let panel = backend.plot_area();
823    let x_scale = scales.get(&Aesthetic::X);
824    let y_scale = scales.get(&Aesthetic::Y);
825    let size = if size.is_finite() && size > 0.0 {
826        size
827    } else {
828        10.0
829    };
830
831    let to_px = |xv: &Value, yv: &Value| -> (f64, f64) {
832        let nx = x_scale.map(|s| s.map(xv)).unwrap_or(0.5);
833        let ny = y_scale.map(|s| s.map(yv)).unwrap_or(0.5);
834        coord.transform((nx, ny), &panel)
835    };
836    let nudged = |v: &Value, d: f64, discrete: bool| -> Value {
837        match v.as_f64() {
838            Some(f) if d != 0.0 && d.is_finite() && !discrete => Value::Float(f + d),
839            _ => v.clone(),
840        }
841    };
842    let x_discrete = x_scale.map(|s| s.is_discrete()).unwrap_or(false);
843    let y_discrete = y_scale.map(|s| s.is_discrete()).unwrap_or(false);
844
845    let mut points = Vec::with_capacity(data.nrows());
846    let mut items: Vec<Item> = Vec::new();
847    for i in 0..data.nrows() {
848        if x_col[i].is_na() || y_col[i].is_na() {
849            continue;
850        }
851        let anchor = to_px(&x_col[i], &y_col[i]);
852        if !(anchor.0.is_finite() && anchor.1.is_finite()) {
853            continue;
854        }
855        points.push(anchor);
856        let text = if label_col[i].is_na() {
857            String::new()
858        } else {
859            label_col[i].to_group_key()
860        };
861        if text.trim().is_empty() {
862            continue;
863        }
864        let target = to_px(
865            &nudged(&x_col[i], p.nudge_x, x_discrete),
866            &nudged(&y_col[i], p.nudge_y, y_discrete),
867        );
868        let target = if target.0.is_finite() && target.1.is_finite() {
869            target
870        } else {
871            anchor
872        };
873        items.push(Item {
874            row: i,
875            anchor,
876            target,
877            text,
878        });
879    }
880    if items.is_empty() {
881        return Ok(());
882    }
883
884    let pad = label.map(|(_, pd)| pd.max(0.0)).unwrap_or(0.0);
885    let half: Vec<(f64, f64)> = items
886        .iter()
887        .map(|it| {
888            (
889                it.text.chars().count() as f64 * size * 0.3 + pad,
890                size * 0.5 + pad,
891            )
892        })
893        .collect();
894    let anchors: Vec<(f64, f64)> = items.iter().map(|it| it.anchor).collect();
895    // The box's start: its point, justified (#513; y grows downwards).
896    let just = |j: f64| if j.is_finite() { 0.5 - j } else { 0.0 };
897    let targets: Vec<(f64, f64)> = items
898        .iter()
899        .zip(&half)
900        .map(|(it, h)| {
901            (
902                it.target.0 + 2.0 * h.0 * just(p.hjust),
903                it.target.1 - 2.0 * h.1 * just(p.vjust),
904            )
905        })
906        .collect();
907    // `avoid_ablines` in pixels: the line between two far-apart x values
908    // (the data's own x range, widened) — the box test clips it.
909    let mut lines = Vec::new();
910    if !p.avoid_ablines.is_empty() && !x_discrete && !y_discrete {
911        let xs: Vec<f64> = x_col
912            .iter()
913            .filter_map(|v| v.as_f64())
914            .filter(|v| v.is_finite())
915            .collect();
916        if let (Some(lo), Some(hi)) = (
917            xs.iter().copied().reduce(f64::min),
918            xs.iter().copied().reduce(f64::max),
919        ) {
920            let w = (hi - lo).max(1.0);
921            let (lo, hi) = (lo - 4.0 * w, hi + 4.0 * w);
922            for &(slope, intercept) in &p.avoid_ablines {
923                if !(slope.is_finite() && intercept.is_finite()) {
924                    continue;
925                }
926                let at = |x: f64| to_px(&Value::Float(x), &Value::Float(intercept + slope * x));
927                lines.push((at(lo), at(hi)));
928            }
929        }
930    }
931    let lay = layout_with_lines(&anchors, &targets, &half, &points, &lines, &panel, p);
932
933    if lay.capped {
934        backend.warn(format!(
935            "geom_{name}: {} labels exceed the repel limit of {}; placed without \
936             repulsion (overlapping labels dropped)",
937            items.len(),
938            p.max_labels
939        ));
940    }
941    if lay.dropped > 0 {
942        backend.warn(format!(
943            "geom_{name}: {} unlabeled data point{} (too many overlaps). Consider \
944             increasing max_overlaps",
945            lay.dropped,
946            if lay.dropped == 1 { "" } else { "s" }
947        ));
948    }
949
950    let seg_min = if p.min_segment_length.is_finite() {
951        p.min_segment_length.max(0.0)
952    } else {
953        f64::INFINITY
954    };
955    let alpha = if alpha.is_finite() {
956        alpha.clamp(0.0, 1.0)
957    } else {
958        1.0
959    };
960
961    // Segments first so labels paint over them.
962    super::clear_mark(backend);
963    for (k, it) in items.iter().enumerate() {
964        if !lay.kept[k] {
965            continue;
966        }
967        let b = lay.boxes[k];
968        let d = b.dist_to(it.anchor.0, it.anchor.1);
969        if d <= seg_min || d <= 0.0 {
970            continue;
971        }
972        let (ex, ey) = b.closest(it.anchor.0, it.anchor.1);
973        // Leave a gap of `point_padding` at the point end.
974        let gap = if p.point_padding.is_finite() {
975            p.point_padding.max(0.0)
976        } else {
977            0.0
978        };
979        let (dx, dy) = (ex - it.anchor.0, ey - it.anchor.1);
980        let len = dx.hypot(dy);
981        if len <= gap {
982            continue;
983        }
984        let start = (it.anchor.0 + dx / len * gap, it.anchor.1 + dy / len * gap);
985        let c = p
986            .segment_color
987            .unwrap_or_else(|| row_color(scales, color_col, it.row, color));
988        backend.draw_line(
989            &[start, (ex, ey)],
990            &LineStyle {
991                color: c,
992                width: if p.segment_width.is_finite() {
993                    p.segment_width.max(0.0)
994                } else {
995                    0.6
996                },
997                alpha,
998                linetype: Linetype::Solid,
999                ..Default::default()
1000            },
1001        )?;
1002    }
1003
1004    for (k, it) in items.iter().enumerate() {
1005        if !lay.kept[k] {
1006            continue;
1007        }
1008        let b = lay.boxes[k];
1009        let c = row_color(scales, color_col, it.row, color);
1010        if let Some((fill, _)) = label {
1011            let f = fill_col
1012                .and_then(|fc| scales.map_color(&Aesthetic::Fill, &fc[it.row]))
1013                .unwrap_or(fill);
1014            super::set_mark(
1015                backend,
1016                Some(it.text.clone()),
1017                Some(super::tip_value(&x_col[it.row])),
1018                super::series_key(data, it.row),
1019                super::measured_value(data, it.row),
1020            );
1021            super::set_mark_formatted(
1022                backend,
1023                scales,
1024                Some(&x_col[it.row]),
1025                &Aesthetic::Y,
1026                super::measured_raw(data, it.row),
1027            );
1028            backend.draw_rect(
1029                (b.cx - b.hw, b.cy - b.hh),
1030                (b.cx + b.hw, b.cy + b.hh),
1031                &RectStyle {
1032                    fill: Some(f),
1033                    stroke: Some(c),
1034                    stroke_width: 0.5,
1035                    alpha,
1036                    clip: true,
1037                    corner_radius: 0.0,
1038                },
1039            )?;
1040            super::clear_mark(backend);
1041        }
1042        backend.draw_text(
1043            &it.text,
1044            (b.cx, b.cy),
1045            &TextStyle {
1046                color: c,
1047                size,
1048                anchor: TextAnchor::Middle,
1049                angle: 0.0,
1050                family: super::resolve_font_family("", theme),
1051                face,
1052                bg_colour: p.bg_colour,
1053                bg_r: if p.bg_r.is_finite() {
1054                    p.bg_r.max(0.0)
1055                } else {
1056                    0.0
1057                },
1058            },
1059        )?;
1060    }
1061    Ok(())
1062}
1063
1064fn row_color(
1065    scales: &ScaleSet,
1066    color_col: Option<&[Value]>,
1067    row: usize,
1068    fallback: (u8, u8, u8),
1069) -> (u8, u8, u8) {
1070    color_col
1071        .and_then(|cc| scales.map_color(&Aesthetic::Color, &cc[row]))
1072        .unwrap_or(fallback)
1073}
1074
1075impl Geom for GeomTextRepel {
1076    fn draw(
1077        &self,
1078        data: &DataFrame,
1079        coord: &dyn Coord,
1080        scales: &ScaleSet,
1081        theme: &Theme,
1082        backend: &mut dyn DrawBackend,
1083    ) -> Result<(), RenderError> {
1084        draw_repel(
1085            "text_repel",
1086            data,
1087            coord,
1088            scales,
1089            theme,
1090            backend,
1091            self.size,
1092            self.color,
1093            self.alpha,
1094            self.fontface,
1095            None,
1096            &self.repel,
1097        )
1098    }
1099
1100    fn required_aes(&self) -> Vec<Aesthetic> {
1101        vec![Aesthetic::X, Aesthetic::Y, Aesthetic::Label]
1102    }
1103    fn default_stat(&self) -> Box<dyn Stat> {
1104        Box::new(StatIdentity)
1105    }
1106    fn default_position(&self) -> Box<dyn Position> {
1107        Box::new(PositionIdentity)
1108    }
1109    fn default_params(&self) -> GeomParams {
1110        GeomParams::default()
1111    }
1112    fn name(&self) -> &str {
1113        "text_repel"
1114    }
1115
1116    fn apply_element_geom(&mut self, el: &crate::theme::elements::ElementGeom) {
1117        if let (true, Some(ink)) = (self.color == (0, 0, 0), el.ink) {
1118            self.color = ink;
1119        }
1120    }
1121}
1122
1123impl Geom for GeomLabelRepel {
1124    fn draw(
1125        &self,
1126        data: &DataFrame,
1127        coord: &dyn Coord,
1128        scales: &ScaleSet,
1129        theme: &Theme,
1130        backend: &mut dyn DrawBackend,
1131    ) -> Result<(), RenderError> {
1132        draw_repel(
1133            "label_repel",
1134            data,
1135            coord,
1136            scales,
1137            theme,
1138            backend,
1139            self.size,
1140            self.color,
1141            self.alpha,
1142            self.fontface,
1143            Some((self.fill, self.label_padding)),
1144            &self.repel,
1145        )
1146    }
1147
1148    fn required_aes(&self) -> Vec<Aesthetic> {
1149        vec![Aesthetic::X, Aesthetic::Y, Aesthetic::Label]
1150    }
1151    fn default_stat(&self) -> Box<dyn Stat> {
1152        Box::new(StatIdentity)
1153    }
1154    fn default_position(&self) -> Box<dyn Position> {
1155        Box::new(PositionIdentity)
1156    }
1157    fn default_params(&self) -> GeomParams {
1158        GeomParams::default()
1159    }
1160    fn name(&self) -> &str {
1161        "label_repel"
1162    }
1163
1164    fn apply_element_geom(&mut self, el: &crate::theme::elements::ElementGeom) {
1165        if let (true, Some(ink)) = (self.color == (0, 0, 0), el.ink) {
1166            self.color = ink;
1167        }
1168        if let (true, Some(paper)) = (self.fill == (255, 255, 255), el.paper) {
1169            self.fill = paper;
1170        }
1171    }
1172}
1173
1174#[cfg(test)]
1175mod tests {
1176    use super::*;
1177
1178    fn panel() -> Rect {
1179        Rect {
1180            x: 0.0,
1181            y: 0.0,
1182            width: 400.0,
1183            height: 300.0,
1184        }
1185    }
1186
1187    fn overlapping(lay: &RepelLayout) -> usize {
1188        let mut c = 0;
1189        for i in 0..lay.boxes.len() {
1190            for j in i + 1..lay.boxes.len() {
1191                if lay.kept[i] && lay.kept[j] && lay.boxes[i].overlaps(&lay.boxes[j], 0.0) {
1192                    c += 1;
1193                }
1194            }
1195        }
1196        c
1197    }
1198
1199    #[test]
1200    fn coincident_labels_are_separated_deterministically() {
1201        let anchors = vec![(200.0, 150.0); 6];
1202        let half = vec![(20.0, 6.0); 6];
1203        let p = RepelParams::default();
1204        let a = layout(&anchors, &anchors, &half, &anchors, &panel(), &p);
1205        let b = layout(&anchors, &anchors, &half, &anchors, &panel(), &p);
1206        assert_eq!(overlapping(&a), 0);
1207        assert_eq!(a.dropped, 0);
1208        for (x, y) in a.boxes.iter().zip(&b.boxes) {
1209            assert_eq!((x.cx, x.cy), (y.cx, y.cy), "same seed, same layout");
1210        }
1211        let c = layout(
1212            &anchors,
1213            &anchors,
1214            &half,
1215            &anchors,
1216            &panel(),
1217            &RepelParams {
1218                seed: 7,
1219                ..RepelParams::default()
1220            },
1221        );
1222        assert_eq!(overlapping(&c), 0);
1223    }
1224
1225    #[test]
1226    fn crowded_top_edge_labels_end_clear_of_labels_and_points() {
1227        // #475: a risk map's points crowd the top edge (y = 100 %); the
1228        // spring phase leaves labels on neighbouring points, and the final
1229        // separation-only phase used to stop as soon as labels were apart.
1230        let pan = Rect {
1231            x: 0.0,
1232            y: 0.0,
1233            width: 440.0,
1234            height: 260.0,
1235        };
1236        let px = |v: f64| 10.0 + v / 33.0 * 420.0;
1237        let py = |p: f64| 17.0 + (100.0 - p) / 80.0 * 226.0;
1238        let pts: Vec<(f64, f64)> = [
1239            (1.0, 100.0),
1240            (2.0, 100.0),
1241            (4.0, 100.0),
1242            (4.4, 100.0),
1243            (5.0, 100.0),
1244            (7.0, 100.0),
1245            (7.4, 97.0),
1246            (6.0, 83.0),
1247            (9.0, 100.0),
1248            (16.0, 41.0),
1249            (16.5, 24.0),
1250            (18.0, 27.0),
1251        ]
1252        .iter()
1253        .map(|&(v, p)| (px(v), py(p)))
1254        .collect();
1255        let half = vec![(21.0, 6.0); pts.len()];
1256        let lay = layout(&pts, &pts, &half, &pts, &pan, &RepelParams::default());
1257        assert_eq!(overlapping(&lay), 0);
1258        assert_eq!(lay.dropped, 0);
1259        // A label box touching another point's dot (radius point_size).
1260        let r = RepelParams::default().point_size;
1261        let covered: Vec<usize> = (0..pts.len())
1262            .filter(|&i| {
1263                let b = lay.boxes[i];
1264                pts.iter().enumerate().any(|(j, q)| {
1265                    j != i && (q.0 - b.cx).abs() < b.hw + r && (q.1 - b.cy).abs() < b.hh + r
1266                })
1267            })
1268            .collect();
1269        assert!(covered.is_empty(), "labels on other points: {covered:?}");
1270    }
1271
1272    #[test]
1273    fn labels_avoid_points_and_stay_inside() {
1274        // A dense cloud near the corner.
1275        let anchors: Vec<(f64, f64)> = (0..30)
1276            .map(|i| (5.0 + (i % 6) as f64 * 3.0, 5.0 + (i / 6) as f64 * 3.0))
1277            .collect();
1278        let half = vec![(15.0, 5.0); anchors.len()];
1279        let lay = layout(
1280            &anchors,
1281            &anchors,
1282            &half,
1283            &anchors,
1284            &panel(),
1285            &RepelParams {
1286                max_overlaps: usize::MAX,
1287                ..RepelParams::default()
1288            },
1289        );
1290        let pa = panel();
1291        for b in &lay.boxes {
1292            assert!(b.cx - b.hw >= pa.x - 1e-9 && b.cx + b.hw <= pa.x + pa.width + 1e-9);
1293            assert!(b.cy - b.hh >= pa.y - 1e-9 && b.cy + b.hh <= pa.y + pa.height + 1e-9);
1294        }
1295        assert_eq!(overlapping(&lay), 0, "all 30 labels separated");
1296    }
1297
1298    #[test]
1299    fn max_overlaps_zero_drops_what_cannot_be_placed() {
1300        // 40 labels in a panel that only fits a handful.
1301        let tiny = Rect {
1302            x: 0.0,
1303            y: 0.0,
1304            width: 60.0,
1305            height: 30.0,
1306        };
1307        let anchors = vec![(30.0, 15.0); 40];
1308        let half = vec![(20.0, 6.0); 40];
1309        let lay = layout(
1310            &anchors,
1311            &anchors,
1312            &half,
1313            &[],
1314            &tiny,
1315            &RepelParams {
1316                max_overlaps: 0,
1317                ..RepelParams::default()
1318            },
1319        );
1320        assert!(lay.dropped > 0);
1321        assert_eq!(overlapping(&lay), 0);
1322        assert_eq!(lay.kept.iter().filter(|k| **k).count() + lay.dropped, 40);
1323    }
1324
1325    #[test]
1326    fn direction_y_only_moves_vertically() {
1327        let anchors = vec![(100.0, 150.0), (101.0, 150.0), (102.0, 150.0)];
1328        let half = vec![(20.0, 6.0); 3];
1329        let lay = layout(
1330            &anchors,
1331            &anchors,
1332            &half,
1333            &[],
1334            &panel(),
1335            &RepelParams {
1336                direction: RepelDirection::Y,
1337                ..RepelParams::default()
1338            },
1339        );
1340        for (b, a) in lay.boxes.iter().zip(&anchors) {
1341            assert!((b.cx - a.0).abs() <= 0.5, "x stayed put");
1342        }
1343        assert_eq!(overlapping(&lay), 0);
1344    }
1345
1346    /// #513: labels hanging from the top edge, close in x (event labels).
1347    fn top_edge_labels(direction: RepelDirection) -> (Vec<(f64, f64)>, RepelLayout) {
1348        let xs = [20.0, 32.0, 44.0, 50.0, 58.0, 70.0, 140.0, 150.0];
1349        let anchors: Vec<(f64, f64)> = xs.iter().map(|&x| (x, 0.0)).collect();
1350        let targets: Vec<(f64, f64)> = xs.iter().map(|&x| (x + 26.0, 6.0)).collect();
1351        let half = vec![(25.0, 6.0); xs.len()];
1352        let lay = layout(
1353            &anchors,
1354            &targets,
1355            &half,
1356            &[],
1357            &panel(),
1358            &RepelParams {
1359                direction,
1360                max_overlaps: usize::MAX,
1361                ..RepelParams::default()
1362            },
1363        );
1364        (targets, lay)
1365    }
1366
1367    #[test]
1368    fn down_stacks_top_labels_without_overlap() {
1369        let (targets, lay) = top_edge_labels(RepelDirection::Down);
1370        assert_eq!(overlapping(&lay), 0);
1371        for (b, t) in lay.boxes.iter().zip(&targets) {
1372            assert!((b.cx - t.0).abs() <= 0.5, "x stays put");
1373            assert!(b.cy >= t.1 - 1e-6, "never above its anchor");
1374        }
1375        // the first in x order keeps its place; the one after it, which it
1376        // overlaps, sits right below it
1377        assert_eq!(lay.boxes[0].cy, targets[0].1);
1378        assert!(lay.boxes[1].cy > lay.boxes[0].cy);
1379        assert!(
1380            lay.boxes[6].cy == targets[6].1,
1381            "a label clear of the rest stays up"
1382        );
1383    }
1384
1385    #[test]
1386    fn cap_skips_simulation() {
1387        let anchors: Vec<(f64, f64)> = (0..20).map(|i| (i as f64, 10.0)).collect();
1388        let half = vec![(5.0, 3.0); 20];
1389        let lay = layout(
1390            &anchors,
1391            &anchors,
1392            &half,
1393            &anchors,
1394            &panel(),
1395            &RepelParams {
1396                max_labels: 5,
1397                ..RepelParams::default()
1398            },
1399        );
1400        assert!(lay.capped);
1401        assert_eq!(overlapping(&lay), 0);
1402    }
1403
1404    #[test]
1405    fn non_finite_params_do_not_hang_or_panic() {
1406        let anchors = vec![(10.0, 10.0), (10.0, 10.0)];
1407        let half = vec![(5.0, 3.0); 2];
1408        let lay = layout(
1409            &anchors,
1410            &anchors,
1411            &half,
1412            &[(f64::NAN, 1.0)],
1413            &panel(),
1414            &RepelParams {
1415                force: f64::NAN,
1416                force_pull: f64::INFINITY,
1417                box_padding: f64::NAN,
1418                ..RepelParams::default()
1419            },
1420        );
1421        for b in &lay.boxes {
1422            assert!(b.cx.is_finite() && b.cy.is_finite());
1423        }
1424    }
1425
1426    #[test]
1427    fn labels_move_off_a_line() {
1428        // three labels sitting on the diagonal y = x
1429        let anchors = vec![(100.0, 100.0), (200.0, 200.0), (300.0, 300.0)];
1430        let half = vec![(20.0, 6.0); 3];
1431        let line = ((0.0, 0.0), (400.0, 400.0));
1432        let lay = layout_with_lines(
1433            &anchors,
1434            &anchors,
1435            &half,
1436            &anchors,
1437            &[line],
1438            &panel(),
1439            &RepelParams::default(),
1440        );
1441        for (k, b) in lay.boxes.iter().enumerate() {
1442            assert!(lay.kept[k]);
1443            assert!(
1444                !segment_hits_box(line.0, line.1, b, 0.0),
1445                "label {k} still on the line: {b:?}"
1446            );
1447        }
1448    }
1449
1450    #[test]
1451    fn segment_box_test() {
1452        let b = LabelBox {
1453            cx: 50.0,
1454            cy: 50.0,
1455            hw: 10.0,
1456            hh: 5.0,
1457        };
1458        assert!(segment_hits_box((0.0, 0.0), (100.0, 100.0), &b, 0.0));
1459        assert!(segment_hits_box((0.0, 50.0), (100.0, 50.0), &b, 0.0));
1460        assert!(!segment_hits_box((0.0, 70.0), (100.0, 70.0), &b, 0.0));
1461        assert!(segment_hits_box((0.0, 57.0), (100.0, 57.0), &b, 3.0));
1462        assert!(!segment_hits_box((0.0, 0.0), (30.0, 30.0), &b, 0.0));
1463    }
1464
1465    #[test]
1466    fn down_keeps_every_event_label_in_a_narrow_plot() {
1467        // #513 (anofox#1140): seven event labels at the top of the data,
1468        // close in x, in a narrow plot — all drawn, each starting right of
1469        // its point.
1470        let names = [
1471            "Port strike",
1472            "Typhoon Haikui",
1473            "Canal closure",
1474            "Plant fire",
1475            "Rail outage",
1476            "Customs backlog",
1477            "Typhoon Koinu",
1478        ];
1479        let render = |n: usize, hjust: f64| {
1480            let xs: Vec<Value> = (0..n).map(|i| Value::Float(i as f64)).collect();
1481            let labels: Vec<Value> = names[..n]
1482                .iter()
1483                .map(|n| Value::Str(n.to_string()))
1484                .collect();
1485            crate::plot::GGPlot::new(vec![
1486                ("x".into(), xs),
1487                ("y".into(), vec![Value::Float(10.0); n]),
1488                ("l".into(), labels),
1489            ])
1490            .aes(crate::aes::Aes::new().x("x").y("y").label("l"))
1491            .geom_text_repel_with(
1492                GeomTextRepel::default()
1493                    .direction(RepelDirection::Down)
1494                    .justify(hjust, 0.0)
1495                    .max_overlaps(usize::MAX),
1496            )
1497            .render_svg_native_with_size(220, 300)
1498            .unwrap()
1499        };
1500        let text_x = |svg: &str, name: &str| -> f64 {
1501            let end = svg.find(&format!(">{name}<")).expect(name);
1502            let tag = &svg[svg[..end].rfind("<text").unwrap()..end];
1503            let k = tag.find(" x=\"").unwrap() + 4;
1504            tag[k..k + tag[k..].find('"').unwrap()].parse().unwrap()
1505        };
1506        let all = render(7, 0.0);
1507        assert!(!all.contains("paint-order"), "no halo unless asked");
1508        let halo = crate::plot::GGPlot::new(vec![
1509            ("x".into(), vec![Value::Float(1.0)]),
1510            ("y".into(), vec![Value::Float(1.0)]),
1511            ("l".into(), vec![Value::Str("event".into())]),
1512        ])
1513        .aes(crate::aes::Aes::new().x("x").y("y").label("l"))
1514        .geom_text_repel_with(GeomTextRepel::default().halo((255, 255, 255), 2.0))
1515        .render_svg_native_with_size(220, 300)
1516        .unwrap();
1517        assert!(
1518            halo.contains("paint-order") && halo.contains("stroke=\"#FFFFFF\""),
1519            "{halo}"
1520        );
1521        for n in names {
1522            assert!(all.contains(&format!(">{n}<")), "{n} kept");
1523        }
1524        // one label in mid-panel: justified left, it starts at its point
1525        let (left, centred) = (
1526            text_x(&render(1, 0.0), names[0]),
1527            text_x(&render(1, 0.5), names[0]),
1528        );
1529        assert!(left > centred + 10.0, "{left} vs {centred}");
1530    }
1531
1532    #[test]
1533    fn avoid_abline_in_a_plot() {
1534        let render = |avoid: bool| {
1535            let xs: Vec<Value> = (0..8).map(|i| Value::Float(i as f64)).collect();
1536            let labels: Vec<Value> = (0..8).map(|i| Value::Str(format!("point {i}"))).collect();
1537            crate::plot::GGPlot::new(vec![
1538                ("x".into(), xs.clone()),
1539                ("y".into(), xs),
1540                ("l".into(), labels),
1541            ])
1542            .aes(crate::aes::Aes::new().x("x").y("y").label("l"))
1543            .geom_point()
1544            .geom_text_repel_with(if avoid {
1545                GeomTextRepel::default().avoid_abline(1.0, 0.0)
1546            } else {
1547                GeomTextRepel::default()
1548            })
1549            .render_svg_native_with_size(400, 300)
1550            .unwrap()
1551        };
1552        let (with, without) = (render(true), render(false));
1553        assert_eq!(
1554            with.matches(">point ").count(),
1555            without.matches(">point ").count(),
1556            "no label dropped"
1557        );
1558        assert_ne!(with, without, "the line moved the labels");
1559    }
1560}