use crate::math::{Box2, Vector2};
#[inline]
fn orient(a: [f64; 2], b: [f64; 2], c: [f64; 2]) -> f64 {
(b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])
}
#[inline]
fn in_circle(a: [f64; 2], b: [f64; 2], c: [f64; 2], d: [f64; 2]) -> f64 {
let (ax, ay) = (a[0] - d[0], a[1] - d[1]);
let (bx, by) = (b[0] - d[0], b[1] - d[1]);
let (cx, cy) = (c[0] - d[0], c[1] - d[1]);
(ax * ax + ay * ay) * (bx * cy - by * cx) - (bx * bx + by * by) * (ax * cy - ay * cx)
+ (cx * cx + cy * cy) * (ax * by - ay * bx)
}
pub fn delaunay(points: &[Vector2]) -> Vec<[u32; 3]> {
if points.len() < 3 {
return Vec::new();
}
let p: Vec<[f64; 2]> = points.iter().map(|v| [v.x as f64, v.y as f64]).collect();
let n = p.len();
let Some(j) = (1..n).find(|&j| p[j] != p[0]) else {
return Vec::new();
};
let Some(k) = (j + 1..n).find(|&k| orient(p[0], p[j], p[k]) != 0.0) else {
return Vec::new();
};
let seed = if orient(p[0], p[j], p[k]) > 0.0 {
[0, j, k]
} else {
[0, k, j]
};
let mut tris: Vec<[usize; 3]> = vec![seed];
let mut bad: Vec<usize> = Vec::new();
let mut cavity: Vec<(usize, usize)> = Vec::new();
let mut directed: std::collections::HashSet<(u32, u32)> = std::collections::HashSet::new();
let mut fresh: Vec<[usize; 3]> = Vec::new();
for i in 0..n {
if i == 0 || i == j || i == k {
continue;
}
bad.clear();
cavity.clear();
fresh.clear();
for (t, tri) in tris.iter().enumerate() {
if in_circle(p[tri[0]], p[tri[1]], p[tri[2]], p[i]) > 0.0 {
bad.push(t);
}
}
for &t in &bad {
let tri = tris[t];
for e in 0..3 {
cavity.push((tri[e], tri[(e + 1) % 3]));
}
}
let inside = bad.iter().any(|&t| {
let tri = tris[t];
orient(p[tri[0]], p[tri[1]], p[i]) >= 0.0
&& orient(p[tri[1]], p[tri[2]], p[i]) >= 0.0
&& orient(p[tri[2]], p[tri[0]], p[i]) >= 0.0
});
if !inside {
directed.clear();
directed.reserve(tris.len() * 3);
for tri in &tris {
for e in 0..3 {
directed.insert((tri[e] as u32, tri[(e + 1) % 3] as u32));
}
}
for tri in &tris {
for e in 0..3 {
let (u, v) = (tri[e], tri[(e + 1) % 3]);
if directed.contains(&(v as u32, u as u32)) {
continue; }
if orient(p[u], p[v], p[i]) < 0.0 {
cavity.push((v, u));
}
}
}
}
for a in 0..cavity.len() {
let (u, v) = cavity[a];
let shared = cavity
.iter()
.enumerate()
.any(|(b, &(x, y))| b != a && ((x == u && y == v) || (x == v && y == u)));
if !shared {
fresh.push([u, v, i]);
}
}
if fresh.is_empty() {
debug_assert!(bad.is_empty(), "cavity vanished around {} bad triangles", bad.len());
continue;
}
for &t in bad.iter().rev() {
tris.swap_remove(t);
}
tris.append(&mut fresh);
}
tris.into_iter()
.map(|t| {
if orient(p[t[0]], p[t[1]], p[t[2]]) < 0.0 {
[t[0] as u32, t[2] as u32, t[1] as u32]
} else {
[t[0] as u32, t[1] as u32, t[2] as u32]
}
})
.collect()
}
pub fn convex_hull(points: &[Vector2]) -> Vec<u32> {
if points.len() < 3 {
return (0..points.len() as u32).collect();
}
let mut order: Vec<u32> = (0..points.len() as u32).collect();
order.sort_by(|&a, &b| {
let (pa, pb) = (points[a as usize], points[b as usize]);
pa.x
.partial_cmp(&pb.x)
.unwrap_or(std::cmp::Ordering::Equal)
.then(pa.y.partial_cmp(&pb.y).unwrap_or(std::cmp::Ordering::Equal))
});
order.dedup_by(|a, b| points[*a as usize] == points[*b as usize]);
if order.len() < 3 {
return order;
}
let cross = |o: u32, a: u32, b: u32| {
let (o, a, b) = (
points[o as usize],
points[a as usize],
points[b as usize],
);
orient(
[o.x as f64, o.y as f64],
[a.x as f64, a.y as f64],
[b.x as f64, b.y as f64],
)
};
let mut hull: Vec<u32> = Vec::with_capacity(order.len() + 1);
for &i in &order {
while hull.len() >= 2 && cross(hull[hull.len() - 2], hull[hull.len() - 1], i) <= 0.0 {
hull.pop();
}
hull.push(i);
}
let lower = hull.len() + 1;
for &i in order.iter().rev() {
while hull.len() >= lower && cross(hull[hull.len() - 2], hull[hull.len() - 1], i) <= 0.0 {
hull.pop();
}
hull.push(i);
}
hull.pop();
hull
}
pub fn voronoi_cells(sites: &[Vector2], bounds: Box2) -> Vec<Vec<Vector2>> {
match delaunay_neighbours(sites) {
Some(adjacency) => voronoi_from_adjacency(sites, bounds, &adjacency),
None => voronoi_all_pairs(sites, bounds),
}
}
fn delaunay_neighbours(sites: &[Vector2]) -> Option<Vec<Vec<u32>>> {
let tris = delaunay(sites);
let mut adjacency: Vec<Vec<u32>> = vec![Vec::new(); sites.len()];
for t in &tris {
for k in 0..3 {
let (a, b) = (t[k], t[(k + 1) % 3]);
if !adjacency[a as usize].contains(&b) {
adjacency[a as usize].push(b);
}
if !adjacency[b as usize].contains(&a) {
adjacency[b as usize].push(a);
}
}
}
if adjacency.iter().any(|a| a.is_empty()) {
return None;
}
Some(adjacency)
}
fn bounds_polygon(bounds: Box2) -> [Vector2; 4] {
[
Vector2::new(bounds.min.x, bounds.min.y),
Vector2::new(bounds.max.x, bounds.min.y),
Vector2::new(bounds.max.x, bounds.max.y),
Vector2::new(bounds.min.x, bounds.max.y),
]
}
fn clip_by_bisector(
cell: &mut Vec<Vector2>,
scratch: &mut Vec<Vector2>,
s: Vector2,
o: Vector2,
) -> bool {
let d = Vector2::new(o.x - s.x, o.y - s.y);
if d.x * d.x + d.y * d.y < 1e-20 {
cell.clear();
return false;
}
let mid = Vector2::new((s.x + o.x) * 0.5, (s.y + o.y) * 0.5);
clip_half_plane(cell, mid, d, scratch);
std::mem::swap(cell, scratch);
true
}
fn voronoi_from_adjacency(
sites: &[Vector2],
bounds: Box2,
adjacency: &[Vec<u32>],
) -> Vec<Vec<Vector2>> {
let rect = bounds_polygon(bounds);
let mut cell: Vec<Vector2> = Vec::with_capacity(16);
let mut scratch: Vec<Vector2> = Vec::with_capacity(16);
let mut out = Vec::with_capacity(sites.len());
for (i, &s) in sites.iter().enumerate() {
cell.clear();
cell.extend_from_slice(&rect);
for &j in &adjacency[i] {
if cell.is_empty() {
break;
}
if !clip_by_bisector(&mut cell, &mut scratch, s, sites[j as usize]) {
break;
}
}
out.push(cell.clone());
}
out
}
fn voronoi_all_pairs(sites: &[Vector2], bounds: Box2) -> Vec<Vec<Vector2>> {
let rect = bounds_polygon(bounds);
let mut cell: Vec<Vector2> = Vec::with_capacity(16);
let mut scratch: Vec<Vector2> = Vec::with_capacity(16);
let mut out = Vec::with_capacity(sites.len());
for (i, &s) in sites.iter().enumerate() {
cell.clear();
cell.extend_from_slice(&rect);
for (j, &o) in sites.iter().enumerate() {
if i == j || cell.is_empty() {
continue;
}
if !clip_by_bisector(&mut cell, &mut scratch, s, o) {
break;
}
}
out.push(cell.clone());
}
out
}
fn clip_half_plane(poly: &[Vector2], point: Vector2, normal: Vector2, out: &mut Vec<Vector2>) {
out.clear();
if poly.is_empty() {
return;
}
let side = |p: Vector2| (p.x - point.x) * normal.x + (p.y - point.y) * normal.y;
for i in 0..poly.len() {
let a = poly[i];
let b = poly[(i + 1) % poly.len()];
let (sa, sb) = (side(a), side(b));
if sa <= 0.0 {
out.push(a);
}
if (sa <= 0.0) != (sb <= 0.0) {
let t = sa / (sa - sb);
out.push(Vector2::new(a.x + (b.x - a.x) * t, a.y + (b.y - a.y) * t));
}
}
}
pub fn triangulate_polygon(outer: &[[f64; 2]], holes: &[Vec<[f64; 2]>]) -> Vec<[u32; 3]> {
use crate::curves::shapes::{shape_utils, Vec2d};
let ring = |r: &[[f64; 2]]| -> Vec<Vec2d> { open_ring(r).iter().map(|p| Vec2d::new(p[0], p[1])).collect() };
let mut contour = ring(outer);
let mut hs: Vec<Vec<Vec2d>> = holes.iter().map(|h| ring(h)).collect();
if contour.len() < 3 {
return Vec::new();
}
shape_utils::triangulate_shape(&mut contour, &mut hs)
}
pub fn polygon_points(outer: &[[f64; 2]], holes: &[Vec<[f64; 2]>]) -> Vec<[f64; 2]> {
let mut out = open_ring(outer).to_vec();
for h in holes {
out.extend_from_slice(open_ring(h));
}
out
}
pub(crate) fn open_ring(ring: &[[f64; 2]]) -> &[[f64; 2]] {
match ring {
[first, .., last] if ring.len() > 2 && first == last => &ring[..ring.len() - 1],
_ => ring,
}
}
#[cfg(test)]
mod tests {
use super::*;
fn grid(n: usize) -> Vec<Vector2> {
seeded_grid(n, 0x5EED)
}
fn seeded_grid(n: usize, seed: u64) -> Vec<Vector2> {
let mut rng = crate::math::Rng::new(seed);
let mut out = Vec::new();
for y in 0..n {
for x in 0..n {
out.push(Vector2::new(
x as f32 + rng.range(-0.18, 0.18),
y as f32 + rng.range(-0.18, 0.18),
));
}
}
out
}
fn shoelace(poly: &[Vector2]) -> f64 {
let mut two = 0.0f64;
for w in 0..poly.len() {
let a = poly[w];
let b = poly[(w + 1) % poly.len()];
two += a.x as f64 * b.y as f64 - b.x as f64 * a.y as f64;
}
two.abs() * 0.5
}
fn area_of(p: &[Vector2], tris: &[[u32; 3]]) -> f64 {
let c = |i: u32| [p[i as usize].x as f64, p[i as usize].y as f64];
tris.iter()
.map(|t| orient(c(t[0]), c(t[1]), c(t[2])).abs() * 0.5)
.sum()
}
fn hull_area_of(p: &[Vector2], hull: &[u32]) -> f64 {
let c = |i: u32| [p[i as usize].x as f64, p[i as usize].y as f64];
let mut two = 0.0f64;
for w in 0..hull.len() {
let (a, b) = (c(hull[w]), c(hull[(w + 1) % hull.len()]));
two += a[0] * b[1] - b[0] * a[1];
}
two.abs() * 0.5
}
#[test]
fn the_triangulation_covers_its_own_hull() {
for n in [3usize, 4, 5, 8, 12] {
for seed in [0x5EED, 1, 2, 0xABCDEF] {
let p = seeded_grid(n, seed);
let tris = delaunay(&p);
let hull = convex_hull(&p);
let (got, want) = (area_of(&p, &tris), hull_area_of(&p, &hull));
assert!(
(got - want).abs() <= want * 1e-9,
"{n}x{n} seed {seed:#x}: triangles cover {got:.9} of a {want:.9} hull \
(deficit {:.3e})",
want - got
);
}
}
}
#[test]
fn cocircular_points_still_tile_their_hull() {
for count in [3usize, 4, 7, 32] {
let p: Vec<Vector2> = (0..count)
.map(|i| {
let a = i as f32 / count as f32 * std::f32::consts::TAU;
Vector2::new(a.cos() * 3.0, a.sin() * 3.0)
})
.collect();
let tris = delaunay(&p);
let hull = convex_hull(&p);
assert_eq!(hull.len(), count, "{count} on a circle are all hull points");
let (got, want) = (area_of(&p, &tris), hull_area_of(&p, &hull));
assert!(
(got - want).abs() <= want * 1e-6,
"{count} on a circle: covered {got:.9} of {want:.9}"
);
assert_eq!(tris.len(), count - 2, "a convex polygon fans into n-2");
}
}
#[test]
fn a_nearly_degenerate_strip_is_covered() {
let mut rng = crate::math::Rng::new(7);
let p: Vec<Vector2> = (0..40)
.map(|i| Vector2::new(i as f32 * 0.25, rng.range(-0.002, 0.002)))
.collect();
let tris = delaunay(&p);
let hull = convex_hull(&p);
let (got, want) = (area_of(&p, &tris), hull_area_of(&p, &hull));
assert!(
(got - want).abs() <= want * 1e-6,
"strip: covered {got:.9} of {want:.9}"
);
}
#[test]
fn a_square_is_two_triangles() {
let p = [
Vector2::new(0.0, 0.0),
Vector2::new(1.0, 0.0),
Vector2::new(1.0, 1.0),
Vector2::new(0.0, 1.0),
];
assert_eq!(delaunay(&p).len(), 2);
}
#[test]
fn the_triangle_count_matches_eulers_formula() {
for n in [3usize, 4, 5, 8, 12] {
for seed in [0x5EED, 1, 2, 0xABCDEF] {
let p = seeded_grid(n, seed);
let tris = delaunay(&p);
let hull = convex_hull(&p);
let expect = 2 * p.len() - hull.len() - 2;
assert_eq!(
tris.len(),
expect,
"{}x{} grid seed {:#x}: {} triangles for {} points and {} on the hull",
n,
n,
seed,
tris.len(),
p.len(),
hull.len()
);
}
}
}
#[test]
fn no_point_lies_inside_a_circumcircle() {
let p = grid(9);
let tris = delaunay(&p);
assert!(!tris.is_empty());
let c: Vec<[f64; 2]> = p.iter().map(|v| [v.x as f64, v.y as f64]).collect();
for t in &tris {
for (i, d) in c.iter().enumerate() {
if t.contains(&(i as u32)) {
continue;
}
let v = in_circle(
c[t[0] as usize],
c[t[1] as usize],
c[t[2] as usize],
*d,
);
assert!(
v <= 1e-6,
"point {i} is inside the circumcircle of {t:?} by {v:.3e}"
);
}
}
}
#[test]
fn every_triangle_comes_back_counter_clockwise() {
let p = grid(7);
let c: Vec<[f64; 2]> = p.iter().map(|v| [v.x as f64, v.y as f64]).collect();
for t in delaunay(&p) {
let a = orient(c[t[0] as usize], c[t[1] as usize], c[t[2] as usize]);
assert!(a > 0.0, "{t:?} is wound the other way (area {a:.3e})");
}
}
#[test]
fn degenerate_input_gives_no_triangles_rather_than_nonsense() {
assert!(delaunay(&[]).is_empty());
assert!(delaunay(&[Vector2::new(0.0, 0.0)]).is_empty());
let line: Vec<Vector2> = (0..8).map(|i| Vector2::new(i as f32, 0.0)).collect();
assert!(delaunay(&line).is_empty());
let dupes = vec![
Vector2::new(0.0, 0.0),
Vector2::new(1.0, 0.0),
Vector2::new(0.0, 1.0),
Vector2::new(0.0, 0.0),
];
assert_eq!(delaunay(&dupes).len(), 1);
}
#[test]
fn the_hull_is_its_corners_and_not_every_point_on_it() {
let p = vec![
Vector2::new(0.0, 0.0),
Vector2::new(2.0, 0.0),
Vector2::new(2.0, 2.0),
Vector2::new(0.0, 2.0),
Vector2::new(1.0, 0.0), Vector2::new(1.0, 1.0), ];
let hull = convex_hull(&p);
assert_eq!(hull.len(), 4, "got {hull:?}");
for i in [0u32, 1, 2, 3] {
assert!(hull.contains(&i), "corner {i} missing from {hull:?}");
}
}
#[test]
fn the_hull_is_counter_clockwise_and_contains_every_point() {
for n in [3usize, 4, 6, 9] {
for seed in [0x5EED, 1, 2, 0xABCDEF] {
check_hull(&seeded_grid(n, seed));
}
}
}
fn check_hull(p: &[Vector2]) {
let hull = convex_hull(p);
let c = |i: u32| {
let v = p[i as usize];
[v.x as f64, v.y as f64]
};
for w in 0..hull.len() {
let a = orient(
c(hull[w]),
c(hull[(w + 1) % hull.len()]),
c(hull[(w + 2) % hull.len()]),
);
assert!(a > -1e-9, "hull turns right at {w} ({a:.3e})");
}
for (i, q) in p.iter().enumerate() {
for w in 0..hull.len() {
let a = orient(c(hull[w]), c(hull[(w + 1) % hull.len()]), [
q.x as f64,
q.y as f64,
]);
assert!(a > -1e-6, "point {i} is outside hull edge {w}");
}
}
}
#[test]
fn every_cell_point_is_nearest_to_its_own_site() {
let sites = grid(5);
let bounds = Box2::new(Vector2::new(-1.0, -1.0), Vector2::new(5.0, 5.0));
let cells = voronoi_cells(&sites, bounds);
assert_eq!(cells.len(), sites.len());
let d2 = |a: Vector2, b: Vector2| (a.x - b.x).powi(2) + (a.y - b.y).powi(2);
for (i, cell) in cells.iter().enumerate() {
assert!(cell.len() >= 3, "cell {i} is degenerate: {cell:?}");
let n = cell.len() as f32;
let centroid = Vector2::new(
cell.iter().map(|p| p.x).sum::<f32>() / n,
cell.iter().map(|p| p.y).sum::<f32>() / n,
);
let own = d2(centroid, sites[i]);
for (j, s) in sites.iter().enumerate() {
if i != j {
assert!(
own <= d2(centroid, *s) + 1e-4,
"cell {i}'s centroid is nearer site {j}"
);
}
}
}
}
#[test]
fn the_cells_tile_the_bounds_exactly() {
let bounds = Box2::new(Vector2::new(-0.5, -0.5), Vector2::new(6.5, 6.5));
let want = 7.0f64 * 7.0;
for n in [2usize, 3, 5, 7] {
let sites = grid(n);
let cells = voronoi_cells(&sites, bounds);
let mut total = 0.0f64;
for cell in &cells {
assert!(cell.len() >= 3, "a site inside the bounds has a cell");
total += shoelace(cell);
}
assert!(
(total - want).abs() < want * 1e-4,
"{n}x{n} sites: cells cover {total:.6} of a {want:.6} rectangle"
);
}
}
#[test]
fn the_dual_shortcut_agrees_with_clipping_against_everything() {
let bounds = Box2::new(Vector2::new(-1.0, -1.0), Vector2::new(13.0, 13.0));
for n in [3usize, 5, 8, 12] {
for seed in [0x5EED, 1, 2, 0xABCDEF] {
let sites = seeded_grid(n, seed);
let fast = voronoi_cells(&sites, bounds);
let slow = voronoi_all_pairs(&sites, bounds);
assert!(
delaunay_neighbours(&sites).is_some(),
"{n}x{n} seed {seed:#x} should take the fast path"
);
assert_eq!(fast.len(), slow.len());
for (i, (f, s)) in fast.iter().zip(slow.iter()).enumerate() {
let sorted = |c: &[Vector2]| {
let mut v: Vec<(f32, f32)> = c.iter().map(|p| (p.x, p.y)).collect();
v.sort_by(|a, b| a.partial_cmp(b).unwrap());
v
};
let (fv, sv) = (sorted(f), sorted(s));
assert_eq!(
fv.len(),
sv.len(),
"cell {i} of {n}x{n} seed {seed:#x}: {f:?} vs {s:?}"
);
for (a, b) in fv.iter().zip(sv.iter()) {
assert!(
(a.0 - b.0).abs() < 1e-4 && (a.1 - b.1).abs() < 1e-4,
"cell {i} of {n}x{n} seed {seed:#x}: {a:?} vs {b:?}\n fast {f:?}\n slow {s:?}"
);
}
assert!(
(shoelace(f) - shoelace(s)).abs() < 1e-4,
"cell {i} area {} vs {}",
shoelace(f),
shoelace(s)
);
}
}
}
}
#[test]
fn degenerate_input_falls_back_to_all_pairs() {
let line: Vec<Vector2> = (0..6).map(|i| Vector2::new(i as f32, 0.0)).collect();
assert!(delaunay_neighbours(&line).is_none());
let bounds = Box2::new(Vector2::new(-1.0, -2.0), Vector2::new(6.0, 2.0));
let cells = voronoi_cells(&line, bounds);
let total: f64 = cells.iter().map(|c| shoelace(c)).sum();
assert!(
(total - 28.0).abs() < 1e-3,
"collinear sites: cells cover {total:.4} of 28.0"
);
let mut dupes = seeded_grid(3, 11);
dupes.push(dupes[4]);
assert!(delaunay_neighbours(&dupes).is_none());
let cells = voronoi_cells(&dupes, Box2::new(Vector2::new(-1.0, -1.0), Vector2::new(3.0, 3.0)));
assert!(
cells[4].is_empty() && cells[9].is_empty(),
"coincident sites have no cell: {:?} {:?}",
cells[4],
cells[9]
);
}
#[test]
fn cells_stay_inside_the_bounds_they_were_given() {
let sites = grid(4);
let bounds = Box2::new(Vector2::new(0.0, 0.0), Vector2::new(3.0, 3.0));
for cell in voronoi_cells(&sites, bounds) {
for p in cell {
assert!(
p.x >= -1e-4 && p.x <= 3.0 + 1e-4 && p.y >= -1e-4 && p.y <= 3.0 + 1e-4,
"{p:?} escaped the bounds"
);
}
}
}
#[test]
fn a_single_site_owns_the_whole_rectangle() {
let bounds = Box2::new(Vector2::new(0.0, 0.0), Vector2::new(2.0, 2.0));
let cells = voronoi_cells(&[Vector2::new(1.0, 1.0)], bounds);
assert_eq!(cells[0].len(), 4);
let dup = voronoi_cells(
&[Vector2::new(1.0, 1.0), Vector2::new(1.0, 1.0)],
bounds,
);
assert!(dup[0].is_empty() && dup[1].is_empty());
}
}