const SNAP: f64 = 1e-7;
#[derive(Debug, Clone, PartialEq)]
pub struct Ring {
pub uv: Vec<[f64; 2]>,
pub sources: Vec<Source>,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Source {
Boundary(usize),
Chord { chord: usize, point: usize },
Crossing,
}
#[derive(Debug, Clone, PartialEq)]
pub struct Region {
pub outer: Ring,
pub holes: Vec<Ring>,
pub area: f64,
}
pub fn clip_to_region(boundary: &[[f64; 2]], path: &[[f64; 2]]) -> Vec<Vec<[f64; 2]>> {
clip_runs(boundary, path, false)
}
pub fn clip_to_region_strictly(boundary: &[[f64; 2]], path: &[[f64; 2]]) -> Vec<Vec<[f64; 2]>> {
clip_runs(boundary, path, true)
}
fn clip_runs(boundary: &[[f64; 2]], path: &[[f64; 2]], strict: bool) -> Vec<Vec<[f64; 2]>> {
clip_runs_with_holes(boundary, &[], path, strict)
}
pub fn clip_to_region_with_holes(
boundary: &[[f64; 2]],
holes: &[Vec<[f64; 2]>],
path: &[[f64; 2]],
) -> Vec<Vec<[f64; 2]>> {
clip_runs_with_holes(boundary, holes, path, true)
}
fn clip_runs_with_holes(
boundary: &[[f64; 2]],
holes: &[Vec<[f64; 2]>],
path: &[[f64; 2]],
strict: bool,
) -> Vec<Vec<[f64; 2]>> {
if boundary.len() < 3 || path.len() < 2 {
return Vec::new();
}
let closed = dist(path[0], *path.last().unwrap()) <= extent(boundary) * SNAP;
let rings: Vec<&[[f64; 2]]> = std::iter::once(boundary)
.chain(holes.iter().filter(|h| h.len() >= 3).map(|h| h.as_slice()))
.collect();
let mut pts: Vec<([f64; 2], bool)> = Vec::new(); for i in 0..path.len() - 1 {
pts.push((path[i], false));
let mut here: Vec<(f64, [f64; 2])> = Vec::new();
for ring in &rings {
for j in 0..ring.len() {
let (q, q2) = (ring[j], ring[(j + 1) % ring.len()]);
if let Some((t, _, at)) = segment_cross(path[i], path[i + 1], q, q2)
&& !here.iter().any(|(_, p)| dist(*p, at) <= SNAP)
{
here.push((t, at));
}
}
}
here.sort_by(|a, b| a.0.partial_cmp(&b.0).unwrap_or(std::cmp::Ordering::Equal));
pts.extend(here.into_iter().map(|(_, p)| (p, true)));
}
pts.push((*path.last().unwrap(), false));
let mut out: Vec<Vec<[f64; 2]>> = Vec::new();
let mut run: Vec<[f64; 2]> = Vec::new();
for (i, (p, crossing)) in pts.iter().enumerate() {
run.push(*p);
if *crossing && i + 1 < pts.len() {
if run.len() > 1 && inside_rings(&rings, &run, strict) {
out.push(std::mem::take(&mut run));
run.push(*p);
} else {
run.clear();
run.push(*p);
}
}
}
if run.len() > 1 && inside_rings(&rings, &run, strict) {
out.push(run);
}
if closed && out.len() > 1 {
let first = out[0].clone();
let last = out[out.len() - 1].clone();
if dist(*last.last().unwrap(), first[0]) <= extent(boundary) * SNAP {
let mut joined = last;
joined.extend(first.into_iter().skip(1));
let n = out.len();
out[0] = joined;
out.remove(n - 1);
}
}
out
}
fn inside_rings(rings: &[&[[f64; 2]]], run: &[[f64; 2]], strict: bool) -> bool {
let (boundary, holes) = (rings[0], &rings[1..]);
if !inside_run(boundary, run, strict) {
return false;
}
let mid = run[run.len() / 2];
let probe = if run.len() >= 2 {
let a = run[run.len() / 2 - 1];
[(a[0] + mid[0]) * 0.5, (a[1] + mid[1]) * 0.5]
} else {
mid
};
let reach = extent(boundary) * SNAP * 10.0;
holes.iter().all(|h| {
!point_in_ring(h, probe)
&& (!strict
|| nearest_on_boundary(h, probe).is_none_or(|(_, _, at)| dist(probe, at) > reach))
})
}
fn inside_run(boundary: &[[f64; 2]], run: &[[f64; 2]], strict: bool) -> bool {
let mid = run[run.len() / 2];
let probe = if run.len() >= 2 {
let a = run[run.len() / 2 - 1];
[(a[0] + mid[0]) * 0.5, (a[1] + mid[1]) * 0.5]
} else {
mid
};
if !point_in_ring(boundary, probe) {
return false;
}
let reach = extent(boundary) * SNAP * 10.0;
!strict || nearest_on_boundary(boundary, probe).is_none_or(|(_, _, at)| dist(probe, at) > reach)
}
fn segment_cross(
p: [f64; 2],
p2: [f64; 2],
q: [f64; 2],
q2: [f64; 2],
) -> Option<(f64, f64, [f64; 2])> {
let r = [p2[0] - p[0], p2[1] - p[1]];
let s = [q2[0] - q[0], q2[1] - q[1]];
let denom = r[0] * s[1] - r[1] * s[0];
if denom.abs() <= f64::MIN_POSITIVE {
return None;
}
let d = [q[0] - p[0], q[1] - p[1]];
let t = (d[0] * s[1] - d[1] * s[0]) / denom;
let u = (d[0] * r[1] - d[1] * r[0]) / denom;
if !(-SNAP..=1.0 + SNAP).contains(&t) || !(-SNAP..=1.0 + SNAP).contains(&u) {
return None;
}
Some((t, u, [p[0] + r[0] * t, p[1] + r[1] * t]))
}
pub fn subdivide(boundary: &[[f64; 2]], chords: &[Vec<[f64; 2]>]) -> Option<Vec<Region>> {
if boundary.len() < 3 {
return None;
}
if chords.is_empty() {
let ring = Ring {
uv: boundary.to_vec(),
sources: (0..boundary.len()).map(Source::Boundary).collect(),
};
let area = signed_area(&ring.uv).abs();
return Some(vec![Region {
outer: ring,
holes: Vec::new(),
area,
}]);
}
let mut nodes: Vec<Node> = boundary
.iter()
.enumerate()
.map(|(i, p)| Node {
uv: *p,
source: Source::Boundary(i),
})
.collect();
let scale = extent(boundary).max(1e-12);
let snap = scale * SNAP;
let mut cuts: Vec<Vec<(f64, usize)>> = vec![Vec::new(); chords.len()];
for i in 0..chords.len() {
for j in i + 1..chords.len() {
for (ti, tj, at) in crossings(&chords[i], &chords[j]) {
let node = match nodes.iter().position(|n| dist(n.uv, at) <= snap) {
Some(n) => n,
None => {
nodes.push(Node {
uv: at,
source: Source::Crossing,
});
nodes.len() - 1
}
};
cuts[i].push((ti, node));
cuts[j].push((tj, node));
}
}
}
let mut splits: Vec<Vec<(f64, usize)>> = vec![Vec::new(); boundary.len()];
let mut ends: Vec<[usize; 2]> = Vec::with_capacity(chords.len());
for (ci, chord) in chords.iter().enumerate() {
if chord.len() < 2 {
return None;
}
if chord.len() > 3 && dist(chord[0], *chord.last().unwrap()) <= snap {
nodes.push(Node {
uv: chord[0],
source: Source::Chord {
chord: ci,
point: 0,
},
});
let n = nodes.len() - 1;
ends.push([n, n]);
continue;
}
let mut got = [usize::MAX; 2];
for (k, p, t_end) in [
(0usize, chord[0], 0.0),
(1, *chord.last().unwrap(), (chord.len() - 1) as f64),
] {
if let Some((_, n)) = cuts[ci].iter().find(|(t, _)| (t - t_end).abs() <= SNAP) {
got[k] = *n;
continue;
}
let (seg, t, at) = nearest_on_boundary(boundary, p)?;
if dist(at, p) > snap {
return None; }
got[k] = if t <= SNAP {
seg
} else if t >= 1.0 - SNAP {
(seg + 1) % boundary.len()
} else {
match splits[seg].iter().find(|(u, _)| (u - t).abs() <= SNAP) {
Some((_, n)) => *n,
None => {
nodes.push(Node {
uv: at,
source: Source::Crossing,
});
splits[seg].push((t, nodes.len() - 1));
nodes.len() - 1
}
}
};
}
if got[0] == got[1] {
return None; }
ends.push(got);
}
let mut edges: Vec<Edge> = Vec::new();
for (i, here) in splits.iter().enumerate() {
let mut here = here.clone();
here.sort_by(|a, b| a.0.partial_cmp(&b.0).unwrap_or(std::cmp::Ordering::Equal));
let mut from = i;
for (_, n) in here {
edges.push(Edge {
from,
to: n,
interior: Vec::new(),
chord: None,
});
from = n;
}
edges.push(Edge {
from,
to: (i + 1) % boundary.len(),
interior: Vec::new(),
chord: None,
});
}
for (ci, chord) in chords.iter().enumerate() {
let mut stops: Vec<(f64, usize)> = cuts[ci].clone();
stops.push((0.0, ends[ci][0]));
stops.push(((chord.len() - 1) as f64, ends[ci][1]));
stops.sort_by(|a, b| a.0.partial_cmp(&b.0).unwrap_or(std::cmp::Ordering::Equal));
stops.dedup_by(|a, b| (a.0 - b.0).abs() <= SNAP);
if ends[ci][0] == ends[ci][1] && cuts[ci].is_empty() {
edges.push(Edge {
from: ends[ci][0],
to: ends[ci][0],
interior: chord[1..chord.len() - 1].to_vec(),
chord: Some(ci),
});
continue;
}
for w in stops.windows(2) {
let (t0, n0) = w[0];
let (t1, n1) = w[1];
if n0 == n1 {
continue;
}
edges.push(Edge {
from: n0,
to: n1,
interior: between(chord, t0, t1),
chord: Some(ci),
});
}
}
let half: Vec<Half> = edges
.iter()
.enumerate()
.flat_map(|(i, e)| {
[
Half {
edge: i,
from: e.from,
to: e.to,
forward: true,
},
Half {
edge: i,
from: e.to,
to: e.from,
forward: false,
},
]
})
.collect();
let mut out_of: Vec<Vec<usize>> = vec![Vec::new(); nodes.len()];
for (i, h) in half.iter().enumerate() {
out_of[h.from].push(i);
}
for (n, list) in out_of.iter_mut().enumerate() {
list.sort_by(|&a, &b| {
angle_of(&half[a], &nodes, &edges, n)
.partial_cmp(&angle_of(&half[b], &nodes, &edges, n))
.unwrap_or(std::cmp::Ordering::Equal)
});
}
let mut seen = vec![false; half.len()];
let mut regions: Vec<Region> = Vec::new();
let mut inverted: Vec<(Ring, f64)> = Vec::new();
for start in 0..half.len() {
if seen[start] {
continue;
}
let mut ring: Vec<[f64; 2]> = Vec::new();
let mut sources: Vec<Source> = Vec::new();
let mut h = start;
loop {
if seen[h] {
break;
}
seen[h] = true;
let cur = &half[h];
ring.push(nodes[cur.from].uv);
sources.push(nodes[cur.from].source);
let e = &edges[cur.edge];
if !e.interior.is_empty() {
let chord = e.chord.expect("only chords carry interior points");
let n = e.interior.len();
for k in 0..n {
let k = if cur.forward { k } else { n - 1 - k };
ring.push(e.interior[k]);
sources.push(Source::Chord {
chord,
point: k + 1,
});
}
}
let back = h ^ 1;
let at = half[back].from;
let list = &out_of[at];
let pos = list.iter().position(|&x| x == back)?;
h = list[(pos + list.len() - 1) % list.len()];
if h == start {
break;
}
}
if ring.len() < 3 {
continue;
}
let area = signed_area(&ring);
if area > 0.0 {
regions.push(Region {
outer: Ring { uv: ring, sources },
holes: Vec::new(),
area,
});
} else {
inverted.push((Ring { uv: ring, sources }, -area));
}
}
if regions.is_empty() {
return None;
}
for (ring, area) in inverted {
let Some(probe) = ring.uv.first().copied() else {
continue;
};
let mut best: Option<usize> = None;
for (i, r) in regions.iter().enumerate() {
if r.area <= area * (1.0 + 1e-9) || !point_in_ring(&r.outer.uv, probe) {
continue;
}
if best.is_none_or(|b| r.area < regions[b].area) {
best = Some(i);
}
}
if let Some(i) = best {
regions[i].holes.push(ring);
regions[i].area -= area;
}
}
Some(regions)
}
struct Node {
uv: [f64; 2],
source: Source,
}
struct Edge {
from: usize,
to: usize,
interior: Vec<[f64; 2]>,
chord: Option<usize>,
}
struct Half {
edge: usize,
from: usize,
to: usize,
forward: bool,
}
fn angle_of(h: &Half, nodes: &[Node], edges: &[Edge], at: usize) -> f64 {
let e = &edges[h.edge];
let next = if e.interior.is_empty() {
nodes[h.to].uv
} else if h.forward {
e.interior[0]
} else {
e.interior[e.interior.len() - 1]
};
let from = nodes[at].uv;
(next[1] - from[1]).atan2(next[0] - from[0])
}
fn point_in_ring(ring: &[[f64; 2]], p: [f64; 2]) -> bool {
let n = ring.len();
let mut inside = false;
for i in 0..n {
let (a, b) = (ring[i], ring[(i + 1) % n]);
if (a[1] > p[1]) != (b[1] > p[1]) {
let t = (p[1] - a[1]) / (b[1] - a[1]);
if p[0] < a[0] + t * (b[0] - a[0]) {
inside = !inside;
}
}
}
inside
}
fn signed_area(ring: &[[f64; 2]]) -> f64 {
let n = ring.len();
(0..n)
.map(|i| {
let (a, b) = (ring[i], ring[(i + 1) % n]);
a[0] * b[1] - b[0] * a[1]
})
.sum::<f64>()
/ 2.0
}
fn between(chord: &[[f64; 2]], t0: f64, t1: f64) -> Vec<[f64; 2]> {
let mut out = Vec::new();
let first = (t0.floor() as usize) + 1;
for (k, p) in chord.iter().enumerate().skip(first) {
if (k as f64) >= t1 - SNAP {
break;
}
out.push(*p);
}
out
}
fn crossings(a: &[[f64; 2]], b: &[[f64; 2]]) -> Vec<(f64, f64, [f64; 2])> {
let mut out = Vec::new();
for i in 0..a.len().saturating_sub(1) {
for j in 0..b.len().saturating_sub(1) {
let (p, p2) = (a[i], a[i + 1]);
let (q, q2) = (b[j], b[j + 1]);
let r = [p2[0] - p[0], p2[1] - p[1]];
let s = [q2[0] - q[0], q2[1] - q[1]];
let denom = r[0] * s[1] - r[1] * s[0];
if denom.abs() <= f64::MIN_POSITIVE {
continue; }
let d = [q[0] - p[0], q[1] - p[1]];
let t = (d[0] * s[1] - d[1] * s[0]) / denom;
let u = (d[0] * r[1] - d[1] * r[0]) / denom;
if !(-SNAP..=1.0 + SNAP).contains(&t) || !(-SNAP..=1.0 + SNAP).contains(&u) {
continue;
}
let at = [p[0] + r[0] * t, p[1] + r[1] * t];
if out
.iter()
.any(|&(_, _, q): &(f64, f64, [f64; 2])| dist(q, at) <= SNAP)
{
continue;
}
out.push((i as f64 + t, j as f64 + u, at));
}
}
out
}
fn dist(a: [f64; 2], b: [f64; 2]) -> f64 {
(a[0] - b[0]).hypot(a[1] - b[1])
}
fn extent(ring: &[[f64; 2]]) -> f64 {
let (mut lo, mut hi) = ([f64::MAX; 2], [f64::MIN; 2]);
for p in ring {
for k in 0..2 {
lo[k] = lo[k].min(p[k]);
hi[k] = hi[k].max(p[k]);
}
}
(hi[0] - lo[0]).max(hi[1] - lo[1])
}
pub fn within_hole(ring: &[[f64; 2]], hole: &[[f64; 2]]) -> bool {
let reach = extent(hole) * SNAP * 10.0;
ring.len() >= 3
&& hole.len() >= 3
&& ring.iter().all(|&p| {
point_in_ring(hole, p)
|| nearest_on_boundary(hole, p).is_some_and(|(_, _, at)| dist(p, at) <= reach)
})
}
fn nearest_on_boundary(boundary: &[[f64; 2]], p: [f64; 2]) -> Option<(usize, f64, [f64; 2])> {
let n = boundary.len();
let mut best: Option<(f64, usize, f64, [f64; 2])> = None;
for i in 0..n {
let (a, b) = (boundary[i], boundary[(i + 1) % n]);
let (dx, dy) = (b[0] - a[0], b[1] - a[1]);
let len2 = dx * dx + dy * dy;
let t = if len2 <= f64::MIN_POSITIVE {
0.0
} else {
(((p[0] - a[0]) * dx + (p[1] - a[1]) * dy) / len2).clamp(0.0, 1.0)
};
let at = [a[0] + dx * t, a[1] + dy * t];
let d = dist(at, p);
if best.is_none_or(|(bd, _, _, _)| d < bd) {
best = Some((d, i, t, at));
}
}
best.map(|(_, i, t, at)| (i, t, at))
}
pub fn arrange(rings: &[Vec<[f64; 2]>], tolerance: f64) -> (Vec<[f64; 2]>, Vec<[usize; 2]>) {
let mut ends: Vec<([f64; 2], [f64; 2])> = Vec::new();
for r in rings {
let n = r.len();
if n < 2 {
continue;
}
for i in 0..n {
ends.push((r[i], r[(i + 1) % n]));
}
}
let mut cuts: Vec<Vec<f64>> = vec![Vec::new(); ends.len()];
for i in 0..ends.len() {
for j in i + 1..ends.len() {
let (a, b) = ends[i];
let (c, d) = ends[j];
let r = [b[0] - a[0], b[1] - a[1]];
let s = [d[0] - c[0], d[1] - c[1]];
let denom = r[0] * s[1] - r[1] * s[0];
if denom.abs() < 1e-15 {
continue; }
let ac = [c[0] - a[0], c[1] - a[1]];
let t = (ac[0] * s[1] - ac[1] * s[0]) / denom;
let u = (ac[0] * r[1] - ac[1] * r[0]) / denom;
if t > 1e-12 && t < 1.0 - 1e-12 && u > 1e-12 && u < 1.0 - 1e-12 {
cuts[i].push(t);
cuts[j].push(u);
}
}
}
let mut pts: Vec<[f64; 2]> = Vec::new();
let id = |p: [f64; 2], pts: &mut Vec<[f64; 2]>| -> usize {
for (i, q) in pts.iter().enumerate() {
if (q[0] - p[0]).hypot(q[1] - p[1]) <= tolerance {
return i;
}
}
pts.push(p);
pts.len() - 1
};
let mut edges: Vec<[usize; 2]> = Vec::new();
for (i, (a, b)) in ends.iter().enumerate() {
let mut ts = cuts[i].clone();
ts.push(0.0);
ts.push(1.0);
ts.sort_by(|x, y| x.total_cmp(y));
ts.dedup_by(|x, y| (*x - *y).abs() <= 1e-12);
for w in ts.windows(2) {
let at = |t: f64| [a[0] + (b[0] - a[0]) * t, a[1] + (b[1] - a[1]) * t];
let (p, q) = (id(at(w[0]), &mut pts), id(at(w[1]), &mut pts));
if p != q {
edges.push([p, q]);
}
}
}
(pts, edges)
}
pub fn regions_of(rings: &[Vec<[f64; 2]>], tolerance: f64) -> Vec<Vec<[f64; 2]>> {
let (pts, edges) = arrange(rings, tolerance);
if pts.len() < 3 || edges.is_empty() {
return Vec::new();
}
let mut half: Vec<(usize, usize)> = Vec::with_capacity(edges.len() * 2);
for e in &edges {
half.push((e[0], e[1]));
half.push((e[1], e[0]));
}
let angle = |h: usize| -> f64 {
let (a, b) = half[h];
(pts[b][1] - pts[a][1]).atan2(pts[b][0] - pts[a][0])
};
let mut out_of: Vec<Vec<usize>> = vec![Vec::new(); pts.len()];
for h in 0..half.len() {
out_of[half[h].0].push(h);
}
for list in out_of.iter_mut() {
list.sort_by(|&x, &y| angle(x).total_cmp(&angle(y)));
}
let mut seen = vec![false; half.len()];
let mut cycles: Vec<Vec<usize>> = Vec::new();
for start in 0..half.len() {
if seen[start] {
continue;
}
let mut cycle = Vec::new();
let mut h = start;
loop {
if seen[h] {
break;
}
seen[h] = true;
cycle.push(half[h].0);
let back = h ^ 1;
let at = half[back].0;
let list = &out_of[at];
let Some(pos) = list.iter().position(|&x| x == back) else {
break;
};
h = list[(pos + list.len() - 1) % list.len()];
if h == start {
break;
}
}
if cycle.len() >= 3 {
cycles.push(cycle);
}
}
let mut kept = Vec::new();
for cycle in cycles {
let uv: Vec<[f64; 2]> = cycle.iter().map(|&i| pts[i]).collect();
let area = signed_area(&uv);
if area <= tolerance * tolerance {
continue;
}
let inside = uv
.iter()
.zip(uv.iter().cycle().skip(1))
.fold([0.0, 0.0], |acc, (a, b)| {
[acc[0] + (a[0] + b[0]) * 0.5, acc[1] + (a[1] + b[1]) * 0.5]
});
let probe = [inside[0] / uv.len() as f64, inside[1] / uv.len() as f64];
if winding(rings, probe) != 0 {
kept.push(uv);
}
}
kept
}
pub type PlaneRegion = (Vec<[f64; 2]>, Vec<Vec<[f64; 2]>>);
pub fn boolean(
a: &[Vec<[f64; 2]>],
b: &[Vec<[f64; 2]>],
keep: impl Fn(bool, bool) -> bool,
tolerance: f64,
) -> Vec<PlaneRegion> {
let rings: Vec<Vec<[f64; 2]>> = a.iter().chain(b).cloned().collect();
let (pts, edges) = arrange(&rings, tolerance);
if pts.len() < 3 || edges.is_empty() {
return Vec::new();
}
let mut half: Vec<(usize, usize)> = Vec::with_capacity(edges.len() * 2);
for e in &edges {
half.push((e[0], e[1]));
half.push((e[1], e[0]));
}
let angle = |h: usize| -> f64 {
let (p, q) = half[h];
(pts[q][1] - pts[p][1]).atan2(pts[q][0] - pts[p][0])
};
let mut out_of: Vec<Vec<usize>> = vec![Vec::new(); pts.len()];
for h in 0..half.len() {
out_of[half[h].0].push(h);
}
for list in out_of.iter_mut() {
list.sort_by(|&x, &y| angle(x).total_cmp(&angle(y)));
}
let mut seen = vec![false; half.len()];
let mut cycles: Vec<Vec<[f64; 2]>> = Vec::new();
for start in 0..half.len() {
if seen[start] {
continue;
}
let mut cycle = Vec::new();
let mut h = start;
loop {
if seen[h] {
break;
}
seen[h] = true;
cycle.push(pts[half[h].0]);
let back = h ^ 1;
let list = &out_of[half[back].0];
let Some(pos) = list.iter().position(|&x| x == back) else {
break;
};
h = list[(pos + list.len() - 1) % list.len()];
if h == start {
break;
}
}
if cycle.len() >= 3 {
cycles.push(cycle);
}
}
let inside = |set: &[Vec<[f64; 2]>], p: [f64; 2]| {
set.iter()
.filter(|r| winding(std::slice::from_ref(*r), p) != 0)
.count()
% 2
== 1
};
let probe = |c: &[[f64; 2]]| -> [f64; 2] {
let n = c.len();
let i = (0..n)
.max_by(|&i, &j| {
let l = |k: usize| {
let (p, q) = (c[k], c[(k + 1) % n]);
(q[0] - p[0]).hypot(q[1] - p[1])
};
l(i).total_cmp(&l(j))
})
.unwrap();
let (p, q) = (c[i], c[(i + 1) % n]);
let len = (q[0] - p[0]).hypot(q[1] - p[1]).max(1e-300);
let step = (tolerance * 10.0).max(len * 1e-6);
let mid = [(p[0] + q[0]) * 0.5, (p[1] + q[1]) * 0.5];
[
mid[0] - (q[1] - p[1]) / len * step,
mid[1] + (q[0] - p[0]) / len * step,
]
};
let tiny = tolerance * tolerance;
let mut faces: Vec<(Vec<[f64; 2]>, f64, bool)> = Vec::new(); let mut outlines: Vec<Vec<[f64; 2]>> = Vec::new();
for c in cycles {
let area = signed_area(&c);
if area > tiny {
let p = probe(&c);
let kept = keep(inside(a, p), inside(b, p));
faces.push((c, area, kept));
} else if area < -tiny {
outlines.push(c);
}
}
let mut out: Vec<PlaneRegion> = faces
.iter()
.filter(|f| f.2)
.map(|f| (f.0.clone(), Vec::new()))
.collect();
let index: Vec<usize> = faces
.iter()
.enumerate()
.filter(|(_, f)| f.2)
.map(|(i, _)| i)
.collect();
for o in outlines {
let p = o[0];
let around = faces
.iter()
.enumerate()
.filter(|(_, f)| {
winding(std::slice::from_ref(&f.0), p) != 0
&& !f
.0
.iter()
.any(|q| (q[0] - p[0]).hypot(q[1] - p[1]) <= tolerance)
})
.min_by(|x, y| x.1 .1.total_cmp(&y.1 .1))
.map(|(i, _)| i);
if let Some(i) = around
&& let Some(k) = index.iter().position(|&j| j == i)
{
out[k].1.push(o);
}
}
out
}
fn winding(rings: &[Vec<[f64; 2]>], p: [f64; 2]) -> i32 {
let mut w = 0;
for r in rings {
let n = r.len();
for i in 0..n {
let (a, b) = (r[i], r[(i + 1) % n]);
if a[1] <= p[1] {
if b[1] > p[1]
&& (b[0] - a[0]) * (p[1] - a[1]) - (p[0] - a[0]) * (b[1] - a[1]) > 0.0
{
w += 1;
}
} else if b[1] <= p[1]
&& (b[0] - a[0]) * (p[1] - a[1]) - (p[0] - a[0]) * (b[1] - a[1]) < 0.0
{
w -= 1;
}
}
}
w
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn two_squares_cut_fused_and_shared() {
let a = vec![square()];
let b = vec![vec![[2.0, 2.0], [6.0, 2.0], [6.0, 6.0], [2.0, 6.0]]];
let area = |rs: &[PlaneRegion]| -> f64 {
rs.iter()
.map(|(o, hs)| signed_area(o) + hs.iter().map(|h| signed_area(h)).sum::<f64>())
.sum()
};
let cut = boolean(&a, &b, |x, y| x && !y, 1e-9);
assert_eq!(cut.len(), 1);
assert!((area(&cut) - 12.0).abs() < 1e-9);
let common = boolean(&a, &b, |x, y| x && y, 1e-9);
assert!((area(&common) - 4.0).abs() < 1e-9);
let fuse = boolean(&a, &b, |x, y| x || y, 1e-9);
assert_eq!(fuse.len(), 3);
assert!((area(&fuse) - 28.0).abs() < 1e-9);
let big = vec![vec![[-4.0, -4.0], [8.0, -4.0], [8.0, 8.0], [-4.0, 8.0]]];
let holed = boolean(&big, &a, |x, y| x && !y, 1e-9);
assert_eq!(holed.len(), 1);
assert_eq!(holed[0].1.len(), 1);
assert!((area(&holed) - 128.0).abs() < 1e-9);
}
fn square() -> Vec<[f64; 2]> {
vec![[0.0, 0.0], [4.0, 0.0], [4.0, 4.0], [0.0, 4.0]]
}
fn areas(regions: &[Region]) -> Vec<f64> {
let mut a: Vec<f64> = regions
.iter()
.map(|r| (r.area * 1e6).round() / 1e6)
.collect();
a.sort_by(|x, y| x.partial_cmp(y).unwrap());
a
}
#[test]
fn no_chords_leaves_the_region_alone() {
let r = subdivide(&square(), &[]).unwrap();
assert_eq!(r.len(), 1);
assert_eq!(r[0].area, 16.0);
}
#[test]
fn one_chord_cuts_the_region_in_two() {
let r = subdivide(&square(), &[vec![[0.0, 2.0], [4.0, 2.0]]]).unwrap();
assert_eq!(r.len(), 2);
assert_eq!(areas(&r), vec![8.0, 8.0]);
}
#[test]
fn a_chord_landing_on_corners_reuses_them() {
let r = subdivide(&square(), &[vec![[0.0, 0.0], [4.0, 4.0]]]).unwrap();
assert_eq!(r.len(), 2);
assert_eq!(areas(&r), vec![8.0, 8.0]);
}
#[test]
fn two_chords_cut_three_pieces() {
let r = subdivide(
&square(),
&[vec![[0.0, 1.0], [4.0, 1.0]], vec![[0.0, 3.0], [4.0, 3.0]]],
)
.unwrap();
assert_eq!(r.len(), 3);
assert_eq!(areas(&r), vec![4.0, 8.0, 4.0].tap_sort());
}
#[test]
fn a_curved_chord_keeps_its_shape() {
let bow: Vec<[f64; 2]> = (0..=8)
.map(|i| {
let t = i as f64 / 8.0;
[4.0 * t, 2.0 + (std::f64::consts::PI * t).sin()]
})
.collect();
let r = subdivide(&square(), std::slice::from_ref(&bow)).unwrap();
assert_eq!(r.len(), 2);
let total: f64 = r.iter().map(|x| x.area).sum();
assert!((total - 16.0).abs() < 1e-9, "pieces total {total}");
assert!(
r.iter().any(|x| x.area > 8.5),
"the bow should make the halves unequal: {:?}",
areas(&r)
);
for p in &bow[1..bow.len() - 1] {
assert!(
r.iter()
.any(|x| x.outer.uv.iter().any(|q| dist(*q, *p) < 1e-9)),
"{p:?} was dropped"
);
}
}
#[test]
fn the_pieces_tile_the_original() {
for chords in [
vec![vec![[0.0, 2.0], [4.0, 2.0]]],
vec![vec![[2.0, 0.0], [2.0, 4.0]]],
vec![vec![[0.0, 1.0], [4.0, 3.0]]],
vec![
vec![[0.0, 1.0], [4.0, 1.0]],
vec![[0.0, 2.0], [4.0, 2.0]],
vec![[0.0, 3.0], [4.0, 3.0]],
],
vec![vec![[0.0, 0.0], [4.0, 2.0]], vec![[0.0, 4.0], [4.0, 2.0]]],
] {
let r = subdivide(&square(), &chords).unwrap();
let total: f64 = r.iter().map(|x| x.area).sum();
assert!(
(total - 16.0).abs() < 1e-9,
"{chords:?} gave {} pieces totalling {total}",
r.len()
);
}
}
#[test]
fn a_chord_that_stops_inside_is_refused() {
assert!(subdivide(&square(), &[vec![[0.0, 2.0], [2.0, 2.0]]]).is_none());
assert!(subdivide(&square(), &[vec![[1.0, 1.0], [3.0, 3.0]]]).is_none());
}
#[test]
fn a_degenerate_chord_is_refused() {
assert!(subdivide(&square(), &[vec![[0.0, 2.0]]]).is_none());
assert!(subdivide(&square(), &[vec![[0.0, 2.0], [0.0, 2.0]]]).is_none());
}
#[test]
fn crossing_chords_give_four_pieces() {
let r = subdivide(
&square(),
&[vec![[0.0, 2.0], [4.0, 2.0]], vec![[2.0, 0.0], [2.0, 4.0]]],
)
.unwrap();
assert_eq!(r.len(), 4);
assert_eq!(areas(&r), vec![4.0, 4.0, 4.0, 4.0]);
}
#[test]
fn an_off_centre_crossing_gives_the_right_four() {
let r = subdivide(
&square(),
&[vec![[0.0, 1.0], [4.0, 1.0]], vec![[3.0, 0.0], [3.0, 4.0]]],
)
.unwrap();
assert_eq!(r.len(), 4);
assert_eq!(areas(&r), vec![3.0, 3.0, 1.0, 9.0].tap_sort());
}
#[test]
fn three_chords_crossing_pairwise() {
let r = subdivide(
&square(),
&[
vec![[0.0, 1.0], [4.0, 1.0]],
vec![[0.0, 3.0], [4.0, 3.0]],
vec![[2.0, 0.0], [2.0, 4.0]],
],
)
.unwrap();
assert_eq!(r.len(), 6);
let total: f64 = r.iter().map(|x| x.area).sum();
assert!((total - 16.0).abs() < 1e-9, "{:?}", areas(&r));
}
#[test]
fn a_curved_chord_crossing_a_straight_one() {
let bow: Vec<[f64; 2]> = (0..=16)
.map(|i| {
let t = i as f64 / 16.0;
[4.0 * t, 2.0 + 1.5 * (std::f64::consts::PI * t).sin()]
})
.collect();
let r = subdivide(&square(), &[bow, vec![[2.0, 0.0], [2.0, 4.0]]]).unwrap();
assert_eq!(r.len(), 4);
let total: f64 = r.iter().map(|x| x.area).sum();
assert!((total - 16.0).abs() < 1e-9, "{:?}", areas(&r));
}
#[test]
fn a_closed_path_inside_a_region_becomes_a_hole() {
let ring: Vec<[f64; 2]> = (0..=12)
.map(|i| {
let t = std::f64::consts::TAU * i as f64 / 12.0;
[2.0 + t.cos(), 2.0 + t.sin()]
})
.collect();
let r = subdivide(&square(), &[ring]).unwrap();
assert_eq!(r.len(), 2, "the surround and the disc");
let surround = r
.iter()
.find(|x| x.holes.len() == 1)
.expect("one has a hole");
let disc = r
.iter()
.find(|x| x.holes.is_empty())
.expect("the other does not");
assert!((surround.area + disc.area - 16.0).abs() < 1e-9);
assert!(disc.area > 2.9 && disc.area < 3.15, "{}", disc.area);
}
#[test]
fn a_hole_and_a_cut_together() {
let ring: Vec<[f64; 2]> = (0..=12)
.map(|i| {
let t = std::f64::consts::TAU * i as f64 / 12.0;
[1.0 + 0.5 * t.cos(), 1.0 + 0.5 * t.sin()]
})
.collect();
let r = subdivide(&square(), &[ring, vec![[0.0, 3.0], [4.0, 3.0]]]).unwrap();
let total: f64 = r.iter().map(|x| x.area).sum();
assert!((total - 16.0).abs() < 1e-9, "areas {:?}", areas(&r));
assert_eq!(r.iter().filter(|x| !x.holes.is_empty()).count(), 1);
}
#[test]
fn clipping_a_path_to_the_region() {
let inside = vec![[1.0, 1.0], [3.0, 1.0], [3.0, 3.0], [1.0, 3.0], [1.0, 1.0]];
let r = clip_to_region(&square(), &inside);
assert_eq!(r.len(), 1);
assert_eq!(r[0].len(), inside.len());
let outside = vec![[5.0, 5.0], [7.0, 5.0], [7.0, 7.0], [5.0, 5.0]];
assert!(clip_to_region(&square(), &outside).is_empty());
let across = vec![[2.0, -1.0], [2.0, 5.0]];
let r = clip_to_region(&square(), &across);
assert_eq!(r.len(), 1);
assert!((r[0][0][1] - 0.0).abs() < 1e-9, "{:?}", r[0][0]);
assert!((r[0][r[0].len() - 1][1] - 4.0).abs() < 1e-9);
}
#[test]
fn a_partly_overlapping_square_cuts_this_one_in_two() {
let other = vec![[2.0, 2.0], [6.0, 2.0], [6.0, 6.0], [2.0, 6.0], [2.0, 2.0]];
let chords = clip_to_region(&square(), &other);
assert_eq!(chords.len(), 1, "one stretch of it is inside");
let r = subdivide(&square(), &chords).unwrap();
assert_eq!(r.len(), 2);
assert_eq!(areas(&r), vec![4.0, 12.0]);
}
#[test]
fn an_overlap_that_crosses_two_sides() {
let other = vec![
[3.0, -1.0],
[5.0, -1.0],
[5.0, 5.0],
[3.0, 5.0],
[3.0, -1.0],
];
let chords = clip_to_region(&square(), &other);
let r = subdivide(&square(), &chords).unwrap();
let total: f64 = r.iter().map(|x| x.area).sum();
assert!((total - 16.0).abs() < 1e-9, "{:?}", areas(&r));
assert_eq!(areas(&r), vec![4.0, 12.0]);
}
#[test]
fn chords_that_are_not_a_clean_cut_are_refused() {
assert!(subdivide(&square(), &[vec![[0.0, 0.0], [0.0, 4.0]]]).is_none());
}
#[test]
fn a_chord_may_end_on_another_chord() {
let r = subdivide(
&square(),
&[vec![[1.0, 0.0], [1.0, 4.0]], vec![[0.0, 1.0], [1.0, 1.0]]],
)
.unwrap();
assert_eq!(r.len(), 3);
assert_eq!(areas(&r), vec![1.0, 3.0, 12.0]);
}
#[test]
fn two_chords_meeting_end_to_end_cut_a_corner_off() {
let r = subdivide(
&square(),
&[vec![[2.0, 0.0], [2.0, 2.0]], vec![[2.0, 2.0], [0.0, 2.0]]],
)
.unwrap();
assert_eq!(r.len(), 2);
assert_eq!(areas(&r), vec![4.0, 12.0]);
}
#[test]
fn sources_point_back_at_the_inputs() {
let r = subdivide(&square(), &[vec![[0.0, 2.0], [4.0, 2.0]]]).unwrap();
let mut boundary = 0;
let mut crossing = 0;
for region in &r {
for s in ®ion.outer.sources {
match s {
Source::Boundary(_) => boundary += 1,
Source::Crossing => crossing += 1,
Source::Chord { .. } => {}
}
}
}
assert_eq!(boundary, 4, "each original corner used once");
assert_eq!(crossing, 4, "two new points, each used by two pieces");
}
trait TapSort {
fn tap_sort(self) -> Self;
}
impl TapSort for Vec<f64> {
fn tap_sort(mut self) -> Self {
self.sort_by(|a, b| a.partial_cmp(b).unwrap());
self
}
}
}