1use 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#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
37pub enum RepelDirection {
38 #[default]
40 Both,
41 X,
43 Y,
45 Down,
50}
51
52#[derive(Clone, Debug)]
54pub struct RepelParams {
55 pub box_padding: f64,
58 pub point_padding: f64,
61 pub point_size: f64,
64 pub nudge_x: f64,
66 pub nudge_y: f64,
68 pub force: f64,
70 pub force_pull: f64,
72 pub max_iter: usize,
74 pub max_time: std::time::Duration,
78 pub max_overlaps: usize,
81 pub min_segment_length: f64,
84 pub seed: u64,
86 pub direction: RepelDirection,
88 pub hjust: f64,
92 pub vjust: f64,
94 pub bg_colour: Option<(u8, u8, u8)>,
97 pub bg_r: f64,
99 pub max_labels: usize,
102 pub segment_color: Option<(u8, u8, u8)>,
104 pub segment_width: f64,
106 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 pub fn box_padding(mut self, px: f64) -> Self {
145 self.repel.box_padding = px;
146 self
147 }
148 pub fn point_padding(mut self, px: f64) -> Self {
150 self.repel.point_padding = px;
151 self
152 }
153 pub fn point_size(mut self, px: f64) -> Self {
155 self.repel.point_size = px;
156 self
157 }
158 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 pub fn force(mut self, force: f64) -> Self {
166 self.repel.force = force;
167 self
168 }
169 pub fn force_pull(mut self, force: f64) -> Self {
171 self.repel.force_pull = force;
172 self
173 }
174 pub fn max_iter(mut self, n: usize) -> Self {
176 self.repel.max_iter = n;
177 self
178 }
179 pub fn max_time(mut self, t: std::time::Duration) -> Self {
181 self.repel.max_time = t;
182 self
183 }
184 pub fn max_overlaps(mut self, n: usize) -> Self {
186 self.repel.max_overlaps = n;
187 self
188 }
189 pub fn min_segment_length(mut self, px: f64) -> Self {
191 self.repel.min_segment_length = px;
192 self
193 }
194 pub fn seed(mut self, seed: u64) -> Self {
196 self.repel.seed = seed;
197 self
198 }
199 pub fn direction(mut self, d: RepelDirection) -> Self {
201 self.repel.direction = d;
202 self
203 }
204 pub fn justify(mut self, hjust: f64, vjust: f64) -> Self {
207 self.repel.hjust = hjust;
208 self.repel.vjust = vjust;
209 self
210 }
211 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 pub fn max_labels(mut self, n: usize) -> Self {
219 self.repel.max_labels = n;
220 self
221 }
222 pub fn avoid_abline(mut self, slope: f64, intercept: f64) -> Self {
225 self.repel.avoid_ablines.push((slope, intercept));
226 self
227 }
228 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
237pub 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
262pub struct GeomLabelRepel {
265 pub size: f64,
266 pub color: (u8, u8, u8),
267 pub fill: (u8, u8, u8),
268 pub alpha: f64,
269 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#[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 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 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
322pub(crate) struct RepelLayout {
325 boxes: Vec<LabelBox>,
326 kept: Vec<bool>,
327 dropped: usize,
328 capped: bool,
330}
331
332#[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
347fn 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
374pub(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 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 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 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 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 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 let pull_until = p.max_iter - p.max_iter / 4;
505 let max_step = 12.0;
508 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 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 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 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 let label_hit = if final_phase { hit.clone() } else { Vec::new() };
590 let free = |i: usize| !final_phase || !label_hit[i];
591
592 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 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 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 let mut moved = 0.0f64;
698 for i in 0..n {
699 let b = &mut boxes[i];
700 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 if let Some((_, b)) = best {
733 boxes = b;
734 }
735 }
736
737 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 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
774fn 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
783type Seg = ((f64, f64), (f64, f64));
785
786struct Item {
788 row: usize,
789 anchor: (f64, f64),
790 target: (f64, f64),
791 text: String,
792}
793
794#[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 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 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 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 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 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 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 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 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 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 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 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 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 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}