use std::collections::{HashMap, HashSet};
use super::ids::{EdgeId, FaceId, VertexId};
use crate::hull::{HullBoundaryPoints, convex_hull2, dedup_sorted};
use crate::predicates::{Orientation, Sign, incircle, orient2d};
use crate::primitives::{Point2, Triangle2};
#[derive(Debug, Clone, PartialEq)]
pub struct Triangulation2 {
triangles: Vec<Triangle2>,
vertices: Vec<Point2>,
faces: Vec<[VertexId; 3]>,
face_neighbors: Vec<[Option<FaceId>; 3]>,
edges: Vec<(VertexId, VertexId)>,
edge_faces: Vec<[Option<FaceId>; 2]>,
}
impl Triangulation2 {
fn empty() -> Self {
Triangulation2 {
triangles: Vec::new(),
vertices: Vec::new(),
faces: Vec::new(),
face_neighbors: Vec::new(),
edges: Vec::new(),
edge_faces: Vec::new(),
}
}
pub fn triangles(&self) -> &[Triangle2] {
&self.triangles
}
pub fn len(&self) -> usize {
self.triangles.len()
}
pub fn is_empty(&self) -> bool {
self.triangles.is_empty()
}
pub fn vertices(&self) -> impl Iterator<Item = (VertexId, Point2)> + '_ {
self.vertices
.iter()
.enumerate()
.map(|(i, &p)| (VertexId(i as u32), p))
}
pub(super) fn vertex_point(&self, v: VertexId) -> Point2 {
self.vertices[v.raw() as usize]
}
pub fn edges(&self) -> impl Iterator<Item = EdgeId> + '_ {
(0..self.edges.len()).map(|i| EdgeId(i as u32))
}
pub fn faces(&self) -> impl Iterator<Item = FaceId> + '_ {
(0..self.faces.len()).map(|i| FaceId(i as u32))
}
pub fn edge_vertices(&self, edge: EdgeId) -> (VertexId, VertexId) {
self.edges[edge.0 as usize]
}
pub fn adjacent_faces(&self, edge: EdgeId) -> [Option<FaceId>; 2] {
self.edge_faces[edge.0 as usize]
}
#[cfg(test)]
pub(super) fn clear_adjacent_faces_for_test(&mut self, edge: EdgeId) {
self.edge_faces[edge.0 as usize] = [None, None];
}
pub fn face_vertices(&self, face: FaceId) -> [VertexId; 3] {
self.faces[face.0 as usize]
}
pub fn neighboring_faces(&self, face: FaceId) -> [Option<FaceId>; 3] {
self.face_neighbors[face.0 as usize]
}
pub fn boundary_edges(&self) -> impl Iterator<Item = EdgeId> + '_ {
self.edges()
.filter(move |&e| self.adjacent_faces(e)[1].is_none())
}
}
const GHOST: usize = usize::MAX;
fn is_ghost(idx: usize) -> bool {
idx == GHOST
}
pub fn delaunay2(points: &[Point2]) -> Triangulation2 {
let pts = dedup_sorted(points);
let hull = convex_hull2(&pts, HullBoundaryPoints::ExtremesOnly);
if hull.len() < 3 {
return Triangulation2::empty();
}
let mut ic = 2;
while orient2d(pts[0], pts[1], pts[ic]) == Orientation::Collinear {
ic += 1;
}
let (mut ia, mut ib) = (0, 1);
if orient2d(pts[ia], pts[ib], pts[ic]) == Orientation::Clockwise {
std::mem::swap(&mut ia, &mut ib);
}
let mut tris: Vec<[usize; 3]> = vec![
[ia, ib, ic],
[ib, ia, GHOST],
[ic, ib, GHOST],
[ia, ic, GHOST],
];
for i in 0..pts.len() {
if i == ia || i == ib || i == ic {
continue;
}
insert_point(&mut tris, &pts, i);
}
build_topology(pts, tris)
}
fn build_topology(pts: Vec<Point2>, tris: Vec<[usize; 3]>) -> Triangulation2 {
let real: Vec<[usize; 3]> = tris
.into_iter()
.filter(|t| t.iter().all(|&idx| !is_ghost(idx)))
.collect();
let faces: Vec<[VertexId; 3]> = real
.iter()
.map(|&[a, b, c]| [VertexId(a as u32), VertexId(b as u32), VertexId(c as u32)])
.collect();
assemble_triangulation(pts, faces)
}
pub(super) fn assemble_triangulation(
pts: Vec<Point2>,
faces: Vec<[VertexId; 3]>,
) -> Triangulation2 {
let triangles: Vec<Triangle2> = faces
.iter()
.map(|&[a, b, c]| Triangle2::new(pts[a.0 as usize], pts[b.0 as usize], pts[c.0 as usize]))
.collect();
let edge_key = |u: VertexId, v: VertexId| -> (u32, u32) {
if u.0 <= v.0 { (u.0, v.0) } else { (v.0, u.0) }
};
let mut edge_index: HashMap<(u32, u32), usize> = HashMap::new();
let mut edges: Vec<(VertexId, VertexId)> = Vec::new();
let mut edge_incidences: Vec<Vec<(FaceId, usize)>> = Vec::new();
for (i, face) in faces.iter().enumerate() {
let face_id = FaceId(i as u32);
let local_edges = [(face[1], face[2]), (face[2], face[0]), (face[0], face[1])];
for (k, &(u, v)) in local_edges.iter().enumerate() {
let key = edge_key(u, v);
let idx = *edge_index.entry(key).or_insert_with(|| {
edges.push((u, v));
edge_incidences.push(Vec::new());
edges.len() - 1
});
edge_incidences[idx].push((face_id, k));
}
}
let mut edge_faces: Vec<[Option<FaceId>; 2]> = vec![[None, None]; edges.len()];
let mut face_neighbors: Vec<[Option<FaceId>; 3]> = vec![[None, None, None]; faces.len()];
for (idx, incidences) in edge_incidences.iter().enumerate() {
for (slot, &(face_id, _)) in incidences.iter().take(2).enumerate() {
edge_faces[idx][slot] = Some(face_id);
}
if incidences.len() == 2 {
let (fa, ka) = incidences[0];
let (fb, kb) = incidences[1];
face_neighbors[fa.0 as usize][ka] = Some(fb);
face_neighbors[fb.0 as usize][kb] = Some(fa);
}
}
Triangulation2 {
triangles,
vertices: pts,
faces,
face_neighbors,
edges,
edge_faces,
}
}
#[doc(hidden)]
#[derive(Debug, Clone, PartialEq)]
#[non_exhaustive]
pub enum TopologyError {
FaceNotCcw(FaceId),
NonManifoldEdge {
u: VertexId,
v: VertexId,
incident_faces: usize,
},
AdjacencyMismatch { face: FaceId, local_edge: usize },
EulerFormulaViolated { triangles: usize, expected: isize },
NotLocallyDelaunay { u: VertexId, v: VertexId },
}
impl Triangulation2 {
#[doc(hidden)]
pub fn validate_topology(&self) -> Vec<TopologyError> {
self.validate_topology_excluding(&|_| false)
}
pub(crate) fn validate_topology_excluding(
&self,
excluded: &dyn Fn(EdgeId) -> bool,
) -> Vec<TopologyError> {
let mut errors = Vec::new();
for (i, tri) in self.triangles.iter().enumerate() {
if tri.orientation() != Orientation::CounterClockwise {
errors.push(TopologyError::FaceNotCcw(FaceId(i as u32)));
}
}
let mut incidence: HashMap<(u32, u32), Vec<(FaceId, usize)>> = HashMap::new();
for (i, face) in self.faces.iter().enumerate() {
let face_id = FaceId(i as u32);
let local_edges = [(face[1], face[2]), (face[2], face[0]), (face[0], face[1])];
for (k, &(u, v)) in local_edges.iter().enumerate() {
let key = if u.0 <= v.0 { (u.0, v.0) } else { (v.0, u.0) };
incidence.entry(key).or_default().push((face_id, k));
}
}
let edge_id_of: HashMap<(u32, u32), EdgeId> = self
.edges
.iter()
.enumerate()
.map(|(i, &(u, v))| {
let key = if u.0 <= v.0 { (u.0, v.0) } else { (v.0, u.0) };
(key, EdgeId(i as u32))
})
.collect();
for (&(u, v), incident) in &incidence {
if incident.len() != 1 && incident.len() != 2 {
errors.push(TopologyError::NonManifoldEdge {
u: VertexId(u),
v: VertexId(v),
incident_faces: incident.len(),
});
continue;
}
if incident.len() == 2 {
let (fa, ka) = incident[0];
let (fb, kb) = incident[1];
let claims_a = self.face_neighbors[fa.0 as usize][ka] == Some(fb);
let claims_b = self.face_neighbors[fb.0 as usize][kb] == Some(fa);
if !claims_a || !claims_b {
errors.push(TopologyError::AdjacencyMismatch {
face: fa,
local_edge: ka,
});
}
let is_excluded = edge_id_of.get(&(u, v)).is_some_and(|&id| excluded(id));
if !is_excluded {
let opposite_b = self.vertices[self.faces[fb.0 as usize][kb].0 as usize];
let opposite_a = self.vertices[self.faces[fa.0 as usize][ka].0 as usize];
let tri_a = self.triangles[fa.0 as usize];
let tri_b = self.triangles[fb.0 as usize];
let a_contains_b = incircle(tri_a.a(), tri_a.b(), tri_a.c(), opposite_b);
let b_contains_a = incircle(tri_b.a(), tri_b.b(), tri_b.c(), opposite_a);
if a_contains_b == Sign::Positive || b_contains_a == Sign::Positive {
errors.push(TopologyError::NotLocallyDelaunay {
u: VertexId(u),
v: VertexId(v),
});
}
}
}
}
if !self.vertices.is_empty() {
let hull = convex_hull2(&self.vertices, HullBoundaryPoints::KeepAllOnBoundary);
if hull.orientation() != Orientation::Collinear {
let n = self.vertices.len() as isize;
let h = hull.len() as isize;
let expected = 2 * n - 2 - h;
if self.triangles.len() as isize != expected {
errors.push(TopologyError::EulerFormulaViolated {
triangles: self.triangles.len(),
expected,
});
}
}
}
errors
}
}
fn is_bad(pts: &[Point2], tri: [usize; 3], p: Point2) -> bool {
let [a, b, c] = tri;
match (is_ghost(a), is_ghost(b), is_ghost(c)) {
(false, false, false) => incircle(pts[a], pts[b], pts[c], p) == Sign::Positive,
(true, false, false) => orient2d(pts[b], pts[c], p) == Orientation::CounterClockwise,
(false, true, false) => orient2d(pts[c], pts[a], p) == Orientation::CounterClockwise,
(false, false, true) => orient2d(pts[a], pts[b], p) == Orientation::CounterClockwise,
_ => unreachable!("a triangle can never carry more than one ghost vertex"),
}
}
fn insert_point(tris: &mut Vec<[usize; 3]>, pts: &[Point2], p_idx: usize) {
let p = pts[p_idx];
let bad: Vec<usize> = tris
.iter()
.enumerate()
.filter(|&(_, &tri)| is_bad(pts, tri, p))
.map(|(i, _)| i)
.collect();
let mut edges: Vec<(usize, usize)> = Vec::with_capacity(bad.len() * 3);
for &ti in &bad {
let [a, b, c] = tris[ti];
edges.push((a, b));
edges.push((b, c));
edges.push((c, a));
}
let edge_set: HashSet<(usize, usize)> = edges.iter().copied().collect();
let boundary: Vec<(usize, usize)> = edges
.into_iter()
.filter(|&(u, v)| !edge_set.contains(&(v, u)))
.collect();
for &ti in bad.iter().rev() {
tris.swap_remove(ti);
}
for (u, v) in boundary {
tris.push([u, v, p_idx]);
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::predicates::Orientation;
use crate::primitives::PointTriangleRelation;
fn p(x: f64, y: f64) -> Point2 {
Point2::new(x, y).unwrap()
}
fn all_ccw(t: &Triangulation2) {
for tri in t.triangles() {
assert_eq!(tri.orientation(), Orientation::CounterClockwise);
}
}
#[test]
fn is_bad_single_ghost_arms_agree_under_rotation() {
let mut rng = 0x1234_5678_9abc_def0_u64;
let mut next = || {
rng ^= rng << 13;
rng ^= rng >> 7;
rng ^= rng << 17;
(rng >> 11) as f64 * (1.0 / (1u64 << 53) as f64) * 2.0 - 1.0
};
for _ in 0..200 {
let pts = vec![p(next(), next()), p(next(), next())];
let query = p(next(), next());
let (a, b) = (0usize, 1usize);
let by_c = is_bad(&pts, [a, b, GHOST], query);
let by_a = is_bad(&pts, [GHOST, a, b], query);
let by_b = is_bad(&pts, [b, GHOST, a], query);
assert_eq!(by_c, by_a, "ghost-at-c vs ghost-at-a disagree");
assert_eq!(by_c, by_b, "ghost-at-c vs ghost-at-b disagree");
}
}
fn empty_circumcircle_property(points: &[Point2], t: &Triangulation2) {
for tri in t.triangles() {
for &q in points {
let sign = incircle(tri.a(), tri.b(), tri.c(), q);
assert_ne!(
sign,
Sign::Positive,
"point {q:?} strictly inside circumcircle of {tri:?}"
);
}
}
}
fn every_vertex_is_an_input_point(points: &[Point2], t: &Triangulation2) {
for tri in t.triangles() {
for v in [tri.a(), tri.b(), tri.c()] {
assert!(points.contains(&v), "triangle vertex {v:?} not in input");
}
}
}
#[test]
fn empty_input() {
let t = delaunay2(&[]);
assert!(t.is_empty());
}
#[test]
fn one_and_two_points() {
assert!(delaunay2(&[p(0.0, 0.0)]).is_empty());
assert!(delaunay2(&[p(0.0, 0.0), p(1.0, 1.0)]).is_empty());
}
#[test]
fn fully_collinear_input() {
let pts = [p(0.0, 0.0), p(1.0, 0.0), p(2.0, 0.0), p(3.0, 0.0)];
assert!(delaunay2(&pts).is_empty());
}
#[test]
fn single_triangle() {
let pts = [p(0.0, 0.0), p(4.0, 0.0), p(0.0, 4.0)];
let t = delaunay2(&pts);
assert_eq!(t.len(), 1);
all_ccw(&t);
every_vertex_is_an_input_point(&pts, &t);
empty_circumcircle_property(&pts, &t);
}
#[test]
fn square_gives_two_triangles() {
let pts = [p(0.0, 0.0), p(4.0, 0.0), p(4.0, 4.0), p(0.0, 4.0)];
let t = delaunay2(&pts);
assert_eq!(t.len(), 2);
all_ccw(&t);
every_vertex_is_an_input_point(&pts, &t);
empty_circumcircle_property(&pts, &t);
}
#[test]
fn square_with_center_point_gives_four_triangles() {
let pts = [
p(0.0, 0.0),
p(4.0, 0.0),
p(4.0, 4.0),
p(0.0, 4.0),
p(2.0, 2.0),
];
let t = delaunay2(&pts);
assert_eq!(t.len(), 4);
all_ccw(&t);
every_vertex_is_an_input_point(&pts, &t);
empty_circumcircle_property(&pts, &t);
}
#[test]
fn point_on_interior_edge_splits_both_adjacent_triangles() {
let pts = [
p(0.0, 0.0),
p(4.0, 0.0),
p(4.0, 4.0),
p(0.0, 4.0),
p(2.0, 2.0), ];
let t = delaunay2(&pts);
assert_eq!(t.len(), 4);
all_ccw(&t);
empty_circumcircle_property(&pts, &t);
}
#[test]
fn point_on_hull_boundary_edge_splits_one_triangle() {
let pts = [
p(0.0, 0.0),
p(4.0, 0.0),
p(0.0, 4.0),
p(2.0, 0.0), ];
let t = delaunay2(&pts);
assert_eq!(t.len(), 2);
all_ccw(&t);
empty_circumcircle_property(&pts, &t);
}
#[test]
fn cocircular_square_plus_center_is_stable_across_permutations() {
let pts = [
p(0.0, 0.0),
p(4.0, 0.0),
p(4.0, 4.0),
p(0.0, 4.0),
p(1.0, 1.0),
];
let base = delaunay2(&pts);
empty_circumcircle_property(&pts, &base);
all_ccw(&base);
let mut shuffled = pts;
shuffled.reverse();
let other = delaunay2(&shuffled);
assert_eq!(base.triangles(), other.triangles());
}
#[test]
fn triangulation_covers_the_convex_hull() {
let pts = [
p(0.0, 0.0),
p(4.0, 0.0),
p(4.0, 4.0),
p(0.0, 4.0),
p(1.0, 1.0),
p(3.0, 1.0),
p(2.0, 3.0),
];
let t = delaunay2(&pts);
for &q in &pts {
let covered = t
.triangles()
.iter()
.any(|tri| tri.relation_to(q) != PointTriangleRelation::Outside);
assert!(covered, "point {q:?} not covered by any triangle");
}
}
#[test]
fn ghost_vertex_never_leaks_into_output() {
let pts = [
p(0.0, 0.0),
p(4.0, 0.0),
p(4.0, 4.0),
p(0.0, 4.0),
p(1.0, 1.0),
];
let t = delaunay2(&pts);
every_vertex_is_an_input_point(&pts, &t);
}
#[test]
fn topology_empty_and_single_triangle_do_not_panic() {
let empty = delaunay2(&[]);
assert_eq!(empty.vertices().count(), 0);
assert_eq!(empty.edges().count(), 0);
assert_eq!(empty.faces().count(), 0);
assert_eq!(empty.boundary_edges().count(), 0);
assert!(empty.validate_topology().is_empty());
let pts = [p(0.0, 0.0), p(4.0, 0.0), p(0.0, 4.0)];
let t = delaunay2(&pts);
assert_eq!(t.vertices().count(), 3);
assert_eq!(t.faces().count(), 1);
assert_eq!(t.edges().count(), 3);
assert_eq!(t.boundary_edges().count(), 3);
let face = t.faces().next().unwrap();
assert_eq!(t.neighboring_faces(face), [None, None, None]);
assert!(t.validate_topology().is_empty());
}
#[test]
fn topology_square_with_center_has_one_shared_edge_per_interior_pair() {
let pts = [
p(0.0, 0.0),
p(4.0, 0.0),
p(4.0, 4.0),
p(0.0, 4.0),
p(2.0, 2.0),
];
let t = delaunay2(&pts);
assert_eq!(t.faces().count(), 4);
assert_eq!(t.edges().count(), 8);
assert_eq!(t.boundary_edges().count(), 4);
for edge in t.edges() {
let adj = t.adjacent_faces(edge);
if let [Some(fa), Some(fb)] = adj {
let neighbors_a = t.neighboring_faces(fa);
let neighbors_b = t.neighboring_faces(fb);
assert!(neighbors_a.contains(&Some(fb)));
assert!(neighbors_b.contains(&Some(fa)));
}
}
assert!(t.validate_topology().is_empty());
}
#[test]
fn face_vertices_matches_triangles_coordinates() {
let pts = [
p(0.0, 0.0),
p(4.0, 0.0),
p(4.0, 4.0),
p(0.0, 4.0),
p(2.0, 2.0),
];
let t = delaunay2(&pts);
let vertex_coords: std::collections::HashMap<VertexId, Point2> = t.vertices().collect();
for (face, tri) in t.faces().zip(t.triangles()) {
let [v0, v1, v2] = t.face_vertices(face);
assert_eq!(vertex_coords[&v0], tri.a());
assert_eq!(vertex_coords[&v1], tri.b());
assert_eq!(vertex_coords[&v2], tri.c());
}
}
#[test]
fn validate_topology_catches_broken_adjacency_reciprocity() {
let pts = [
p(0.0, 0.0),
p(4.0, 0.0),
p(4.0, 4.0),
p(0.0, 4.0),
p(2.0, 2.0),
];
let mut t = delaunay2(&pts);
assert!(t.validate_topology().is_empty());
let broken = t.face_neighbors[0]
.iter()
.position(|n| n.is_some())
.expect("triangle 0 has at least one interior neighbor");
t.face_neighbors[0][broken] = None;
let errors = t.validate_topology();
assert!(
errors
.iter()
.any(|e| matches!(e, TopologyError::AdjacencyMismatch { .. })),
"expected an AdjacencyMismatch, got {errors:?}"
);
}
}