2bc41aeb8602
bridge.rs
//! Smooth Bridge: two circles joined into one outline by two concave arcs, each touching both
//! circles from outside, so the outline runs on smoothly from each circle into the bridge; and
//! many circles joined at once, each to the others within reach ([`bridge_many`]).
use std::collections::{BTreeMap, HashMap, HashSet};
use std::f64::consts::{FRAC_PI_2, PI, SQRT_2, TAU};
use kurbo::{CubicBez, ParamCurve, Point, Shape, Vec2};
use vectorcraft_geom::{Anchor, AnchorKind, FillRule, PathData, SubPath, shapes};
use crate::boolean::{DEFAULT_PRECISION, try_unite_all_with};
use super::Circle;
/// How far (as a share of the radius) a path's outline may stray from a circle and still be read
/// as that circle.
const ROUND: f64 = 1e-3;
/// Points [`circle_of`] checks on each segment, its ends included.
const SAMPLES: usize = 9;
/// Why [`smooth_bridge`] makes no outline.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum BridgeError {
/// One circle is inside the other (or they share a center).
Inside,
/// The circles are too far apart for the radius: the two arcs would not reach both circles,
/// or would cross before they do.
TooFar,
/// A radius or circle that is not a finite size above 0, or an outline too large for `f64`.
Bad,
}
/// The circle `path` draws: one closed subpath whose outline stays within 0.1% of its radius of
/// a circle all the way around, once. `None` for any other path.
pub fn circle_of(path: &PathData) -> Option<Circle> {
let [sp] = path.subpaths.as_slice() else { return None };
if !sp.closed || sp.anchors.len() < 2 {
return None;
}
let b = path.bounds()?;
let (w, h) = (b.width(), b.height());
if !(w > 0.0 && h > 0.0 && w.is_finite() && h.is_finite()) || (w - h).abs() > ROUND * w.max(h) {
return None;
}
let (center, radius) = (b.center(), (w + h) / 4.0);
let off = |q: Point| (q.distance(center) - radius).abs() > ROUND * radius;
for k in 0..sp.segment_count() {
let seg = sp.segment(k);
if (0..SAMPLES).any(|i| off(seg.eval(i as f64 / (SAMPLES - 1) as f64))) {
return None;
}
}
// Around once: a path going around twice, or back on itself, encloses a different area.
let area = path.to_bezpath().area().abs();
((area - PI * radius * radius).abs() <= 4.0 * ROUND * area).then_some(Circle { center, radius })
}
/// The outline of circles `a` and `b` joined by two arcs of radius `radius` (pt), one on each
/// side of the line through their centers, each touching both circles from outside. The outline
/// runs around `a` on its side away from `b`, along one arc, around `b` on its side away from `a`
/// and back along the other arc; every anchor is smooth, as each arc and the circle it meets share
/// a tangent there. Overlapping and touching circles are joined too. A larger radius makes a wider,
/// gentler bridge; farther apart circles make a narrower one, until the arcs would cross.
pub fn smooth_bridge(a: Circle, b: Circle, radius: f64) -> Result<SubPath, BridgeError> {
let t = touches(a, b, radius)?;
let mut segs = vec![];
arc(&mut segs, a.center, a.radius, t.a1, t.a2, Some(-t.u));
arc(&mut segs, t.p2, radius, t.a2, t.b2, None);
arc(&mut segs, b.center, b.radius, t.b2, t.b1, Some(t.u));
arc(&mut segs, t.p1, radius, t.b1, t.a1, None);
closed(&segs, AnchorKind::Smooth)
}
/// The part of [`smooth_bridge`]'s outline between the circles: the two arcs, joined across each
/// circle by a straight line between the arc ends on it. Each line lies inside its circle, so the
/// two circles and this shape unite into the outline, with each circle drawn once however many
/// bridges it has.
fn neck(a: Circle, b: Circle, radius: f64) -> Result<SubPath, BridgeError> {
let t = touches(a, b, radius)?;
let line = |p: Point, q: Point| CubicBez::new(p, p, q, q);
let mut segs = vec![];
arc(&mut segs, t.p2, radius, t.a2, t.b2, None);
segs.push(line(t.b2, t.b1));
arc(&mut segs, t.p1, radius, t.b1, t.a1, None);
segs.push(line(t.a1, t.a2));
closed(&segs, AnchorKind::Corner)
}
/// A closed subpath through the cubics `segs`, each starting where the one before it ends, with
/// anchors of `kind`; [`BridgeError::Bad`] when a point does not fit in `f64`.
fn closed(segs: &[CubicBez], kind: AnchorKind) -> Result<SubPath, BridgeError> {
let count = segs.len();
let anchors: Vec<Anchor> = (0..count)
.filter_map(|i| {
let (prev, seg) = (segs.get((i + count - 1) % count)?, segs.get(i)?);
Some(Anchor { p: seg.p0, h_in: prev.p2, h_out: seg.p1, kind })
})
.collect();
let finite_point = |p: Point| p.x.is_finite() && p.y.is_finite();
if !anchors.iter().all(|q| finite_point(q.p) && finite_point(q.h_in) && finite_point(q.h_out)) {
return Err(BridgeError::Bad);
}
Ok(SubPath::new(anchors, true))
}
/// Where the arcs of radius `radius` that bridge circles `a` and `b` lie: the unit vector from
/// `a`'s center to `b`'s, and on each side the arc's center (`p1`, `p2`) and where it touches `a`
/// and `b`; and the neck's width where the arcs come nearest each other between the circles
/// (infinite when that is at the circles).
struct Touches {
waist: f64,
u: Vec2,
p1: Point,
a1: Point,
b1: Point,
p2: Point,
a2: Point,
b2: Point,
}
/// The arcs of [`smooth_bridge`], or why there are none.
fn touches(a: Circle, b: Circle, radius: f64) -> Result<Touches, BridgeError> {
let finite = |x: f64| x.is_finite() && x > 0.0;
let points = [a.center, b.center].iter().all(|c| c.x.is_finite() && c.y.is_finite());
if !finite(radius) || !finite(a.radius) || !finite(b.radius) || !points {
return Err(BridgeError::Bad);
}
let axis = b.center - a.center;
// `f64::hypot`: `Vec2::hypot` squares the length, which overflows above about 1e154 pt.
let d = axis.x.hypot(axis.y);
if d + a.radius.min(b.radius) <= a.radius.max(b.radius) * (1.0 + 1e-9) {
return Err(BridgeError::Inside);
}
// The arcs' centers are `radius` outside both circles: where circles about the two centers,
// `radius` larger than each, cross.
let (ra, rb) = (radius + a.radius, radius + b.radius);
if !ra.is_finite() || !rb.is_finite() {
return Err(BridgeError::Bad);
}
// Halves and no squares, so no step overflows while the lengths fit in `f64`.
let half = ra / 2.0 + rb / 2.0;
if d / 2.0 > half {
return Err(BridgeError::TooFar);
}
let along = d / 2.0 + (ra - rb) / d * half;
let across = (ra - along).max(0.0).sqrt() * (ra / 2.0 + along / 2.0).max(0.0).sqrt() * SQRT_2;
if !along.is_finite() || !across.is_finite() {
return Err(BridgeError::Bad);
}
// Each arc runs between its points on `a` and `b`, which lie towards the two centers from the
// arc's center. Its point nearest the axis is the foot of its center on the axis when that foot
// is between the two centers, else one of its ends, which are off the axis. So the two arcs
// cross, leaving no neck, only when that foot is between the centers and nearer to the arc's
// center than its radius.
if along > 0.0 && along < d && across <= radius * (1.0 + 1e-9) {
return Err(BridgeError::TooFar);
}
let u = axis / d;
let n = Vec2::new(-u.y, u.x);
// Each side's arc center and where its arc touches `a` and `b`.
let side = |s: f64| {
let p = a.center + u * along + n * (s * across);
(p, a.center + (p - a.center) * (a.radius / ra), b.center + (p - b.center) * (b.radius / rb))
};
let ((p1, a1, b1), (p2, a2, b2)) = (side(1.0), side(-1.0));
let waist = if along > 0.0 && along < d { 2.0 * (across - radius) } else { f64::INFINITY };
Ok(Touches { waist, u, p1, a1, b1, p2, a2, b2 })
}
/// The most circles [`bridge_many`] takes.
pub const MAX_BRIDGED_CIRCLES: usize = 2000;
/// The most bridges [`bridge_many`] makes.
pub const MAX_BRIDGES: usize = 8000;
/// Holes [`bridge_many`] fills: those smaller than this share of the area of the smallest circle
/// they join.
const SPECK: f64 = 0.01;
/// The radius of the arcs that bridge two circles.
#[derive(Clone, Copy, Debug, PartialEq)]
pub enum ArcRadius {
/// This share of the smaller circle's radius (1 is the same radius).
Share(f64),
/// The smaller circle's radius plus this gap (pt). Each arc is then this gap outside a circle
/// of the smaller circle's radius about the arc's center: for equal circles that gap apart,
/// the place of a third circle that gap from both, as in a triangular grid.
Gap(f64),
}
impl ArcRadius {
/// The arcs' radius (pt) for circles `a` and `b`.
pub fn between(self, a: Circle, b: Circle) -> f64 {
let r = a.radius.min(b.radius);
match self {
ArcRadius::Share(share) => r * share,
ArcRadius::Gap(gap) => r + gap,
}
}
}
/// Circles that bridges join into one shape: their indices, ascending, and the shape's outline.
#[derive(Clone, Debug, PartialEq)]
pub struct Joined {
pub members: Vec<usize>,
pub outline: PathData,
}
/// What [`bridge_many`] makes: the joined shapes, in the order of their first member, and the
/// indices of the circles left alone, ascending.
#[derive(Clone, Debug, Default, PartialEq)]
pub struct Bridged {
pub joined: Vec<Joined>,
pub alone: Vec<usize>,
}
/// Why [`bridge_many`] makes nothing.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum ManyError {
/// More than [`MAX_BRIDGED_CIRCLES`] circles.
TooManyCircles,
/// More than [`MAX_BRIDGES`] pairs of circles to bridge: within reach, near enough for the
/// arcs and with a neck wide enough for the shape's precision. Also more than nine times as many
/// pairs within reach to check.
TooManyBridges,
/// No two circles are within reach of each other.
NoneInReach,
/// The circles at these indices are within reach but [`smooth_bridge`] can't join them: one is
/// inside the other, or no pair within reach is near enough for the arcs (the first such pair).
Pair(usize, usize, BridgeError),
/// A reach that is not a finite size of 0 or more, or a circle that is not a finite size above 0.
Bad,
/// A joined shape too complex to unite.
TooComplex,
}
/// Every pair of `circles` whose outlines are at most `reach` (pt) apart, overlapping ones
/// included, joined by a [`smooth_bridge`] with arcs of radius `arc`, and the bridges that connect
/// united into one shape each, without holes smaller than 1% of the smallest circle's area. A pair
/// too far apart for the arcs gets no bridge; a circle bridged to no other is left alone. One
/// circle inside another is an error, and so is no pair that the arcs can join.
pub fn bridge_many(circles: &[Circle], arc: ArcRadius, reach: f64) -> Result<Bridged, ManyError> {
let (pairs, too_far, roots, precision) = bridgeable(circles, arc, reach)?;
match (pairs.is_empty(), too_far) {
(true, Some((i, j))) => return Err(ManyError::Pair(i, j, BridgeError::TooFar)),
(true, None) => return Err(ManyError::NoneInReach),
(false, _) => {}
}
let mut necks = Vec::with_capacity(pairs.len());
for &((i, j), _) in &pairs {
let (a, b) = (circles[i], circles[j]);
let sp = neck(a, b, arc.between(a, b)).map_err(|e| ManyError::Pair(i, j, e))?;
necks.push(((i, j), PathData::single(sp)));
}
let mut sets: BTreeMap<usize, (Vec<usize>, Vec<&PathData>)> = BTreeMap::new();
for &((i, j), ref neck) in &necks {
let (members, parts) = sets.entry(roots[i]).or_default();
members.extend([i, j]);
parts.push(neck);
}
let mut out = Bridged::default();
for (set, (mut members, parts)) in sets {
members.sort_unstable();
members.dedup();
// Each circle once, and the necks between them.
let rounds: Vec<PathData> = members
.iter()
.filter_map(|&i| circles.get(i))
.map(|c| shapes::ellipse(kurbo::Rect::from_center_size(c.center, (2.0 * c.radius, 2.0 * c.radius))))
.collect();
let fills: Vec<(&PathData, FillRule)> = rounds.iter().chain(parts).map(|p| (p, FillRule::NonZero)).collect();
let smallest = members.iter().filter_map(|&i| circles.get(i)).map(|c| c.radius).fold(f64::INFINITY, f64::min);
let mut outline = try_unite_all_with(&fills, precision[set]).map_err(|_| ManyError::TooComplex)?;
// Where three bridges' arcs nearly meet, the union leaves a speck of a hole; a contour that
// encloses a circle is far larger than this.
let speck = SPECK * PI * smallest * smallest;
outline.subpaths.retain(|sp| PathData::single(sp.clone()).to_bezpath().area().abs() >= speck);
out.joined.push(Joined { members, outline });
}
let joined: HashSet<usize> = necks.iter().flat_map(|&((i, j), _)| [i, j]).collect();
out.alone = (0..circles.len()).filter(|i| !joined.contains(i)).collect();
Ok(out)
}
/// Whether [`bridge_many`] would bridge at least one pair of `circles` with arcs of `arc` and
/// `reach`, under the same rules (a neck too thin for its shape's precision included), without
/// making the bridges or uniting them.
pub fn bridges_any(circles: &[Circle], arc: ArcRadius, reach: f64) -> bool {
bridgeable(circles, arc, reach).is_ok_and(|(pairs, ..)| !pairs.is_empty())
}
/// What [`bridgeable`] finds: the pairs [`bridge_many`] bridges with their necks' widths, the
/// lowest pair within reach that it can't bridge, each circle's set (its lowest index) and each
/// set's precision, under its lowest index.
type Bridgeable = (Vec<(Pair, f64)>, Option<Pair>, Vec<usize>, Vec<f64>);
/// The pairs of `circles` that [`bridge_many`] bridges, and how it sorts them into sets.
fn bridgeable(circles: &[Circle], arc: ArcRadius, reach: f64) -> Result<Bridgeable, ManyError> {
if circles.len() > MAX_BRIDGED_CIRCLES {
return Err(ManyError::TooManyCircles);
}
let fine = |c: &Circle| c.center.x.is_finite() && c.center.y.is_finite() && c.radius.is_finite() && c.radius > 0.0;
if !(reach.is_finite() && reach >= 0.0) || !circles.iter().all(fine) {
return Err(ManyError::Bad);
}
let (mut pairs, mut too_far) = pairs_within(circles, reach, arc)?;
// Each set of connected circles, under its lowest index, is united at a precision fine enough
// for its smallest circle. A neck narrower than twice that would not survive the union, so its
// pair gets no bridge; that can split a set and make its precision coarser, so the sets are
// found again until no neck is dropped.
let (roots, precision) = loop {
let mut parent: Vec<usize> = (0..circles.len()).collect();
for &((i, j), _) in &pairs {
let (ri, rj) = (root(&mut parent, i), root(&mut parent, j));
parent[ri.max(rj)] = ri.min(rj);
}
let roots: Vec<usize> = (0..circles.len()).map(|i| root(&mut parent, i)).collect();
let mut precision = vec![DEFAULT_PRECISION; circles.len()];
for (&r, c) in roots.iter().zip(circles) {
precision[r] = precision[r].min(c.radius * 1e-3);
}
let thin = |&((i, _), waist): &(Pair, f64)| waist < 2.0 * precision[roots[i]];
if !pairs.iter().any(thin) {
break (roots, precision);
}
for &(pair, _) in pairs.iter().filter(|&p| thin(p)) {
too_far = Some(too_far.map_or(pair, |t| t.min(pair)));
}
pairs.retain(|p| !thin(p));
};
if pairs.len() > MAX_BRIDGES {
return Err(ManyError::TooManyBridges);
}
Ok((pairs, too_far, roots, precision))
}
/// Two circles' indices, the lower first.
type Pair = (usize, usize);
/// What [`pairs_within`] finds: the pairs the arcs can bridge, each with its neck's width, and the
/// lowest pair too far apart for them.
type Within = (Vec<(Pair, f64)>, Option<Pair>);
/// The set `i` is in: the lowest index in it, with the path to it shortened on the way.
fn root(parent: &mut [usize], mut i: usize) -> usize {
while parent[i] != i {
parent[i] = parent[parent[i]];
i = parent[i];
}
i
}
/// Every pair of indices `(i, j)`, `i < j`, ascending, of `circles` whose outlines are at most
/// `reach` apart and that arcs of `arc` can bridge, with the width of the neck between them, and
/// the lowest pair within reach that they can't because it is too far apart for them. Circles go
/// into a grid of cells as wide as the farthest two centers within reach can be, so each circle is
/// compared only with those in its own cell and the eight around it.
fn pairs_within(circles: &[Circle], reach: f64, arc: ArcRadius) -> Result<Within, ManyError> {
let biggest = circles.iter().map(|c| c.radius).fold(0.0, f64::max);
let cell = 2.0 * biggest + reach;
if !(cell.is_finite() && cell > 0.0) {
return Err(ManyError::Bad);
}
// Saturating casts: a cell beyond i64 shares the last one, which only adds comparisons.
let key = |p: Point| ((p.x / cell).floor() as i64, (p.y / cell).floor() as i64);
let mut grid: HashMap<(i64, i64), Vec<usize>> = HashMap::new();
for (i, c) in circles.iter().enumerate() {
grid.entry(key(c.center)).or_default().push(i);
}
let (mut pairs, mut too_far) = (vec![], None::<Pair>);
for (i, &c) in circles.iter().enumerate() {
let (x, y) = key(c.center);
for (dx, dy) in (-1..=1).flat_map(|dx| (-1..=1).map(move |dy| (dx, dy))) {
let Some(near) = grid.get(&(x.saturating_add(dx), y.saturating_add(dy))) else { continue };
for &j in near.iter().filter(|&&j| j > i) {
let o = circles[j];
if c.center.distance(o.center) - c.radius - o.radius > reach {
continue;
}
// Only the arcs' ends are worked out here; the bridge itself is made later.
match touches(c, o, arc.between(c, o)) {
Ok(t) => pairs.push(((i, j), t.waist)),
Err(BridgeError::TooFar) => too_far = Some(too_far.map_or((i, j), |t| t.min((i, j)))),
Err(e) => return Err(ManyError::Pair(i, j, e)),
}
}
}
// A bound on the work before thin necks are dropped; [`bridgeable`] holds the pairs left
// to [`MAX_BRIDGES`].
if pairs.len() > 9 * MAX_BRIDGES {
return Err(ManyError::TooManyBridges);
}
}
// Saturated cells can list a pair twice.
pairs.sort_unstable_by_key(|&(pair, _)| pair);
pairs.dedup_by_key(|&mut (pair, _)| pair);
Ok((pairs, too_far))
}
/// Append to `out` the arc of the circle about `center` with radius `r` from `from` to `to` (both
/// on it): through the direction `through` from the center when given, else the shorter way. In
/// cubics of at most a quarter turn each, `from` exactly at the start and `to` at the end.
fn arc(out: &mut Vec<CubicBez>, center: Point, r: f64, from: Point, to: Point, through: Option<Vec2>) {
let angle = |q: Vec2| q.y.atan2(q.x);
let start = angle(from - center);
// The turn from `from` to `to` counter-clockwise (in the y-up sense), 0 to 2π.
let ccw = (angle(to - center) - start).rem_euclid(TAU);
let sweep = match through {
Some(dir) if (angle(dir) - start).rem_euclid(TAU) <= ccw => ccw,
Some(_) => ccw - TAU,
None if ccw > PI => ccw - TAU,
None => ccw,
};
let pieces = (sweep.abs() / FRAC_PI_2).ceil().max(1.0) as usize;
let step = sweep / pieces as f64;
// Handle length that makes a cubic follow the arc of `step`, signed with its direction.
let k = 4.0 / 3.0 * (step / 4.0).tan() * r;
let on = |t: f64| center + Vec2::new(t.cos(), t.sin()) * r;
let tangent = |t: f64| Vec2::new(-t.sin(), t.cos());
for i in 0..pieces {
let (t0, t1) = (start + step * i as f64, start + step * (i + 1) as f64);
let p0 = if i == 0 { from } else { on(t0) };
let p3 = if i + 1 == pieces { to } else { on(t1) };
out.push(CubicBez::new(p0, p0 + tangent(t0) * k, p3 - tangent(t1) * k, p3));
}
}
#[cfg(test)]
mod tests {
use vectorcraft_geom::shapes;
use super::*;
fn circle(x: f64, y: f64, r: f64) -> Circle {
Circle { center: Point::new(x, y), radius: r }
}
/// Every point the outline passes through, 32 to a segment.
fn outline(sp: &SubPath) -> Vec<Point> {
(0..sp.segment_count()).flat_map(|k| (0..32).map(move |i| sp.segment(k).eval(i as f64 / 32.0))).collect()
}
/// The outline crosses the vertical line at `x` at these y values, top to bottom.
fn crossings_at(sp: &SubPath, x: f64) -> Vec<f64> {
let pts = outline(sp);
let mut ys: Vec<f64> = (0..pts.len())
.filter_map(|i| {
let (p, q) = (pts[i], pts[(i + 1) % pts.len()]);
((p.x - x) * (q.x - x) <= 0.0 && p.x != q.x).then(|| p.y + (q.y - p.y) * (x - p.x) / (q.x - p.x))
})
.collect();
ys.sort_by(f64::total_cmp);
ys
}
/// The bridge's width at `x`, from the outline's crossings there.
fn width_at(sp: &SubPath, x: f64) -> f64 {
let ys = crossings_at(sp, x);
ys.last().unwrap() - ys.first().unwrap()
}
fn assert_smooth(sp: &SubPath) {
for a in sp.anchors.iter() {
let (i, o) = (a.p - a.h_in, a.h_out - a.p);
assert!(i.hypot() > 1e-6 && o.hypot() > 1e-6, "both handles at {a:?}");
assert!(i.cross(o).abs() <= 1e-9 * i.hypot() * o.hypot() && i.dot(o) > 0.0, "the outline turns at {a:?}");
assert_eq!(a.kind, AnchorKind::Smooth);
}
}
/// Each point of the outline is on circle `c` or outside it.
fn outside(sp: &SubPath, c: Circle) -> bool {
outline(sp).iter().all(|p| p.distance(c.center) >= c.radius - 1e-3)
}
#[test]
fn two_equal_circles_join_with_a_neck_narrower_than_the_circles() {
let (a, b) = (circle(0.0, 0.0, 20.0), circle(60.0, 0.0, 20.0));
let sp = smooth_bridge(a, b, 20.0).unwrap();
assert!(sp.closed);
assert_smooth(&sp);
// The arcs' centers are 40 from each circle's center: (30, ±√700), so the neck at x = 30 is
// 2 × (√700 − 20) wide.
let neck = 2.0 * (700f64.sqrt() - 20.0);
assert!((width_at(&sp, 30.0) - neck).abs() < 1e-2, "{}", width_at(&sp, 30.0));
assert!(width_at(&sp, 30.0) < width_at(&sp, 10.0));
// Around each circle on its far side, and symmetric.
let ys = crossings_at(&sp, -10.0);
assert!((ys[0] + 300f64.sqrt()).abs() < 1e-2 && (ys[1] - 300f64.sqrt()).abs() < 1e-2, "{ys:?}");
assert!((width_at(&sp, 50.0) - width_at(&sp, 10.0)).abs() < 1e-2);
let b = PathData::single(sp).bounds().unwrap();
// Within the cubics' own error from a true circle (about 0.03% of the radius).
assert!((b.x0 + 20.0).abs() < 1e-2 && (b.x1 - 80.0).abs() < 1e-2 && (b.y1 - 20.0).abs() < 1e-2, "{b:?}");
}
#[test]
fn the_arcs_touch_both_circles_and_run_on_from_them() {
for (a, b, r) in [
(circle(0.0, 0.0, 20.0), circle(60.0, 0.0, 20.0), 20.0),
(circle(10.0, 5.0, 30.0), circle(70.0, 40.0, 8.0), 40.0),
(circle(0.0, 0.0, 20.0), circle(30.0, 0.0, 15.0), 10.0),
] {
let sp = smooth_bridge(a, b, r).unwrap();
assert_smooth(&sp);
// The outline goes around the outside of both circles, never into either.
assert!(outside(&sp, a) && outside(&sp, b));
// On each circle the outline leaves along the circle's tangent, where an arc takes over
// as well: two anchors on each circle are where an arc meets it.
for c in [a, b] {
let on: Vec<_> = sp.anchors.iter().filter(|q| (q.p.distance(c.center) - c.radius).abs() < 1e-6).collect();
assert!(on.len() >= 2, "{}", on.len());
for q in on {
let radial = q.p - c.center;
assert!(radial.dot(q.h_out - q.p).abs() <= 1e-6 * radial.hypot() * (q.h_out - q.p).hypot(), "{q:?}");
}
}
assert!(sp.anchors.len() <= 12, "{}", sp.anchors.len());
// Every segment off the two circles is part of an arc of radius `r` that touches both
// circles from outside: its center is `r` farther than each circle's radius from it.
let on = |q: Point, c: Circle| (q.distance(c.center) - c.radius).abs() < 1e-3;
let mut arcs = 0;
for k in 0..sp.segment_count() {
let seg = sp.segment(k);
let (p0, pm, p1) = (seg.eval(0.0), seg.eval(0.5), seg.eval(1.0));
if on(pm, a) || on(pm, b) {
continue;
}
arcs += 1;
let (center, radius) = circumcircle(p0, pm, p1);
assert!((radius - r).abs() < 1e-2 * r, "radius {radius} for {r}");
assert!((center.distance(a.center) - (r + a.radius)).abs() < 1e-2 * r, "touches {a:?}");
assert!((center.distance(b.center) - (r + b.radius)).abs() < 1e-2 * r, "touches {b:?}");
}
assert!((2..=4).contains(&arcs), "{arcs}");
}
}
/// The circle through three points: its center and radius.
fn circumcircle(p: Point, q: Point, s: Point) -> (Point, f64) {
let d = 2.0 * (p.x * (q.y - s.y) + q.x * (s.y - p.y) + s.x * (p.y - q.y));
let sq = |v: Point| v.x * v.x + v.y * v.y;
let x = (sq(p) * (q.y - s.y) + sq(q) * (s.y - p.y) + sq(s) * (p.y - q.y)) / d;
let y = (sq(p) * (s.x - q.x) + sq(q) * (p.x - s.x) + sq(s) * (q.x - p.x)) / d;
let c = Point::new(x, y);
(c, c.distance(p))
}
#[test]
fn unequal_circles_join_round_both() {
let (a, b) = (circle(0.0, 0.0, 30.0), circle(70.0, 0.0, 10.0));
let sp = smooth_bridge(a, b, 40.0).unwrap();
assert_smooth(&sp);
let bounds = PathData::single(sp.clone()).bounds().unwrap();
assert!((bounds.x0 + 30.0).abs() < 1e-2 && (bounds.x1 - 80.0).abs() < 1e-2 && (bounds.y0 + 30.0).abs() < 1e-2, "{bounds:?}");
// The neck narrows from the big circle towards the small one.
assert!(width_at(&sp, 35.0) > width_at(&sp, 50.0));
assert!(width_at(&sp, 50.0) < 20.0);
}
#[test]
fn unequal_circles_join_at_large_radii_overlapping_or_not() {
// With a large radius the arcs' centers lie beyond the smaller circle, so the arcs never
// reach the axis even though their centers are nearer to it than their radius.
for (a, b, r) in [
(circle(0.0, 0.0, 10.0), circle(25.0, 0.0, 30.0), 100.0),
(circle(0.0, 0.0, 30.0), circle(25.0, 0.0, 10.0), 30.0),
(circle(0.0, 0.0, 30.0), circle(25.0, 0.0, 10.0), 50.0),
(circle(0.0, 0.0, 30.0), circle(60.0, 0.0, 8.0), 300.0),
] {
let sp = smooth_bridge(a, b, r).unwrap_or_else(|e| panic!("{a:?} {b:?} {r}: {e:?}"));
assert_smooth(&sp);
assert!(outside(&sp, a) && outside(&sp, b));
// The outline crosses the axis only at the two far ends: it does not cross itself.
let pts = outline(&sp);
let crossings = (0..pts.len()).filter(|&i| (pts[i].y > 0.0) != (pts[(i + 1) % pts.len()].y > 0.0)).count();
assert_eq!(crossings, 2, "{a:?} {b:?} {r}");
// It encloses more than the larger circle.
let area = PathData::single(sp).to_bezpath().area().abs();
assert!(area > PI * a.radius.max(b.radius).powi(2), "{area}");
}
}
#[test]
fn overlapping_and_touching_circles_are_joined() {
let (a, b) = (circle(0.0, 0.0, 20.0), circle(30.0, 0.0, 20.0));
let sp = smooth_bridge(a, b, 10.0).unwrap();
assert_smooth(&sp);
// The circles cross at x = 15, y = ±√175; the bridge fills in the notch there.
assert!(width_at(&sp, 15.0) > 2.0 * 175f64.sqrt());
assert!(width_at(&sp, 15.0) < 40.0);
let touching = smooth_bridge(circle(0.0, 0.0, 20.0), circle(40.0, 0.0, 20.0), 10.0).unwrap();
assert_smooth(&touching);
assert!(width_at(&touching, 20.0) > 1.0);
}
#[test]
fn far_apart_circles_and_nested_ones_make_no_bridge() {
let (a, b) = (circle(0.0, 0.0, 10.0), circle(100.0, 0.0, 10.0));
assert_eq!(smooth_bridge(a, b, 5.0), Err(BridgeError::TooFar), "arcs don't reach");
// The arcs reach both circles (gap 80 < 2 × 45) but cross before they do.
assert_eq!(smooth_bridge(a, b, 45.0), Err(BridgeError::TooFar), "no neck left");
// A large enough radius bridges them: the neck stays open above (d/2)² − r² over 2r = 120.
assert!(smooth_bridge(a, b, 130.0).is_ok());
assert_eq!(smooth_bridge(circle(0.0, 0.0, 30.0), circle(5.0, 0.0, 10.0), 10.0), Err(BridgeError::Inside));
assert_eq!(smooth_bridge(circle(0.0, 0.0, 30.0), circle(0.0, 0.0, 30.0), 10.0), Err(BridgeError::Inside));
assert_eq!(smooth_bridge(a, b, 0.0), Err(BridgeError::Bad));
assert_eq!(smooth_bridge(a, b, f64::NAN), Err(BridgeError::Bad));
assert_eq!(smooth_bridge(circle(f64::INFINITY, 0.0, 10.0), b, 10.0), Err(BridgeError::Bad));
}
/// A 3 × 3 grid of circles of radius 10, 4 apart (centers 24 apart), top-left at the origin.
fn grid() -> Vec<Circle> {
(0..9).map(|k| circle(24.0 * (k % 3) as f64, 24.0 * (k / 3) as f64, 10.0)).collect()
}
fn area(path: &PathData) -> f64 {
crate::area(path, FillRule::NonZero)
}
fn inside(path: &PathData, x: f64, y: f64) -> bool {
path.to_bezpath().winding(Point::new(x, y)) != 0
}
#[test]
fn a_grid_joins_each_circle_to_its_neighbors_within_reach() {
// Reach 5: the side neighbors (4 apart) are joined, the diagonal ones (about 13.9 apart) not.
let b = bridge_many(&grid(), ArcRadius::Gap(4.0), 5.0).unwrap();
assert_eq!(b.alone, Vec::<usize>::new());
let [one] = b.joined.as_slice() else { panic!("{} shapes", b.joined.len()) };
assert_eq!(one.members, (0..9).collect::<Vec<_>>());
for (x, y) in [(12.0, 0.0), (0.0, 12.0), (36.0, 48.0), (48.0, 36.0), (24.0, 24.0)] {
assert!(inside(&one.outline, x, y), "bridged at ({x}, {y})");
}
// Between four circles the side bridges' arcs leave a hole: no diagonal bridge fills it.
for (x, y) in [(12.0, 12.0), (36.0, 36.0)] {
assert!(!inside(&one.outline, x, y), "a hole at ({x}, {y})");
}
let hull = PathData::single(SubPath::polyline(
&[Point::new(-10.0, -10.0), Point::new(58.0, -10.0), Point::new(58.0, 58.0), Point::new(-10.0, 58.0)],
true,
));
assert!(area(&one.outline) < area(&hull));
assert_eq!(one.outline.subpaths.len(), 5, "the outline and a hole in each square");
// Reach 15 takes in the diagonal neighbors too, and their bridges fill the middle of each
// square. The specks of holes (about 0.1 pt²) where side and diagonal arcs nearly meet are
// filled.
let b = bridge_many(&grid(), ArcRadius::Gap(4.0), 15.0).unwrap();
let [one] = b.joined.as_slice() else { panic!("{} shapes", b.joined.len()) };
assert!(inside(&one.outline, 12.0, 12.0) && inside(&one.outline, 36.0, 36.0));
assert_eq!(one.outline.subpaths.len(), 1);
}
#[test]
fn a_circle_with_no_neighbor_in_reach_is_left_alone() {
let mut circles = grid();
circles.truncate(2);
circles.push(circle(200.0, 0.0, 10.0));
circles.push(circle(224.0, 0.0, 10.0));
circles.push(circle(100.0, 100.0, 10.0));
let b = bridge_many(&circles, ArcRadius::Share(1.0), 5.0).unwrap();
assert_eq!(b.joined.iter().map(|j| j.members.clone()).collect::<Vec<_>>(), [vec![0, 1], vec![2, 3]]);
assert_eq!(b.alone, [4]);
// Each pair alone is the two-circle bridge.
let two = smooth_bridge(circles[0], circles[1], 10.0).unwrap();
let (got, want) = (area(&b.joined[0].outline), area(&PathData::single(two)));
assert!((got - want).abs() < 1e-3 * want, "{got} {want}");
}
#[test]
fn a_ring_around_an_empty_place_leaves_a_round_hole_the_gap_wider_than_a_circle() {
// Six circles of radius 10 around an empty place at the origin, each 4 from its two
// neighbors and from where a seventh circle would be (centers 24 from the origin).
let ring: Vec<Circle> = (0..6).map(|k| f64::from(k) * PI / 3.0).map(|t| circle(24.0 * t.cos(), 24.0 * t.sin(), 10.0)).collect();
let b = bridge_many(&ring, ArcRadius::Gap(4.0), 5.0).unwrap();
let [one] = b.joined.as_slice() else { panic!("{} shapes", b.joined.len()) };
assert_eq!(one.members, (0..6).collect::<Vec<_>>());
assert_eq!(one.outline.subpaths.len(), 2, "the outline and the hole");
// The hole's edge is 14 from the origin all the way round: a circle of radius 10 there
// would be 4 from the shape everywhere, the same as from each of the six.
let hole = one.outline.subpaths.iter().min_by(|p, q| {
let size = |sp: &SubPath| PathData::single(sp.clone()).to_bezpath().area().abs();
size(p).total_cmp(&size(q))
});
let edge = outline(hole.unwrap());
let (near, far) = edge.iter().map(|p| p.distance(Point::ZERO)).fold((f64::INFINITY, 0.0f64), |(n, f), d| (n.min(d), f.max(d)));
assert!((near - 14.0).abs() < 1e-2 && (far - 14.0).abs() < 1e-2, "{near} to {far}");
}
#[test]
fn many_circles_make_the_two_circle_outline_for_each_pair() {
// Overlapping, touching, unequal and unequal overlapping pairs, each with a far circle.
for (a, b, share) in [
(circle(0.0, 0.0, 20.0), circle(30.0, 0.0, 20.0), 0.5),
(circle(0.0, 0.0, 20.0), circle(40.0, 0.0, 20.0), 0.5),
(circle(0.0, 0.0, 30.0), circle(70.0, 0.0, 10.0), 4.0),
(circle(0.0, 0.0, 10.0), circle(25.0, 0.0, 30.0), 10.0),
// Circles far smaller than the union's usual precision (0.01 pt).
(circle(0.0, 0.0, 0.004), circle(0.01, 0.0, 0.004), 1.0),
] {
let made = bridge_many(&[a, b, circle(1000.0, 0.0, 5.0)], ArcRadius::Share(share), 40.0).unwrap();
assert_eq!(made.alone, [2]);
let two = smooth_bridge(a, b, share * a.radius.min(b.radius)).unwrap();
let (got, want) = (area(&made.joined[0].outline), area(&PathData::single(two)));
assert!((got - want).abs() < 1e-3 * want, "{a:?}: {got} {want}");
}
}
#[test]
fn a_pair_too_far_apart_for_the_arcs_gets_no_bridge() {
// b and c are within reach (6 apart) but arcs of radius 3 close before they reach both.
let (a, b, c) = (circle(0.0, 0.0, 3.0), circle(8.0, 0.0, 3.0), circle(20.0, 0.0, 3.0));
assert_eq!(smooth_bridge(b, c, 3.0), Err(BridgeError::TooFar));
let made = bridge_many(&[a, b, c], ArcRadius::Share(1.0), 10.0).unwrap();
assert_eq!(made.joined.iter().map(|j| j.members.clone()).collect::<Vec<_>>(), [vec![0, 1]]);
assert_eq!(made.alone, [2]);
// Arcs of radius 10 between circles of radius 10 just under 20√3 apart leave a neck about
// 0.00003 pt wide, too thin for the union: that pair is left unbridged too.
let (a, b, c) = (circle(0.0, 0.0, 10.0), circle(34.6409, 0.0, 10.0), circle(58.6409, 0.0, 10.0));
assert!(smooth_bridge(a, b, 10.0).is_ok(), "two circles alone are bridged");
let made = bridge_many(&[a, b, c], ArcRadius::Share(1.0), 20.0).unwrap();
assert_eq!(made.joined.iter().map(|j| j.members.clone()).collect::<Vec<_>>(), [vec![1, 2]]);
assert_eq!(made.alone, [0]);
// Two tiny circles far off are united at a finer precision, which does not change that.
let tiny = [circle(500.0, 0.0, 0.01), circle(500.025, 0.0, 0.01)];
let made = bridge_many(&[a, b, c, tiny[0], tiny[1]], ArcRadius::Share(1.0), 20.0).unwrap();
assert_eq!(made.joined.iter().map(|j| j.members.clone()).collect::<Vec<_>>(), [vec![1, 2], vec![3, 4]]);
assert_eq!(made.alone, [0]);
// 260 touching circles in a row with a wide reach: 33,670 pairs within reach, far more than
// the bridge limit, but only the 259 touching pairs are near enough for the arcs.
let row: Vec<Circle> = (0..260).map(|i| circle(f64::from(i) * 20.0, 0.0, 10.0)).collect();
let made = bridge_many(&row, ArcRadius::Share(1.0), 6000.0).unwrap();
let [one] = made.joined.as_slice() else { panic!("{} shapes", made.joined.len()) };
assert_eq!(one.members.len(), 260);
assert!(made.alone.is_empty());
}
#[test]
fn the_gap_form_keeps_the_gap_from_a_circle_at_each_arcs_center() {
// Two circles 4 apart; with a gap of 4 each arc's center is 24 from both centers, where a
// third circle of the same size is 4 from both (as in a triangular grid).
let (a, b) = (circle(0.0, 0.0, 10.0), circle(24.0, 0.0, 10.0));
let r = ArcRadius::Gap(4.0).between(a, b);
assert_eq!(r, 14.0);
let sp = smooth_bridge(a, b, r).unwrap();
for third in [circle(12.0, 432f64.sqrt(), 10.0), circle(12.0, -(432f64.sqrt()), 10.0)] {
let gaps: Vec<f64> = outline(&sp).iter().map(|p| p.distance(third.center) - third.radius).collect();
// No part of the bridge comes nearer than the gap, and a stretch of it is that gap away.
assert!(gaps.iter().all(|&g| g > 4.0 - 1e-2), "{:?}", gaps.iter().copied().fold(f64::INFINITY, f64::min));
let along = gaps.iter().filter(|&&g| (g - 4.0).abs() < 1e-2).count();
assert!(along >= 32, "{along}");
}
// The same for unequal circles: the gap is kept from a circle of the smaller one's size.
let (a, b) = (circle(0.0, 0.0, 15.0), circle(30.0, 5.0, 8.0));
let r = ArcRadius::Gap(3.0).between(a, b);
let sp = smooth_bridge(a, b, r).unwrap();
let d = (b.center - a.center).hypot();
let (ra, rb) = (15.0 + r, 8.0 + r);
let along = (d * d + ra * ra - rb * rb) / (2.0 * d);
let u = (b.center - a.center) / d;
let center = a.center + u * along + Vec2::new(-u.y, u.x) * (ra * ra - along * along).sqrt();
let gaps: Vec<f64> = outline(&sp).iter().map(|p| p.distance(center) - 8.0).collect();
assert!(gaps.iter().all(|&g| g > 3.0 - 1e-2) && gaps.iter().filter(|&&g| (g - 3.0).abs() < 1e-2).count() >= 16);
}
#[test]
fn the_gap_form_is_the_percentage_form_of_the_radius_plus_the_gap() {
for (a, b, gap) in [(circle(0.0, 0.0, 10.0), circle(24.0, 0.0, 10.0), 4.0), (circle(0.0, 0.0, 20.0), circle(40.0, 30.0, 10.0), 7.5)] {
let small = a.radius.min(b.radius);
let share = ArcRadius::Share((small + gap) / small);
assert!((ArcRadius::Gap(gap).between(a, b) - share.between(a, b)).abs() < 1e-12);
let (g, s) = (smooth_bridge(a, b, ArcRadius::Gap(gap).between(a, b)).unwrap(), smooth_bridge(a, b, share.between(a, b)).unwrap());
for (p, q) in g.anchors.iter().zip(&s.anchors) {
assert!(p.p.distance(q.p) < 1e-9 && p.h_in.distance(q.h_in) < 1e-9 && p.h_out.distance(q.h_out) < 1e-9);
}
assert_eq!(g.anchors.len(), s.anchors.len());
}
// Over a grid the two forms make the same shape too.
let by_gap = bridge_many(&grid(), ArcRadius::Gap(4.0), 5.0).unwrap();
let by_share = bridge_many(&grid(), ArcRadius::Share(1.4), 5.0).unwrap();
let (g, s) = (area(&by_gap.joined[0].outline), area(&by_share.joined[0].outline));
assert!((g - s).abs() < 1e-6 * g, "{g} {s}");
}
#[test]
fn too_many_circles_or_bridges_and_bad_pairs_are_refused() {
let many = vec![circle(0.0, 0.0, 1.0); MAX_BRIDGED_CIRCLES + 1];
assert_eq!(bridge_many(&many, ArcRadius::Share(1.0), 1.0), Err(ManyError::TooManyCircles));
// 200 circles in a tight row: 19,900 pairs within reach.
let row: Vec<Circle> = (0..200).map(|i| circle(i as f64 * 0.1, 0.0, 10.0)).collect();
assert_eq!(bridge_many(&row, ArcRadius::Share(1.0), 1.0), Err(ManyError::TooManyBridges));
let spread: Vec<Circle> = (0..3).map(|i| circle(i as f64 * 100.0, 0.0, 10.0)).collect();
assert_eq!(bridge_many(&spread, ArcRadius::Share(1.0), 5.0), Err(ManyError::NoneInReach));
let nested = [circle(0.0, 0.0, 30.0), circle(5.0, 0.0, 10.0), circle(200.0, 0.0, 10.0)];
assert_eq!(bridge_many(&nested, ArcRadius::Share(1.0), 5.0), Err(ManyError::Pair(0, 1, BridgeError::Inside)));
// Within reach (40 apart) but too far for arcs of radius 1.
let far = [circle(0.0, 0.0, 10.0), circle(60.0, 0.0, 10.0), circle(300.0, 0.0, 10.0)];
assert_eq!(bridge_many(&far, ArcRadius::Share(0.1), 50.0), Err(ManyError::Pair(0, 1, BridgeError::TooFar)));
assert_eq!(bridge_many(&far, ArcRadius::Share(1.0), f64::NAN), Err(ManyError::Bad));
assert_eq!(bridge_many(&far, ArcRadius::Share(1.0), -1.0), Err(ManyError::Bad));
assert_eq!(bridge_many(&[circle(f64::INFINITY, 0.0, 1.0), far[0]], ArcRadius::Share(1.0), 1.0), Err(ManyError::Bad));
}
#[test]
fn the_bridge_limit_counts_the_necks_left_after_thin_ones_are_dropped() {
// Two columns of 65 nearly coincident circles: 8,385 pairs within reach that the arcs can
// bridge, but the 4,225 between the columns are thinner than the precision allows.
let column = |x: f64| (0..65).map(move |k| circle(x, 0.001 * k as f64, 10.0));
let circles: Vec<Circle> = column(0.0).chain(column(34.6409)).collect();
let (pairs, too_far) = pairs_within(&circles, 15.0, ArcRadius::Share(1.0)).unwrap();
assert_eq!((pairs.len(), too_far), (8385, None));
let (pairs, ..) = bridgeable(&circles, ArcRadius::Share(1.0), 15.0).unwrap();
assert_eq!(pairs.len(), 4160);
assert!(pairs.iter().all(|&((i, j), _)| (i < 65) == (j < 65)));
assert!(bridges_any(&circles, ArcRadius::Share(1.0), 15.0));
}
#[test]
fn huge_circles_bridge_with_finite_anchors_or_are_refused() {
// Squaring these lengths overflows f64.
let (a, b) = (circle(0.0, 0.0, 5e153), circle(1.5e154, 0.0, 5e153));
let sp = smooth_bridge(a, b, 5e153).unwrap();
assert!(sp.anchors.iter().all(|q| [q.p, q.h_in, q.h_out].iter().all(|p| p.x.is_finite() && p.y.is_finite())));
assert_smooth(&sp);
// The two radius sums fit in f64, but not their total.
let (a, b) = (circle(-5e307, 0.0, 1e307), circle(5e307, 0.0, 1e307));
let sp = smooth_bridge(a, b, 1.5e308).unwrap();
assert!(sp.anchors.iter().all(|q| [q.p, q.h_in, q.h_out].iter().all(|p| p.x.is_finite() && p.y.is_finite())));
// The arcs' centers would lie beyond the largest f64.
let (a, b) = (circle(0.0, 0.0, 1e308), circle(1.5e308, 0.0, 1e308));
assert_eq!(smooth_bridge(a, b, 1e308), Err(BridgeError::Bad));
}
#[test]
fn circles_are_told_from_other_paths() {
let round = shapes::ellipse(kurbo::Rect::new(10.0, 20.0, 50.0, 60.0));
let c = circle_of(&round).unwrap();
assert!(c.center.distance(Point::new(30.0, 40.0)) < 1e-9 && (c.radius - 20.0).abs() < 1e-9);
let oval = shapes::ellipse(kurbo::Rect::new(0.0, 0.0, 50.0, 40.0));
assert_eq!(circle_of(&oval), None);
let square = PathData::single(SubPath::polyline(&[Point::ZERO, Point::new(10.0, 0.0), Point::new(10.0, 10.0), Point::new(0.0, 10.0)], true));
assert_eq!(circle_of(&square), None);
let mut open = round.clone();
open.subpaths[0].closed = false;
assert_eq!(circle_of(&open), None);
let two = PathData::new(vec![round.subpaths[0].clone(), round.subpaths[0].clone()]);
assert_eq!(circle_of(&two), None);
}
}
No file is open. Choose one in the tree, or press Ctrl+O (⌘O on a Mac) to find one by name.
Syntax highlighting could not load. The unmodified read-only text remains available above.