use super::delaunay2::Triangulation2;
use super::ids::{EdgeId, FaceId, VertexId};
use crate::predicates::{Orientation, Sign, circumcenter, incircle, orient2d};
use crate::primitives::{Point2, Vector2};
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct VoronoiCellId(pub(super) VertexId);
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct VoronoiVertexId(pub(super) u32);
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct VoronoiEdgeId(pub(super) u32);
#[non_exhaustive]
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum VoronoiEdgeKind {
Bounded {
vertices: [VoronoiVertexId; 2],
},
Unbounded {
finite_vertex: VoronoiVertexId,
},
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct VoronoiEdge {
pub cells: [VoronoiCellId; 2],
pub source_edge: EdgeId,
pub kind: VoronoiEdgeKind,
}
#[non_exhaustive]
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum VoronoiGeometryError {
NonFiniteCircumcenter,
InvalidTopology,
}
#[non_exhaustive]
#[derive(Debug, Clone, Copy, PartialEq)]
pub enum VoronoiEdgeGeometry {
Segment {
start: Point2,
end: Point2,
},
Ray {
origin: Point2,
direction: Vector2,
},
}
#[derive(Debug, Clone, PartialEq)]
pub struct Voronoi2 {
delaunay: Triangulation2,
face_group: Vec<VoronoiVertexId>,
group_faces: Vec<Vec<FaceId>>,
edges: Vec<VoronoiEdge>,
}
struct UnionFind {
parent: Vec<u32>,
}
impl UnionFind {
fn new(n: usize) -> Self {
UnionFind {
parent: (0..n as u32).collect(),
}
}
fn find(&mut self, x: u32) -> u32 {
if self.parent[x as usize] != x {
let root = self.find(self.parent[x as usize]);
self.parent[x as usize] = root;
}
self.parent[x as usize]
}
fn union(&mut self, a: u32, b: u32) {
let ra = self.find(a);
let rb = self.find(b);
if ra != rb {
self.parent[ra as usize] = rb;
}
}
}
fn group_key(delaunay: &Triangulation2, faces: &[FaceId]) -> Vec<u32> {
let mut verts: Vec<u32> = faces
.iter()
.flat_map(|&f| delaunay.face_vertices(f))
.map(VertexId::raw)
.collect();
verts.sort_unstable();
verts.dedup();
verts
}
fn edge_key(cells: [VoronoiCellId; 2]) -> [u32; 2] {
let mut k = [cells[0].0.raw(), cells[1].0.raw()];
k.sort_unstable();
k
}
fn third_vertex(delaunay: &Triangulation2, face: FaceId, u: VertexId, v: VertexId) -> VertexId {
delaunay
.face_vertices(face)
.into_iter()
.find(|&w| w != u && w != v)
.expect("a triangle's vertices must include a 3rd vertex besides its shared edge's two")
}
fn edge_vector(pu: Point2, pv: Point2) -> Vector2 {
let dx = pv.x() - pu.x();
let dy = pv.y() - pu.y();
if dx.is_finite() && dy.is_finite() {
return Vector2::new_unchecked(dx, dy);
}
let s = 2f64.powi(-600);
Vector2::new_unchecked(pv.x() * s - pu.x() * s, pv.y() * s - pu.y() * s)
}
pub fn voronoi2(delaunay: Triangulation2) -> Voronoi2 {
let n_faces = delaunay.faces().count();
let mut uf = UnionFind::new(n_faces);
let coord: Vec<_> = delaunay.vertices().map(|(_, p)| p).collect();
for edge in delaunay.edges() {
if let [Some(f1), Some(f2)] = delaunay.adjacent_faces(edge) {
let (u, v) = delaunay.edge_vertices(edge);
let a = third_vertex(&delaunay, f1, u, v);
let b = third_vertex(&delaunay, f2, u, v);
let cocircular = incircle(
coord[u.raw() as usize],
coord[v.raw() as usize],
coord[a.raw() as usize],
coord[b.raw() as usize],
) == Sign::Zero;
if cocircular {
uf.union(f1.raw(), f2.raw());
}
}
}
let mut by_root: std::collections::HashMap<u32, Vec<FaceId>> = std::collections::HashMap::new();
for f in delaunay.faces() {
by_root.entry(uf.find(f.raw())).or_default().push(f);
}
let mut keyed_groups: Vec<(Vec<u32>, Vec<FaceId>)> = by_root
.into_values()
.map(|mut faces| {
faces.sort_unstable_by_key(|f| f.raw());
(group_key(&delaunay, &faces), faces)
})
.collect();
keyed_groups.sort_unstable_by(|a, b| a.0.cmp(&b.0));
let mut face_group = vec![VoronoiVertexId(0); n_faces];
let mut group_faces = Vec::with_capacity(keyed_groups.len());
for (i, (_, faces)) in keyed_groups.into_iter().enumerate() {
for &f in &faces {
face_group[f.raw() as usize] = VoronoiVertexId(i as u32);
}
group_faces.push(faces);
}
let mut raw_edges: Vec<VoronoiEdge> = Vec::new();
for edge in delaunay.edges() {
let (u, v) = delaunay.edge_vertices(edge);
let cells = [VoronoiCellId(u), VoronoiCellId(v)];
match delaunay.adjacent_faces(edge) {
[Some(f), None] | [None, Some(f)] => {
raw_edges.push(VoronoiEdge {
cells,
source_edge: edge,
kind: VoronoiEdgeKind::Unbounded {
finite_vertex: face_group[f.raw() as usize],
},
});
}
[Some(f1), Some(f2)] => {
let g1 = face_group[f1.raw() as usize];
let g2 = face_group[f2.raw() as usize];
if g1 != g2 {
raw_edges.push(VoronoiEdge {
cells,
source_edge: edge,
kind: VoronoiEdgeKind::Bounded { vertices: [g1, g2] },
});
}
}
[None, None] => unreachable!("a Triangulation2 edge always has at least one face"),
}
}
raw_edges.sort_unstable_by_key(|e| edge_key(e.cells));
Voronoi2 {
delaunay,
face_group,
group_faces,
edges: raw_edges,
}
}
impl Voronoi2 {
pub fn cells(&self) -> impl Iterator<Item = VoronoiCellId> + '_ {
self.delaunay.vertices().map(|(v, _)| VoronoiCellId(v))
}
pub fn vertices(&self) -> impl Iterator<Item = VoronoiVertexId> + '_ {
(0..self.group_faces.len()).map(|i| VoronoiVertexId(i as u32))
}
pub fn edges(&self) -> impl Iterator<Item = VoronoiEdgeId> + '_ {
(0..self.edges.len()).map(|i| VoronoiEdgeId(i as u32))
}
pub fn cell_site(&self, cell: VoronoiCellId) -> VertexId {
cell.0
}
pub fn neighboring_cells(
&self,
cell: VoronoiCellId,
) -> impl Iterator<Item = VoronoiCellId> + '_ {
self.edges.iter().filter_map(move |e| {
if e.cells[0] == cell {
Some(e.cells[1])
} else if e.cells[1] == cell {
Some(e.cells[0])
} else {
None
}
})
}
pub fn cell_is_unbounded(&self, cell: VoronoiCellId) -> bool {
self.edges.iter().any(|e| {
(e.cells[0] == cell || e.cells[1] == cell)
&& matches!(e.kind, VoronoiEdgeKind::Unbounded { .. })
})
}
pub fn edge_cells(&self, edge: VoronoiEdgeId) -> [VoronoiCellId; 2] {
self.edges[edge.0 as usize].cells
}
pub fn edge_kind(&self, edge: VoronoiEdgeId) -> &VoronoiEdgeKind {
&self.edges[edge.0 as usize].kind
}
pub fn dual_delaunay_edge(&self, edge: VoronoiEdgeId) -> EdgeId {
self.edges[edge.0 as usize].source_edge
}
pub fn vertex_delaunay_faces(&self, vertex: VoronoiVertexId) -> &[FaceId] {
&self.group_faces[vertex.0 as usize]
}
pub fn cell_edges(&self, cell: VoronoiCellId) -> impl Iterator<Item = VoronoiEdgeId> + '_ {
let s = cell.0;
let mut result = Vec::new();
if let Some(f0) = self
.delaunay
.faces()
.find(|&f| self.delaunay.face_vertices(f).contains(&s))
{
let i0 = self.local_index(f0, s);
let mut face = f0;
let mut i = i0;
let mut is_cycle = false;
loop {
let (_, next) = self.backward_step(face, i);
match next {
None => break,
Some(nf) if nf == f0 => {
is_cycle = true;
break;
}
Some(nf) => {
face = nf;
i = self.local_index(nf, s);
}
}
}
let (start_face, start_i) = if is_cycle { (f0, i0) } else { (face, i) };
let mut face = start_face;
let mut i = start_i;
if !is_cycle {
let (entry_other, _) = self.backward_step(face, i);
if let Some(id) = self.edge_id_between(s, entry_other) {
result.push(id);
}
}
loop {
let (other, next) = self.forward_step(face, i);
if let Some(id) = self.edge_id_between(s, other) {
result.push(id);
}
match next {
Some(nf) if is_cycle && nf == start_face => break,
Some(nf) => {
face = nf;
i = self.local_index(nf, s);
}
None => break,
}
}
}
result.into_iter()
}
pub fn vertex_point(&self, vertex: VoronoiVertexId) -> Result<Point2, VoronoiGeometryError> {
let face = self.canonical_representative_face(vertex)?;
let [a, b, c] = self.delaunay.face_vertices(face);
let (pa, pb, pc) = (
self.delaunay.vertex_point(a),
self.delaunay.vertex_point(b),
self.delaunay.vertex_point(c),
);
circumcenter(pa, pb, pc).ok_or(VoronoiGeometryError::NonFiniteCircumcenter)
}
pub fn edge_geometry(
&self,
edge: VoronoiEdgeId,
) -> Result<VoronoiEdgeGeometry, VoronoiGeometryError> {
match self.edges[edge.0 as usize].kind {
VoronoiEdgeKind::Bounded { vertices: [v0, v1] } => {
let start = self.vertex_point(v0)?;
let end = self.vertex_point(v1)?;
Ok(VoronoiEdgeGeometry::Segment { start, end })
}
VoronoiEdgeKind::Unbounded { finite_vertex } => {
let origin = self.vertex_point(finite_vertex)?;
let source_edge = self.edges[edge.0 as usize].source_edge;
let (u, v) = self.delaunay.edge_vertices(source_edge);
let face = self
.delaunay
.adjacent_faces(source_edge)
.into_iter()
.flatten()
.next()
.ok_or(VoronoiGeometryError::InvalidTopology)?;
let w = third_vertex(&self.delaunay, face, u, v);
let direction = self.outward_ray_direction(u, v, w);
Ok(VoronoiEdgeGeometry::Ray { origin, direction })
}
}
}
fn canonical_representative_face(
&self,
vertex: VoronoiVertexId,
) -> Result<FaceId, VoronoiGeometryError> {
self.group_faces[vertex.0 as usize]
.iter()
.copied()
.min_by_key(|&f| {
let mut verts = self.delaunay.face_vertices(f).map(VertexId::raw);
verts.sort_unstable();
verts
})
.ok_or(VoronoiGeometryError::InvalidTopology)
}
fn outward_ray_direction(&self, u: VertexId, v: VertexId, w: VertexId) -> Vector2 {
let pu = self.delaunay.vertex_point(u);
let pv = self.delaunay.vertex_point(v);
let pw = self.delaunay.vertex_point(w);
let edge = edge_vector(pu, pv);
let perp = Vector2::new_unchecked(-edge.y(), edge.x());
if orient2d(pu, pv, pw) == Orientation::CounterClockwise {
-perp
} else {
perp
}
}
fn local_index(&self, face: FaceId, v: VertexId) -> usize {
self.delaunay
.face_vertices(face)
.iter()
.position(|&w| w == v)
.expect("`face` must be incident to `v`")
}
fn forward_step(&self, face: FaceId, i: usize) -> (VertexId, Option<FaceId>) {
let other = self.delaunay.face_vertices(face)[(i + 2) % 3];
let next = self.delaunay.neighboring_faces(face)[(i + 1) % 3];
(other, next)
}
fn backward_step(&self, face: FaceId, i: usize) -> (VertexId, Option<FaceId>) {
let other = self.delaunay.face_vertices(face)[(i + 1) % 3];
let next = self.delaunay.neighboring_faces(face)[(i + 2) % 3];
(other, next)
}
fn edge_id_between(&self, a: VertexId, b: VertexId) -> Option<VoronoiEdgeId> {
let target = [VoronoiCellId(a), VoronoiCellId(b)];
self.edges
.iter()
.position(|e| e.cells == target || e.cells == [target[1], target[0]])
.map(|idx| VoronoiEdgeId(idx as u32))
}
}
#[doc(hidden)]
#[derive(Debug, Clone, PartialEq)]
#[non_exhaustive]
pub enum VoronoiTopologyError {
FaceGroupNotInverse {
face: FaceId,
},
GroupsNotCanonicallyOrdered {
at: usize,
},
EdgesNotCanonicallyOrdered {
at: usize,
},
MissingVoronoiEdge {
source_edge: EdgeId,
},
EdgeMismatch {
source_edge: EdgeId,
},
NonDistinctEdgeCells {
edge: VoronoiEdgeId,
},
NonDistinctBoundedVertices {
edge: VoronoiEdgeId,
},
UnboundedEdgeNotHullDual {
edge: VoronoiEdgeId,
},
DuplicateFaceInGroup {
vertex: VoronoiVertexId,
face: FaceId,
},
EdgeNotInExactlyTwoCellBoundaries {
edge: VoronoiEdgeId,
count: usize,
},
}
impl Voronoi2 {
#[doc(hidden)]
pub fn validate_voronoi_topology(&self) -> Vec<VoronoiTopologyError> {
let mut errors = Vec::new();
for (i, faces) in self.group_faces.iter().enumerate() {
for &f in faces {
if self.face_group[f.raw() as usize] != VoronoiVertexId(i as u32) {
errors.push(VoronoiTopologyError::FaceGroupNotInverse { face: f });
}
}
}
for f in self.delaunay.faces() {
let g = self.face_group[f.raw() as usize];
if !self.group_faces[g.0 as usize].contains(&f) {
errors.push(VoronoiTopologyError::FaceGroupNotInverse { face: f });
}
}
for (i, w) in self.group_faces.windows(2).enumerate() {
let ka = group_key(&self.delaunay, &w[0]);
let kb = group_key(&self.delaunay, &w[1]);
if ka >= kb {
errors.push(VoronoiTopologyError::GroupsNotCanonicallyOrdered { at: i + 1 });
}
}
for (i, w) in self.edges.windows(2).enumerate() {
if edge_key(w[0].cells) >= edge_key(w[1].cells) {
errors.push(VoronoiTopologyError::EdgesNotCanonicallyOrdered { at: i + 1 });
}
}
for source_edge in self.delaunay.edges() {
let (u, v) = self.delaunay.edge_vertices(source_edge);
let expected_cells = [VoronoiCellId(u), VoronoiCellId(v)];
let expected_kind = match self.delaunay.adjacent_faces(source_edge) {
[Some(f), None] | [None, Some(f)] => Some(VoronoiEdgeKind::Unbounded {
finite_vertex: self.face_group[f.raw() as usize],
}),
[Some(f1), Some(f2)] => {
let g1 = self.face_group[f1.raw() as usize];
let g2 = self.face_group[f2.raw() as usize];
if g1 != g2 {
Some(VoronoiEdgeKind::Bounded { vertices: [g1, g2] })
} else {
None
}
}
[None, None] => None,
};
let actual = self.edges.iter().find(|e| e.source_edge == source_edge);
match (expected_kind, actual) {
(None, Some(_)) => errors.push(VoronoiTopologyError::EdgeMismatch { source_edge }),
(Some(_), None) => {
errors.push(VoronoiTopologyError::MissingVoronoiEdge { source_edge })
}
(Some(expected), Some(actual)) => {
if actual.cells != expected_cells || actual.kind != expected {
errors.push(VoronoiTopologyError::EdgeMismatch { source_edge });
}
}
(None, None) => {}
}
}
for (i, faces) in self.group_faces.iter().enumerate() {
let mut seen = std::collections::HashSet::new();
for &f in faces {
if !seen.insert(f) {
errors.push(VoronoiTopologyError::DuplicateFaceInGroup {
vertex: VoronoiVertexId(i as u32),
face: f,
});
}
}
}
for (i, e) in self.edges.iter().enumerate() {
let edge = VoronoiEdgeId(i as u32);
if e.cells[0] == e.cells[1] {
errors.push(VoronoiTopologyError::NonDistinctEdgeCells { edge });
}
match e.kind {
VoronoiEdgeKind::Bounded { vertices } => {
if vertices[0] == vertices[1] {
errors.push(VoronoiTopologyError::NonDistinctBoundedVertices { edge });
}
}
VoronoiEdgeKind::Unbounded { .. } => {
let is_hull_edge = matches!(
self.delaunay.adjacent_faces(e.source_edge),
[Some(_), None] | [None, Some(_)]
);
if !is_hull_edge {
errors.push(VoronoiTopologyError::UnboundedEdgeNotHullDual { edge });
}
}
}
}
let mut boundary_counts = vec![0usize; self.edges.len()];
for cell in self.cells() {
for edge in self.cell_edges(cell) {
boundary_counts[edge.0 as usize] += 1;
}
}
for (i, &count) in boundary_counts.iter().enumerate() {
if count != 2 {
errors.push(VoronoiTopologyError::EdgeNotInExactlyTwoCellBoundaries {
edge: VoronoiEdgeId(i as u32),
count,
});
}
}
errors
}
}
#[cfg(test)]
mod tests {
use super::super::delaunay2::{assemble_triangulation, delaunay2};
use super::*;
use crate::primitives::Point2;
fn pt(x: f64, y: f64) -> Point2 {
Point2::new(x, y).unwrap()
}
#[test]
fn single_triangle_has_one_group_and_three_unbounded_edges() {
let pts = vec![pt(0.0, 0.0), pt(1.0, 0.0), pt(0.0, 1.0)];
let v = voronoi2(delaunay2(&pts));
assert_eq!(v.group_faces.len(), 1);
assert_eq!(v.edges.len(), 3);
assert!(
v.edges
.iter()
.all(|e| matches!(e.kind, VoronoiEdgeKind::Unbounded { .. }))
);
assert!(v.validate_voronoi_topology().is_empty());
}
#[test]
fn axis_aligned_square_merges_both_faces_into_one_group() {
let pts = vec![pt(0.0, 0.0), pt(2.0, 0.0), pt(2.0, 2.0), pt(0.0, 2.0)];
let v = voronoi2(delaunay2(&pts));
assert_eq!(
v.group_faces.len(),
1,
"the diagonal split by delaunay2's tie-break must not leak as 2 Voronoi vertices"
);
assert_eq!(
v.edges.len(),
4,
"the 4 hull edges are Unbounded; the interior diagonal is same-group and excluded"
);
assert!(
v.edges
.iter()
.all(|e| matches!(e.kind, VoronoiEdgeKind::Unbounded { .. }))
);
assert!(v.validate_voronoi_topology().is_empty());
}
#[test]
fn generic_position_random_points_pass_validation() {
struct Xorshift64(u64);
impl Xorshift64 {
fn next_u64(&mut self) -> u64 {
let mut x = self.0;
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
self.0 = x;
x
}
fn next_f64_in(&mut self, scale: f64) -> f64 {
let bits = self.next_u64();
let unit = (bits >> 11) as f64 * (1.0 / (1u64 << 53) as f64);
(unit * 2.0 - 1.0) * scale
}
}
let mut rng = Xorshift64(0x9e3779b97f4a7c15);
let pts: Vec<Point2> = (0..60)
.map(|_| pt(rng.next_f64_in(100.0), rng.next_f64_in(100.0)))
.collect();
let v = voronoi2(delaunay2(&pts));
assert!(!v.group_faces.is_empty());
assert_eq!(v.validate_voronoi_topology(), Vec::new());
let hull_sites: std::collections::HashSet<VertexId> = v
.delaunay
.boundary_edges()
.flat_map(|e| {
let (a, b) = v.delaunay.edge_vertices(e);
[a, b]
})
.collect();
let mut saw_interior_cell = false;
for cell in v.cells() {
let expected_unbounded = hull_sites.contains(&v.cell_site(cell));
assert_eq!(v.cell_is_unbounded(cell), expected_unbounded);
if !expected_unbounded {
saw_interior_cell = true;
assert!(
v.neighboring_cells(cell).count() >= 3,
"an interior Voronoi cell in generic position has at least 3 neighbors"
);
}
}
assert!(
saw_interior_cell,
"a 60-point generic-position cloud must have at least one interior site"
);
}
fn cocircular_lattice_points(n: usize) -> Vec<Point2> {
const ALL: [(f64, f64); 12] = [
(5.0, 0.0),
(4.0, 3.0),
(3.0, 4.0),
(0.0, 5.0),
(-3.0, 4.0),
(-4.0, 3.0),
(-5.0, 0.0),
(-4.0, -3.0),
(-3.0, -4.0),
(0.0, -5.0),
(3.0, -4.0),
(4.0, -3.0),
];
assert!(n <= ALL.len());
ALL[..n].iter().map(|&(x, y)| pt(x, y)).collect()
}
fn fan_from(n: usize, start: usize) -> Vec<[VertexId; 3]> {
(1..n - 1)
.map(|i| {
let a = start % n;
let b = (start + i) % n;
let c = (start + i + 1) % n;
[VertexId(a as u32), VertexId(b as u32), VertexId(c as u32)]
})
.collect()
}
fn group_site_set(v: &Voronoi2, g: VoronoiVertexId) -> Vec<u32> {
group_key(&v.delaunay, &v.group_faces[g.0 as usize])
}
fn canonical_groups(v: &Voronoi2) -> Vec<Vec<u32>> {
v.group_faces
.iter()
.map(|faces| group_key(&v.delaunay, faces))
.collect()
}
fn canonical_edges(v: &Voronoi2) -> Vec<(Vec<u32>, Vec<Vec<u32>>)> {
let mut out: Vec<_> = v
.edges
.iter()
.map(|e| {
let cell_key = edge_key(e.cells).to_vec();
let mut endpoints: Vec<Vec<u32>> = match e.kind {
VoronoiEdgeKind::Bounded { vertices } => {
vertices.iter().map(|&g| group_site_set(v, g)).collect()
}
VoronoiEdgeKind::Unbounded { finite_vertex } => {
vec![group_site_set(v, finite_vertex)]
}
};
endpoints.sort();
(cell_key, endpoints)
})
.collect();
out.sort();
out
}
fn assert_single_cocircular_group(v: &Voronoi2, n_sites: usize) {
assert_eq!(v.group_faces.len(), 1);
assert_eq!(v.edges.len(), n_sites);
assert!(
v.edges
.iter()
.all(|e| matches!(e.kind, VoronoiEdgeKind::Unbounded { .. }))
);
assert!(v.validate_voronoi_topology().is_empty());
}
#[test]
fn square_both_diagonals_produce_identical_canonical_topology() {
let pts = vec![pt(0.0, 0.0), pt(2.0, 0.0), pt(2.0, 2.0), pt(0.0, 2.0)];
let diagonal_a = voronoi2(assemble_triangulation(pts.clone(), fan_from(4, 0)));
let diagonal_b = voronoi2(assemble_triangulation(pts, fan_from(4, 1)));
assert_single_cocircular_group(&diagonal_a, 4);
assert_single_cocircular_group(&diagonal_b, 4);
assert_eq!(canonical_groups(&diagonal_a), canonical_groups(&diagonal_b));
assert_eq!(canonical_edges(&diagonal_a), canonical_edges(&diagonal_b));
}
#[test]
fn five_cocircular_points_multiple_fans_produce_identical_canonical_topology() {
let pts = cocircular_lattice_points(5);
let fan_0 = voronoi2(assemble_triangulation(pts.clone(), fan_from(5, 0)));
let fan_2 = voronoi2(assemble_triangulation(pts, fan_from(5, 2)));
assert_single_cocircular_group(&fan_0, 5);
assert_single_cocircular_group(&fan_2, 5);
assert_eq!(canonical_groups(&fan_0), canonical_groups(&fan_2));
assert_eq!(canonical_edges(&fan_0), canonical_edges(&fan_2));
}
#[test]
fn eight_cocircular_points_multiple_fans_produce_identical_canonical_topology() {
let pts = cocircular_lattice_points(8);
let fan_0 = voronoi2(assemble_triangulation(pts.clone(), fan_from(8, 0)));
let fan_3 = voronoi2(assemble_triangulation(pts.clone(), fan_from(8, 3)));
let fan_6 = voronoi2(assemble_triangulation(pts, fan_from(8, 6)));
for v in [&fan_0, &fan_3, &fan_6] {
assert_single_cocircular_group(v, 8);
}
assert_eq!(canonical_groups(&fan_0), canonical_groups(&fan_3));
assert_eq!(canonical_groups(&fan_0), canonical_groups(&fan_6));
assert_eq!(canonical_edges(&fan_0), canonical_edges(&fan_3));
assert_eq!(canonical_edges(&fan_0), canonical_edges(&fan_6));
}
#[test]
fn vertex_point_matches_hand_computed_circumcenter() {
let pts = vec![pt(0.0, 0.0), pt(4.0, 0.0), pt(0.0, 4.0)];
let v = voronoi2(delaunay2(&pts));
let vertex = v.vertices().next().unwrap();
let p = v.vertex_point(vertex).unwrap();
assert_eq!((p.x(), p.y()), (2.0, 2.0));
}
#[test]
fn cocircular_group_circumcenter_identical_regardless_of_member_face() {
let pts = cocircular_lattice_points(8);
let v = voronoi2(assemble_triangulation(pts, fan_from(8, 0)));
assert_eq!(v.group_faces.len(), 1, "all 8 points share one circle");
let faces = &v.group_faces[0];
assert!(
faces.len() >= 3,
"expected a genuinely multi-face cocircular group"
);
let results: Vec<Point2> = faces
.iter()
.map(|&f| {
let [a, b, c] = v.delaunay.face_vertices(f);
circumcenter(
v.delaunay.vertex_point(a),
v.delaunay.vertex_point(b),
v.delaunay.vertex_point(c),
)
.expect("a fan triangle of cocircular points is never collinear")
})
.collect();
let first = results[0];
for &r in &results[1..] {
assert_eq!(
(r.x(), r.y()),
(first.x(), first.y()),
"circumcenter must be identical regardless of which member face computed it"
);
}
}
#[test]
fn thin_triangle_vertex_point_and_edge_geometry_return_err_not_panic() {
let l = 1e75;
let h = 1e-170;
let pts = vec![pt(0.0, 0.0), pt(l, 0.0), pt(l / 2.0, h)];
let v = voronoi2(delaunay2(&pts));
let vertex = v.vertices().next().unwrap();
assert_eq!(
v.vertex_point(vertex),
Err(VoronoiGeometryError::NonFiniteCircumcenter)
);
for edge in v.edges() {
assert_eq!(
v.edge_geometry(edge),
Err(VoronoiGeometryError::NonFiniteCircumcenter)
);
}
}
#[test]
fn empty_face_group_is_a_typed_error_not_a_panic() {
let pts = vec![pt(0.0, 0.0), pt(4.0, 0.0), pt(0.0, 4.0)];
let mut broken = voronoi2(delaunay2(&pts));
let vertex = broken.vertices().next().unwrap();
broken.group_faces[vertex.0 as usize].clear();
assert_eq!(
broken.vertex_point(vertex),
Err(VoronoiGeometryError::InvalidTopology)
);
for edge in broken.edges() {
assert_eq!(
broken.edge_geometry(edge),
Err(VoronoiGeometryError::InvalidTopology)
);
}
}
#[test]
fn unbounded_edge_missing_incident_face_is_a_typed_error_not_a_panic() {
let pts = vec![pt(0.0, 0.0), pt(4.0, 0.0), pt(0.0, 4.0)];
let mut broken = voronoi2(delaunay2(&pts));
let edge = broken
.edges()
.find(|&e| matches!(broken.edge_kind(e), VoronoiEdgeKind::Unbounded { .. }))
.expect("a single triangle's Voronoi diagram has 3 Unbounded hull edges");
let source_edge = broken.dual_delaunay_edge(edge);
broken.delaunay.clear_adjacent_faces_for_test(source_edge);
assert_eq!(
broken.edge_geometry(edge),
Err(VoronoiGeometryError::InvalidTopology)
);
}
#[test]
fn edge_geometry_segment_endpoints_match_vertex_point() {
let pts = vec![
pt(0.0, 0.0),
pt(4.0, 0.0),
pt(4.0, 4.0),
pt(0.0, 4.1), ];
let v = voronoi2(delaunay2(&pts));
let mut saw_bounded = false;
for edge in v.edges() {
if let VoronoiEdgeKind::Bounded { vertices } = *v.edge_kind(edge) {
saw_bounded = true;
let expected_start = v.vertex_point(vertices[0]).unwrap();
let expected_end = v.vertex_point(vertices[1]).unwrap();
match v.edge_geometry(edge).unwrap() {
VoronoiEdgeGeometry::Segment { start, end } => {
assert_eq!(
(start.x(), start.y()),
(expected_start.x(), expected_start.y())
);
assert_eq!((end.x(), end.y()), (expected_end.x(), expected_end.y()));
}
VoronoiEdgeGeometry::Ray { .. } => panic!("Bounded edge produced a Ray"),
}
}
}
assert!(
saw_bounded,
"expected at least one Bounded edge in this fixture"
);
}
#[test]
fn edge_geometry_ray_points_away_from_third_vertex() {
let pts = vec![pt(0.0, 0.0), pt(4.0, 0.0), pt(0.0, 4.0)];
let v = voronoi2(delaunay2(&pts));
for edge in v.edges() {
let VoronoiEdgeKind::Unbounded { finite_vertex } = *v.edge_kind(edge) else {
continue;
};
let expected_origin = v.vertex_point(finite_vertex).unwrap();
let source_edge = v.dual_delaunay_edge(edge);
let (u, w) = v.delaunay.edge_vertices(source_edge);
let face = v
.delaunay
.adjacent_faces(source_edge)
.into_iter()
.flatten()
.next()
.expect("a boundary Delaunay edge has exactly 1 incident face");
let third = third_vertex(&v.delaunay, face, u, w);
let pu = v.delaunay.vertex_point(u);
let pw = v.delaunay.vertex_point(w);
let pthird = v.delaunay.vertex_point(third);
match v.edge_geometry(edge).unwrap() {
VoronoiEdgeGeometry::Ray { origin, direction } => {
assert_eq!(
(origin.x(), origin.y()),
(expected_origin.x(), expected_origin.y())
);
let probe = origin + direction;
assert_ne!(
orient2d(pu, pw, pthird),
orient2d(pu, pw, probe),
"ray direction must point to the opposite side of the boundary \
edge from the triangle's third vertex"
);
}
VoronoiEdgeGeometry::Segment { .. } => panic!("Unbounded edge produced a Segment"),
}
}
}
#[test]
fn ray_direction_correct_side_survives_large_offset_precision_loss() {
let p0 = pt(1e20, 0.0);
let p1 = pt(1e20, 5.0);
let p2 = pt(1e20 - 50000.0, 2.5);
assert_ne!(
p2.x(),
p0.x(),
"fixture requires a genuinely distinct 3rd point"
);
let v = voronoi2(delaunay2(&[p0, p1, p2]));
let mut checked = 0;
for edge in v.edges() {
if !matches!(v.edge_kind(edge), VoronoiEdgeKind::Unbounded { .. }) {
continue;
}
let source_edge = v.dual_delaunay_edge(edge);
let (du, dv) = v.delaunay.edge_vertices(source_edge);
let face = v
.delaunay
.adjacent_faces(source_edge)
.into_iter()
.flatten()
.next()
.expect("a boundary Delaunay edge has exactly 1 incident face");
let third = third_vertex(&v.delaunay, face, du, dv);
let pu = v.delaunay.vertex_point(du);
let pv = v.delaunay.vertex_point(dv);
let pw = v.delaunay.vertex_point(third);
let direction = v.outward_ray_direction(du, dv, third);
let edge_vec = (pv.x() - pu.x(), pv.y() - pu.y());
let w_vec = (pw.x() - pu.x(), pw.y() - pu.y());
let cross = |a: (f64, f64), b: (f64, f64)| a.0 * b.1 - a.1 * b.0;
let side_w = cross(edge_vec, w_vec);
let side_dir = cross(edge_vec, (direction.x(), direction.y()));
assert!(
side_w.signum() != side_dir.signum(),
"direction must point to the opposite side from the third vertex \
(side_w={side_w}, side_dir={side_dir})"
);
checked += 1;
}
assert_eq!(checked, 3, "a single triangle has exactly 3 hull edges");
}
#[test]
fn edge_vector_finite_and_nonzero_at_opposite_sign_near_f64_max() {
let cases = [
(pt(-f64::MAX, 0.0), pt(f64::MAX, 0.0)),
(pt(0.0, -f64::MAX), pt(0.0, f64::MAX)),
(pt(-f64::MAX, -f64::MAX), pt(f64::MAX, f64::MAX)),
(pt(-f64::MAX * 0.6, 3.0), pt(f64::MAX * 0.6, -3.0)),
];
for (pu, pv) in cases {
assert!(
!(pv.x() - pu.x()).is_finite() || !(pv.y() - pu.y()).is_finite(),
"fixture must actually overflow plain subtraction: pu={pu:?} pv={pv:?}"
);
let e = edge_vector(pu, pv);
assert!(
e.x().is_finite() && e.y().is_finite(),
"pu={pu:?} pv={pv:?} -> {e:?}"
);
assert!(
e.x() != 0.0 || e.y() != 0.0,
"pu={pu:?} pv={pv:?} -> zero vector"
);
}
}
#[test]
fn edge_vector_matches_plain_subtraction_below_overflow_threshold() {
let cases = [
(pt(0.0, 0.0), pt(1.0, 0.0)),
(pt(1e20, 0.0), pt(1e20, 5.0)),
(pt(-1e150, 2e100), pt(3e150, -4e100)),
];
for (pu, pv) in cases {
let e = edge_vector(pu, pv);
assert_eq!((e.x(), e.y()), (pv.x() - pu.x(), pv.y() - pu.y()));
}
}
#[test]
fn outward_ray_direction_correct_for_third_vertex_on_either_side() {
let pu = pt(0.0, 0.0);
let pv = pt(0.0, 10.0);
let left = pt(-5.0, 5.0);
let right = pt(5.0, 5.0);
for third in [left, right] {
let v = voronoi2(assemble_triangulation(
vec![pu, pv, third],
vec![[VertexId(0), VertexId(1), VertexId(2)]],
));
let direction = v.outward_ray_direction(VertexId(0), VertexId(1), VertexId(2));
assert!(direction.x().is_finite() && direction.y().is_finite());
assert!(direction.x() != 0.0 || direction.y() != 0.0);
let edge_vec = (pv.x() - pu.x(), pv.y() - pu.y());
let w_vec = (third.x() - pu.x(), third.y() - pu.y());
let cross = |a: (f64, f64), b: (f64, f64)| a.0 * b.1 - a.1 * b.0;
let side_w = cross(edge_vec, w_vec);
let side_dir = cross(edge_vec, (direction.x(), direction.y()));
assert!(
side_w.signum() != side_dir.signum(),
"third={third:?}: direction must point opposite the 3rd vertex \
(side_w={side_w}, side_dir={side_dir})"
);
}
}
#[test]
fn cocircular_cluster_plus_outlier_mixes_bounded_and_excluded_edges() {
let p0 = pt(0.0, 0.0);
let p1 = pt(2.0, 0.0);
let p2 = pt(2.0, 2.0);
let p3 = pt(0.0, 2.0);
let p4 = pt(6.0, 1.0);
let pts = vec![p0, p1, p2, p3, p4];
let faces = vec![
[VertexId(1), VertexId(4), VertexId(2)], [VertexId(0), VertexId(1), VertexId(2)], [VertexId(0), VertexId(2), VertexId(3)], ];
let v = voronoi2(assemble_triangulation(pts, faces));
assert_eq!(
v.group_faces.len(),
2,
"the square's 2 faces merge (cocircular); the ear stays its own group"
);
assert_eq!(
v.edges.len(),
6,
"7 Delaunay edges (5 hull + 2 interior) minus 1 excluded same-group diagonal"
);
let bounded: Vec<_> = v
.edges
.iter()
.filter(|e| matches!(e.kind, VoronoiEdgeKind::Bounded { .. }))
.collect();
assert_eq!(
bounded.len(),
1,
"only p1-p2 (square face vs. ear) is a genuine, non-cocircular interior edge"
);
match bounded[0].kind {
VoronoiEdgeKind::Bounded { vertices } => {
assert_ne!(
vertices[0], vertices[1],
"a Bounded edge must separate 2 distinct groups"
);
}
VoronoiEdgeKind::Unbounded { .. } => unreachable!(),
}
assert_eq!(
v.edges.len() - bounded.len(),
5,
"the remaining 5 edges are the pentagon's hull, all Unbounded"
);
assert!(v.validate_voronoi_topology().is_empty());
}
#[test]
fn query_api_matches_underlying_edge_and_group_data() {
let pts = vec![pt(0.0, 0.0), pt(2.0, 0.0), pt(2.0, 2.0), pt(0.0, 2.0)];
let v = voronoi2(delaunay2(&pts));
assert_eq!(v.cells().count(), v.delaunay.vertices().count());
assert_eq!(v.vertices().count(), v.group_faces.len());
assert_eq!(v.edges().count(), v.edges.len());
for (i, id) in v.edges().enumerate() {
let raw = &v.edges[i];
assert_eq!(v.edge_cells(id), raw.cells);
assert_eq!(*v.edge_kind(id), raw.kind);
assert_eq!(v.dual_delaunay_edge(id), raw.source_edge);
}
for (i, id) in v.vertices().enumerate() {
assert_eq!(v.vertex_delaunay_faces(id), v.group_faces[i].as_slice());
}
for cell in v.cells() {
assert_eq!(cell.0, v.cell_site(cell));
}
}
#[test]
fn neighboring_and_unbounded_queries_on_the_mixed_fixture() {
let pts = vec![
pt(0.0, 0.0),
pt(2.0, 0.0),
pt(2.0, 2.0),
pt(0.0, 2.0),
pt(6.0, 1.0),
];
let faces = vec![
[VertexId(1), VertexId(4), VertexId(2)],
[VertexId(0), VertexId(1), VertexId(2)],
[VertexId(0), VertexId(2), VertexId(3)],
];
let v = voronoi2(assemble_triangulation(pts, faces));
let p0 = VoronoiCellId(VertexId(0));
assert!(
v.cell_is_unbounded(p0),
"p0 is a hull vertex of the pentagon"
);
let neighbor_sites: Vec<VertexId> =
v.neighboring_cells(p0).map(|c| v.cell_site(c)).collect();
assert_eq!(
neighbor_sites.len(),
2,
"p0-p2 is cocircular and excluded, so p2 must not appear as a neighbor"
);
assert!(neighbor_sites.contains(&VertexId(1)));
assert!(neighbor_sites.contains(&VertexId(3)));
for cell in v.cells() {
for neighbor in v.neighboring_cells(cell).collect::<Vec<_>>() {
assert!(v.neighboring_cells(neighbor).any(|c| c == cell));
}
}
}
#[test]
fn validator_catches_deliberately_corrupted_invariants() {
let pts = vec![
pt(0.0, 0.0),
pt(2.0, 0.0),
pt(2.0, 2.0),
pt(0.0, 2.0),
pt(6.0, 1.0),
];
let faces = vec![
[VertexId(1), VertexId(4), VertexId(2)],
[VertexId(0), VertexId(1), VertexId(2)],
[VertexId(0), VertexId(2), VertexId(3)],
];
let valid = voronoi2(assemble_triangulation(pts, faces));
assert!(valid.validate_voronoi_topology().is_empty());
let bounded_i = valid
.edges
.iter()
.position(|e| matches!(e.kind, VoronoiEdgeKind::Bounded { .. }))
.expect("the fixture has exactly one Bounded edge (p1-p2)");
let unbounded_i = valid
.edges
.iter()
.position(|e| matches!(e.kind, VoronoiEdgeKind::Unbounded { .. }))
.expect("the fixture has 5 Unbounded hull edges");
let excluded_interior_edge = valid
.delaunay
.edges()
.find(|&e| {
matches!(valid.delaunay.adjacent_faces(e), [Some(_), Some(_)])
&& !valid.edges.iter().any(|ve| ve.source_edge == e)
})
.expect("the square's cocircular diagonal (p0-p2) is excluded and interior");
let mut broken = valid.clone();
broken.edges[bounded_i].cells[1] = broken.edges[bounded_i].cells[0];
assert!(broken.validate_voronoi_topology().contains(
&VoronoiTopologyError::NonDistinctEdgeCells {
edge: VoronoiEdgeId(bounded_i as u32)
}
));
let mut broken = valid.clone();
if let VoronoiEdgeKind::Bounded { vertices } = &mut broken.edges[bounded_i].kind {
vertices[1] = vertices[0];
}
assert!(broken.validate_voronoi_topology().contains(
&VoronoiTopologyError::NonDistinctBoundedVertices {
edge: VoronoiEdgeId(bounded_i as u32)
}
));
let mut broken = valid.clone();
broken.edges[unbounded_i].source_edge = excluded_interior_edge;
assert!(broken.validate_voronoi_topology().contains(
&VoronoiTopologyError::UnboundedEdgeNotHullDual {
edge: VoronoiEdgeId(unbounded_i as u32)
}
));
let mut broken = valid.clone();
let dup = broken.group_faces[0][0];
broken.group_faces[0].push(dup);
assert!(broken.validate_voronoi_topology().contains(
&VoronoiTopologyError::DuplicateFaceInGroup {
vertex: VoronoiVertexId(0),
face: dup,
}
));
}
fn other_cell_site(v: &Voronoi2, e: VoronoiEdgeId, this: VoronoiCellId) -> VertexId {
let [a, b] = v.edge_cells(e);
v.cell_site(if a == this { b } else { a })
}
#[test]
fn cell_edges_square_corner_is_exactly_two_rays() {
let pts = vec![pt(0.0, 0.0), pt(2.0, 0.0), pt(2.0, 2.0), pt(0.0, 2.0)];
let v = voronoi2(delaunay2(&pts));
for cell in v.cells() {
let edges: Vec<_> = v.cell_edges(cell).collect();
assert_eq!(edges.len(), 2);
assert!(
edges
.iter()
.all(|&e| matches!(v.edge_kind(e), VoronoiEdgeKind::Unbounded { .. }))
);
}
assert!(v.validate_voronoi_topology().is_empty());
}
#[test]
fn cell_edges_cocircular_ngon_multiple_triangulations_all_two_rays() {
for &n in &[5usize, 8] {
let pts = cocircular_lattice_points(n);
for start in [0, n / 2] {
let v = voronoi2(assemble_triangulation(pts.clone(), fan_from(n, start)));
for cell in v.cells() {
assert_eq!(
v.cell_edges(cell).count(),
2,
"n={n} start={start}: every site's cell must be exactly 2 rays \
once the whole n-gon merges into one Voronoi vertex"
);
}
assert!(v.validate_voronoi_topology().is_empty());
}
}
}
#[test]
fn cell_edges_partially_cocircular_fixture_matches_hand_verified_order() {
let pts = vec![
pt(0.0, 0.0),
pt(2.0, 0.0),
pt(2.0, 2.0),
pt(0.0, 2.0),
pt(6.0, 1.0),
];
let faces = vec![
[VertexId(1), VertexId(4), VertexId(2)],
[VertexId(0), VertexId(1), VertexId(2)],
[VertexId(0), VertexId(2), VertexId(3)],
];
let v = voronoi2(assemble_triangulation(pts, faces));
let p0 = VoronoiCellId(VertexId(0));
let p0_edges: Vec<_> = v.cell_edges(p0).collect();
assert_eq!(p0_edges.len(), 2);
assert_eq!(other_cell_site(&v, p0_edges[0], p0), VertexId(1));
assert_eq!(other_cell_site(&v, p0_edges[1], p0), VertexId(3));
let p1 = VoronoiCellId(VertexId(1));
let p1_edges: Vec<_> = v.cell_edges(p1).collect();
assert_eq!(p1_edges.len(), 3);
assert_eq!(other_cell_site(&v, p1_edges[0], p1), VertexId(4));
assert!(matches!(
v.edge_kind(p1_edges[0]),
VoronoiEdgeKind::Unbounded { .. }
));
assert_eq!(other_cell_site(&v, p1_edges[1], p1), VertexId(2));
assert!(matches!(
v.edge_kind(p1_edges[1]),
VoronoiEdgeKind::Bounded { .. }
));
assert_eq!(other_cell_site(&v, p1_edges[2], p1), VertexId(0));
assert!(matches!(
v.edge_kind(p1_edges[2]),
VoronoiEdgeKind::Unbounded { .. }
));
for cell in v.cells() {
for e in v.cell_edges(cell) {
assert!(v.edge_cells(e).contains(&cell));
}
}
assert!(v.validate_voronoi_topology().is_empty());
}
#[test]
fn cell_edges_near_cocircular_but_not_does_not_merge() {
let pts = vec![pt(0.0, 0.0), pt(2.0, 0.0), pt(2.0, 2.0), pt(0.0, 2.001)];
let faces = vec![
[VertexId(0), VertexId(1), VertexId(2)],
[VertexId(0), VertexId(2), VertexId(3)],
];
let v = voronoi2(assemble_triangulation(pts, faces));
assert_eq!(
v.group_faces.len(),
2,
"a near-miss cocircular quad must not merge into one Voronoi vertex"
);
let p0_edges: Vec<_> = v.cell_edges(VoronoiCellId(VertexId(0))).collect();
assert_eq!(
p0_edges.len(),
3,
"p0's diagonal to p2 is now a genuine Bounded edge, not excluded"
);
assert!(
p0_edges
.iter()
.any(|&e| matches!(v.edge_kind(e), VoronoiEdgeKind::Bounded { .. }))
);
assert!(v.validate_voronoi_topology().is_empty());
}
#[test]
fn cell_edges_interior_cell_is_cyclically_consistent_on_a_60_point_cloud() {
struct Xorshift64(u64);
impl Xorshift64 {
fn next_u64(&mut self) -> u64 {
let mut x = self.0;
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
self.0 = x;
x
}
fn next_f64_in(&mut self, scale: f64) -> f64 {
let bits = self.next_u64();
let unit = (bits >> 11) as f64 * (1.0 / (1u64 << 53) as f64);
(unit * 2.0 - 1.0) * scale
}
}
let mut rng = Xorshift64(0x00c0_ffee_1234_5678);
let pts: Vec<Point2> = (0..60)
.map(|_| pt(rng.next_f64_in(100.0), rng.next_f64_in(100.0)))
.collect();
let v = voronoi2(delaunay2(&pts));
assert!(v.validate_voronoi_topology().is_empty());
let hull_sites: std::collections::HashSet<VertexId> = v
.delaunay
.boundary_edges()
.flat_map(|e| {
let (a, b) = v.delaunay.edge_vertices(e);
[a, b]
})
.collect();
let mut checked_interior_cell = false;
for cell in v.cells() {
let edges: Vec<_> = v.cell_edges(cell).collect();
for &e in &edges {
assert!(v.edge_cells(e).contains(&cell));
}
if hull_sites.contains(&v.cell_site(cell)) {
assert!(edges.len() >= 2);
assert!(matches!(
v.edge_kind(edges[0]),
VoronoiEdgeKind::Unbounded { .. }
));
assert!(matches!(
v.edge_kind(*edges.last().unwrap()),
VoronoiEdgeKind::Unbounded { .. }
));
let endpoint_set = |e: VoronoiEdgeId| -> Vec<VoronoiVertexId> {
match v.edge_kind(e) {
VoronoiEdgeKind::Bounded { vertices } => vertices.to_vec(),
VoronoiEdgeKind::Unbounded { finite_vertex } => vec![*finite_vertex],
}
};
for w in 0..edges.len() - 1 {
let a = endpoint_set(edges[w]);
let b = endpoint_set(edges[w + 1]);
let shared = a.iter().filter(|x| b.contains(x)).count();
assert_eq!(
shared, 1,
"consecutive hull cell_edges must share exactly one Voronoi vertex, in order"
);
}
} else {
checked_interior_cell = true;
assert!(
edges.len() >= 3,
"an interior Voronoi cell needs at least 3 edges to close"
);
let endpoints = |e: VoronoiEdgeId| -> [VoronoiVertexId; 2] {
match v.edge_kind(e) {
VoronoiEdgeKind::Bounded { vertices } => *vertices,
VoronoiEdgeKind::Unbounded { .. } => {
panic!("an interior cell cannot have an Unbounded edge")
}
}
};
for w in 0..edges.len() {
let a = endpoints(edges[w]);
let b = endpoints(edges[(w + 1) % edges.len()]);
let shared = a.iter().filter(|x| b.contains(x)).count();
assert_eq!(
shared, 1,
"consecutive cell_edges must share exactly one Voronoi vertex, in order"
);
}
}
}
assert!(
checked_interior_cell,
"a 60-point generic-position cloud must have at least one interior site"
);
}
}