use std::collections::{HashSet, VecDeque};
use super::delaunay2::{TopologyError, assemble_triangulation};
use super::ids::{EdgeId, FaceId, VertexId};
use super::{Triangulation2, delaunay2};
use crate::hull::dedup_sorted;
use crate::intersections::{SegmentIntersectionKind, segment_intersection_kind};
use crate::predicates::{Orientation, Sign, incircle, orient2d};
use crate::primitives::{Point2, Segment2};
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[non_exhaustive]
pub enum CdtError {
InvalidVertexIndex,
DuplicateConstraint,
ZeroLengthConstraint,
ProperlyCrossingConstraints,
CollinearOverlappingConstraints,
DegeneratePointSet,
ConstraintInsertionFailed,
}
#[derive(Debug, Clone, PartialEq)]
pub struct ConstrainedTriangulation2 {
triangulation: Triangulation2,
constrained_edges: HashSet<EdgeId>,
}
impl ConstrainedTriangulation2 {
pub fn triangulation(&self) -> &Triangulation2 {
&self.triangulation
}
pub fn is_constrained(&self, edge: EdgeId) -> bool {
self.constrained_edges.contains(&edge)
}
}
fn validate_constraints(points: &[Point2], constraints: &[(usize, usize)]) -> Result<(), CdtError> {
for &(a, b) in constraints {
if a >= points.len() || b >= points.len() {
return Err(CdtError::InvalidVertexIndex);
}
if a == b {
return Err(CdtError::ZeroLengthConstraint);
}
}
if dedup_sorted(points).len() != points.len() {
return Err(CdtError::InvalidVertexIndex);
}
let mut seen_pairs: HashSet<(usize, usize)> = HashSet::new();
for &(a, b) in constraints {
let key = if a <= b { (a, b) } else { (b, a) };
if !seen_pairs.insert(key) {
return Err(CdtError::DuplicateConstraint);
}
}
for i in 0..constraints.len() {
for j in (i + 1)..constraints.len() {
let (a, b) = constraints[i];
let (c, d) = constraints[j];
let s1 = Segment2::new(points[a], points[b]);
let s2 = Segment2::new(points[c], points[d]);
match segment_intersection_kind(s1, s2) {
SegmentIntersectionKind::Proper => {
return Err(CdtError::ProperlyCrossingConstraints);
}
SegmentIntersectionKind::CollinearOverlap => {
return Err(CdtError::CollinearOverlappingConstraints);
}
_ => {}
}
}
}
Ok(())
}
pub fn constrained_delaunay2(
points: &[Point2],
constraints: &[(usize, usize)],
) -> Result<ConstrainedTriangulation2, CdtError> {
validate_constraints(points, constraints)?;
let triangulation = delaunay2(points);
if triangulation.is_empty() {
return if constraints.is_empty() {
Ok(ConstrainedTriangulation2 {
triangulation,
constrained_edges: HashSet::new(),
})
} else {
Err(CdtError::DegeneratePointSet)
};
}
let vertex_of_coord = |p: Point2| -> VertexId {
triangulation
.vertices()
.find(|&(_, q)| q == p)
.expect("every input point has a VertexId: duplicates were already rejected")
.0
};
let vertex_id: Vec<VertexId> = points.iter().map(|&p| vertex_of_coord(p)).collect();
let mut faces: Vec<[VertexId; 3]> = triangulation
.faces()
.map(|f| triangulation.face_vertices(f))
.collect();
let mut face_neighbors: Vec<[Option<FaceId>; 3]> = triangulation
.faces()
.map(|f| triangulation.neighboring_faces(f))
.collect();
let vertex_pos: Vec<Point2> = triangulation.vertices().map(|(_, p)| p).collect();
let mut constrained_pairs: HashSet<(VertexId, VertexId)> = HashSet::new();
for &(a, b) in constraints {
let (u, v) = (vertex_id[a], vertex_id[b]);
insert_constraint_edge(
&mut faces,
&mut face_neighbors,
&vertex_pos,
&constrained_pairs,
u,
v,
)?;
constrained_pairs.insert(canon(u, v));
}
restore_unconstrained_delaunay(
&mut faces,
&mut face_neighbors,
&vertex_pos,
&constrained_pairs,
)?;
let final_triangulation = assemble_triangulation(vertex_pos, faces);
let constrained_edges: HashSet<EdgeId> = final_triangulation
.edges()
.filter(|&e| {
let (u, v) = final_triangulation.edge_vertices(e);
constrained_pairs.contains(&canon(u, v))
})
.collect();
Ok(ConstrainedTriangulation2 {
triangulation: final_triangulation,
constrained_edges,
})
}
fn canon(u: VertexId, v: VertexId) -> (VertexId, VertexId) {
if u.raw() <= v.raw() { (u, v) } else { (v, u) }
}
fn edge_exists(faces: &[[VertexId; 3]], u: VertexId, v: VertexId) -> bool {
faces.iter().any(|f| f.contains(&u) && f.contains(&v))
}
fn unconstrained_interior_edges(
faces: &[[VertexId; 3]],
face_neighbors: &[[Option<FaceId>; 3]],
constrained_pairs: &HashSet<(VertexId, VertexId)>,
) -> Vec<(VertexId, VertexId, FaceId, FaceId)> {
let mut found = Vec::new();
let mut seen: HashSet<(VertexId, VertexId)> = HashSet::new();
for (i, face) in faces.iter().enumerate() {
let fa = FaceId::new(i as u32);
for k in 0..3 {
let Some(fb) = face_neighbors[i][k] else {
continue;
};
let (a, b) = (face[(k + 1) % 3], face[(k + 2) % 3]);
let key = canon(a, b);
if !seen.insert(key) {
continue;
}
if constrained_pairs.contains(&key) {
continue;
}
found.push((key.0, key.1, fa, fb));
}
}
found
}
fn crossing_edges(
faces: &[[VertexId; 3]],
face_neighbors: &[[Option<FaceId>; 3]],
vertex_pos: &[Point2],
constrained_pairs: &HashSet<(VertexId, VertexId)>,
u: VertexId,
v: VertexId,
) -> Vec<(VertexId, VertexId)> {
let seg_uv = Segment2::new(vertex_pos[u.raw() as usize], vertex_pos[v.raw() as usize]);
unconstrained_interior_edges(faces, face_neighbors, constrained_pairs)
.into_iter()
.filter_map(|(a, b, _fa, _fb)| {
let seg_ab = Segment2::new(vertex_pos[a.raw() as usize], vertex_pos[b.raw() as usize]);
(segment_intersection_kind(seg_uv, seg_ab) == SegmentIntersectionKind::Proper)
.then_some((a, b))
})
.collect()
}
fn adjacent_faces_of_edge(
faces: &[[VertexId; 3]],
face_neighbors: &[[Option<FaceId>; 3]],
a: VertexId,
b: VertexId,
) -> Option<(FaceId, FaceId)> {
for (i, face) in faces.iter().enumerate() {
for k in 0..3 {
let Some(fb) = face_neighbors[i][k] else {
continue;
};
let (x, y) = (face[(k + 1) % 3], face[(k + 2) % 3]);
if (x, y) == (a, b) || (x, y) == (b, a) {
return Some((FaceId::new(i as u32), fb));
}
}
}
None
}
fn shared_and_apex(
faces: &[[VertexId; 3]],
fa: FaceId,
fb: FaceId,
) -> (VertexId, VertexId, VertexId, VertexId) {
let tri_a = faces[fa.raw() as usize];
let tri_b = faces[fb.raw() as usize];
let p = *tri_a
.iter()
.find(|x| !tri_b.contains(x))
.expect("fa, fb must share exactly 2 vertices");
let q = *tri_b
.iter()
.find(|x| !tri_a.contains(x))
.expect("fa, fb must share exactly 2 vertices");
let shared: Vec<VertexId> = tri_a.into_iter().filter(|x| *x != p).collect();
(shared[0], shared[1], p, q)
}
fn can_flip(faces: &[[VertexId; 3]], vertex_pos: &[Point2], fa: FaceId, fb: FaceId) -> bool {
let (a, b, p, q) = shared_and_apex(faces, fa, fb);
let (pp, pq, pa, pb) = (
vertex_pos[p.raw() as usize],
vertex_pos[q.raw() as usize],
vertex_pos[a.raw() as usize],
vertex_pos[b.raw() as usize],
);
let oa = orient2d(pp, pq, pa);
let ob = orient2d(pp, pq, pb);
matches!(
(oa, ob),
(Orientation::Clockwise, Orientation::CounterClockwise)
| (Orientation::CounterClockwise, Orientation::Clockwise)
)
}
fn flip_edge(
faces: &mut [[VertexId; 3]],
face_neighbors: &mut [[Option<FaceId>; 3]],
fa: FaceId,
fb: FaceId,
) {
let ia = fa.raw() as usize;
let ib = fb.raw() as usize;
let old_fa = faces[ia];
let old_fb = faces[ib];
let old_na = face_neighbors[ia];
let old_nb = face_neighbors[ib];
let p = *old_fa
.iter()
.find(|x| !old_fb.contains(x))
.expect("fa, fb must share exactly 2 vertices");
let q = *old_fb
.iter()
.find(|x| !old_fa.contains(x))
.expect("fa, fb must share exactly 2 vertices");
let pa = old_fa.iter().position(|&x| x == p).unwrap();
let fa_rot = [old_fa[pa], old_fa[(pa + 1) % 3], old_fa[(pa + 2) % 3]];
let na_rot = [old_na[pa], old_na[(pa + 1) % 3], old_na[(pa + 2) % 3]];
let (u, v) = (fa_rot[1], fa_rot[2]);
let n_opp_u = na_rot[1]; let n_opp_v = na_rot[2];
let pb = old_fb.iter().position(|&x| x == q).unwrap();
let fb_rot = [old_fb[pb], old_fb[(pb + 1) % 3], old_fb[(pb + 2) % 3]];
let nb_rot = [old_nb[pb], old_nb[(pb + 1) % 3], old_nb[(pb + 2) % 3]];
debug_assert_eq!(fb_rot[1], v, "fb's CCW order must trace v then u");
debug_assert_eq!(fb_rot[2], u);
let n_opp_v_in_fb = nb_rot[1]; let n_opp_u_in_fb = nb_rot[2];
faces[ia] = [p, u, q];
faces[ib] = [p, q, v];
face_neighbors[ia] = [n_opp_v_in_fb, Some(fb), n_opp_v];
face_neighbors[ib] = [n_opp_u_in_fb, n_opp_u, Some(fa)];
if let Some(outer) = n_opp_v_in_fb {
let slot = face_neighbors[outer.raw() as usize]
.iter()
.position(|&n| n == Some(fb))
.expect("reciprocal neighbor must exist");
face_neighbors[outer.raw() as usize][slot] = Some(fa);
}
if let Some(outer) = n_opp_u {
let slot = face_neighbors[outer.raw() as usize]
.iter()
.position(|&n| n == Some(fa))
.expect("reciprocal neighbor must exist");
face_neighbors[outer.raw() as usize][slot] = Some(fb);
}
}
fn flip_bound(face_count: usize) -> usize {
4 * face_count + 16
}
fn insert_constraint_edge(
faces: &mut [[VertexId; 3]],
face_neighbors: &mut [[Option<FaceId>; 3]],
vertex_pos: &[Point2],
constrained_pairs: &HashSet<(VertexId, VertexId)>,
u: VertexId,
v: VertexId,
) -> Result<(), CdtError> {
if edge_exists(faces, u, v) {
return Ok(());
}
let mut queue: VecDeque<(VertexId, VertexId)> =
crossing_edges(faces, face_neighbors, vertex_pos, constrained_pairs, u, v)
.into_iter()
.collect();
let seg_uv = Segment2::new(vertex_pos[u.raw() as usize], vertex_pos[v.raw() as usize]);
let bound = flip_bound(faces.len());
let mut flips = 0u32;
for passes in 1..=bound as u32 {
let Some((a, b)) = queue.pop_front() else {
if !edge_exists(faces, u, v) {
return Err(CdtError::ConstraintInsertionFailed);
}
record_cdt_flips(flips);
record_cdt_passes(passes);
return Ok(());
};
let Some((fa, fb)) = adjacent_faces_of_edge(faces, face_neighbors, a, b) else {
continue;
};
if !can_flip(faces, vertex_pos, fa, fb) {
queue.push_back((a, b));
continue;
}
let (_, _, p, q) = shared_and_apex(faces, fa, fb);
flip_edge(faces, face_neighbors, fa, fb);
flips += 1;
if (p == u && q == v) || (p == v && q == u) {
record_cdt_flips(flips);
record_cdt_passes(passes);
return Ok(());
}
let seg_pq = Segment2::new(vertex_pos[p.raw() as usize], vertex_pos[q.raw() as usize]);
if segment_intersection_kind(seg_uv, seg_pq) == SegmentIntersectionKind::Proper {
queue.push_back(canon(p, q));
}
}
Err(CdtError::ConstraintInsertionFailed)
}
fn is_locally_delaunay(
faces: &[[VertexId; 3]],
vertex_pos: &[Point2],
fa: FaceId,
fb: FaceId,
) -> bool {
let (_, _, p, q) = shared_and_apex(faces, fa, fb);
let (pp, pq) = (vertex_pos[p.raw() as usize], vertex_pos[q.raw() as usize]);
let tri_a = faces[fa.raw() as usize];
let tri_b = faces[fb.raw() as usize];
let ccw_incircle = |tri: [VertexId; 3], vertex_pos: &[Point2], query: Point2| -> Sign {
let pts = [
vertex_pos[tri[0].raw() as usize],
vertex_pos[tri[1].raw() as usize],
vertex_pos[tri[2].raw() as usize],
];
incircle(pts[0], pts[1], pts[2], query)
};
ccw_incircle(tri_a, vertex_pos, pq) != Sign::Positive
&& ccw_incircle(tri_b, vertex_pos, pp) != Sign::Positive
}
fn restore_unconstrained_delaunay(
faces: &mut [[VertexId; 3]],
face_neighbors: &mut [[Option<FaceId>; 3]],
vertex_pos: &[Point2],
constrained_pairs: &HashSet<(VertexId, VertexId)>,
) -> Result<(), CdtError> {
let bound = flip_bound(faces.len());
for iter in 0..bound {
let bad =
find_first_bad_unconstrained_edge(faces, face_neighbors, vertex_pos, constrained_pairs);
match bad {
None => {
record_restore_flips(iter as u32);
return Ok(());
}
Some((fa, fb)) => {
if !can_flip(faces, vertex_pos, fa, fb) {
return Err(CdtError::ConstraintInsertionFailed);
}
flip_edge(faces, face_neighbors, fa, fb);
}
}
}
Err(CdtError::ConstraintInsertionFailed)
}
fn find_first_bad_unconstrained_edge(
faces: &[[VertexId; 3]],
face_neighbors: &[[Option<FaceId>; 3]],
vertex_pos: &[Point2],
constrained_pairs: &HashSet<(VertexId, VertexId)>,
) -> Option<(FaceId, FaceId)> {
unconstrained_interior_edges(faces, face_neighbors, constrained_pairs)
.into_iter()
.find_map(|(_a, _b, fa, fb)| {
(!is_locally_delaunay(faces, vertex_pos, fa, fb)).then_some((fa, fb))
})
}
#[doc(hidden)]
pub fn validate_cdt_topology(cdt: &ConstrainedTriangulation2) -> Vec<TopologyError> {
cdt.triangulation
.validate_topology_excluding(&|e| cdt.is_constrained(e))
}
#[cfg(test)]
use std::cell::Cell;
#[cfg(test)]
thread_local! {
static MAX_CDT_FLIPS: Cell<u32> = const { Cell::new(0) };
static MAX_CDT_PASSES: Cell<u32> = const { Cell::new(0) };
static MAX_RESTORE_FLIPS: Cell<u32> = const { Cell::new(0) };
}
#[cfg(test)]
fn record_cdt_flips(n: u32) {
MAX_CDT_FLIPS.with(|c| c.set(c.get().max(n)));
}
#[cfg(not(test))]
#[inline(always)]
fn record_cdt_flips(_n: u32) {}
#[cfg(test)]
fn record_cdt_passes(n: u32) {
MAX_CDT_PASSES.with(|c| c.set(c.get().max(n)));
}
#[cfg(not(test))]
#[inline(always)]
fn record_cdt_passes(_n: u32) {}
#[cfg(test)]
fn record_restore_flips(n: u32) {
MAX_RESTORE_FLIPS.with(|c| c.set(c.get().max(n)));
}
#[cfg(not(test))]
#[inline(always)]
fn record_restore_flips(_n: u32) {}
#[cfg(test)]
mod tests {
use super::*;
fn p(x: f64, y: f64) -> Point2 {
Point2::new(x, y).unwrap()
}
fn reset_flip_counters() {
MAX_CDT_FLIPS.with(|c| c.set(0));
MAX_CDT_PASSES.with(|c| c.set(0));
MAX_RESTORE_FLIPS.with(|c| c.set(0));
}
fn edge_coords(t: &Triangulation2, edge: EdgeId) -> ((f64, f64), (f64, f64)) {
let (u, v) = t.edge_vertices(edge);
let pu = t.vertices().find(|&(id, _)| id == u).unwrap().1;
let pv = t.vertices().find(|&(id, _)| id == v).unwrap().1;
let ku = (pu.x(), pu.y());
let kv = (pv.x(), pv.y());
if ku <= kv { (ku, kv) } else { (kv, ku) }
}
fn find_edge_by_coords(t: &Triangulation2, a: Point2, b: Point2) -> Option<EdgeId> {
let want = {
let ka = (a.x(), a.y());
let kb = (b.x(), b.y());
if ka <= kb { (ka, kb) } else { (kb, ka) }
};
t.edges().find(|&e| edge_coords(t, e) == want)
}
#[test]
fn empty_input_and_no_constraints() {
let cdt = constrained_delaunay2(&[], &[]).unwrap();
assert!(cdt.triangulation().is_empty());
assert!(validate_cdt_topology(&cdt).is_empty());
}
#[test]
fn no_constraints_matches_plain_delaunay() {
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 cdt = constrained_delaunay2(&pts, &[]).unwrap();
let plain = delaunay2(&pts);
assert_eq!(cdt.triangulation().len(), plain.len());
assert!(validate_cdt_topology(&cdt).is_empty());
assert!(cdt.triangulation().validate_topology().is_empty());
}
#[test]
fn invalid_vertex_index() {
let pts = [p(0.0, 0.0), p(1.0, 0.0)];
assert_eq!(
constrained_delaunay2(&pts, &[(0, 5)]),
Err(CdtError::InvalidVertexIndex)
);
}
#[test]
fn duplicate_point_is_invalid_vertex_index() {
let pts = [p(0.0, 0.0), p(1.0, 0.0), p(0.0, 0.0)];
assert_eq!(
constrained_delaunay2(&pts, &[]),
Err(CdtError::InvalidVertexIndex)
);
}
#[test]
fn zero_length_constraint() {
let pts = [p(0.0, 0.0), p(1.0, 0.0)];
assert_eq!(
constrained_delaunay2(&pts, &[(0, 0)]),
Err(CdtError::ZeroLengthConstraint)
);
}
#[test]
fn duplicate_constraint() {
let pts = [p(0.0, 0.0), p(1.0, 0.0), p(0.0, 1.0)];
assert_eq!(
constrained_delaunay2(&pts, &[(0, 1), (1, 0)]),
Err(CdtError::DuplicateConstraint)
);
}
#[test]
fn properly_crossing_constraints() {
let pts = [p(0.0, 0.0), p(4.0, 0.0), p(4.0, 4.0), p(0.0, 4.0)];
assert_eq!(
constrained_delaunay2(&pts, &[(0, 2), (1, 3)]),
Err(CdtError::ProperlyCrossingConstraints)
);
}
#[test]
fn collinear_overlapping_constraints() {
let pts = [p(0.0, 0.0), p(1.0, 0.0), p(2.0, 0.0), p(3.0, 0.0)];
assert_eq!(
constrained_delaunay2(&pts, &[(0, 2), (1, 3)]),
Err(CdtError::CollinearOverlappingConstraints)
);
}
#[test]
fn single_point_no_constraints_is_empty_ok() {
let pts = [p(0.0, 0.0)];
let cdt = constrained_delaunay2(&pts, &[]).unwrap();
assert!(cdt.triangulation().is_empty());
assert_eq!(cdt.triangulation().vertices().count(), 0);
assert!(validate_cdt_topology(&cdt).is_empty());
}
#[test]
fn two_collinear_points_no_constraints_is_empty_ok() {
let pts = [p(0.0, 0.0), p(1.0, 0.0)];
let cdt = constrained_delaunay2(&pts, &[]).unwrap();
assert!(cdt.triangulation().is_empty());
assert!(validate_cdt_topology(&cdt).is_empty());
}
#[test]
fn four_collinear_points_no_constraints_is_empty_ok() {
let pts = [p(0.0, 0.0), p(1.0, 0.0), p(2.0, 0.0), p(3.0, 0.0)];
let cdt = constrained_delaunay2(&pts, &[]).unwrap();
assert!(cdt.triangulation().is_empty());
assert!(validate_cdt_topology(&cdt).is_empty());
}
#[test]
fn two_collinear_points_with_constraint_is_degenerate_point_set() {
let pts = [p(0.0, 0.0), p(1.0, 0.0)];
assert_eq!(
constrained_delaunay2(&pts, &[(0, 1)]),
Err(CdtError::DegeneratePointSet)
);
}
#[test]
fn four_collinear_points_with_constraint_is_degenerate_point_set() {
let pts = [p(0.0, 0.0), p(1.0, 0.0), p(2.0, 0.0), p(3.0, 0.0)];
assert_eq!(
constrained_delaunay2(&pts, &[(0, 3)]),
Err(CdtError::DegeneratePointSet)
);
}
#[test]
fn shared_endpoint_constraints_are_allowed() {
let pts = [p(0.0, 0.0), p(4.0, 0.0), p(0.0, 4.0)];
let cdt = constrained_delaunay2(&pts, &[(0, 1), (1, 2), (2, 0)]).unwrap();
assert!(validate_cdt_topology(&cdt).is_empty());
}
#[test]
fn constrained_edge_survives_even_when_not_locally_delaunay() {
let a = p(0.0, 0.0);
let b = p(5.0, 1.0);
let c = p(4.0, 4.0);
let d = p(-1.0, 3.0);
let pts = [a, b, c, d];
let natural = delaunay2(&pts);
assert_eq!(natural.len(), 2, "expected a convex quad -> 2 triangles");
let ac_exists = find_edge_by_coords(&natural, a, c).is_some();
let (constrained_pair, constrained_a, constrained_b) = if ac_exists {
((1usize, 3usize), b, d)
} else {
((0usize, 2usize), a, c)
};
let cdt = constrained_delaunay2(&pts, &[constrained_pair]).unwrap();
let edge = find_edge_by_coords(cdt.triangulation(), constrained_a, constrained_b)
.expect("constrained diagonal must be present as an edge");
assert!(
cdt.is_constrained(edge),
"the inserted diagonal must be marked constrained"
);
assert!(
validate_cdt_topology(&cdt).is_empty(),
"constrained-aware validator must not flag the constrained edge"
);
let unconstrained_errors = cdt.triangulation().validate_topology();
assert!(
unconstrained_errors
.iter()
.any(|e| matches!(e, TopologyError::NotLocallyDelaunay { .. })),
"test setup didn't actually pick a non-Delaunay diagonal: {unconstrained_errors:?}"
);
}
#[test]
fn multiple_constraints_each_needing_a_flip_all_survive() {
let quad = |ox: f64, oy: f64| {
[
p(0.0 + ox, 0.0 + oy),
p(5.0 + ox, 1.0 + oy),
p(4.0 + ox, 4.0 + oy),
p(-1.0 + ox, 3.0 + oy),
]
};
let qa = quad(0.0, 0.0);
let qb = quad(100.0, 0.0);
let pts = [qa[0], qa[1], qa[2], qa[3], qb[0], qb[1], qb[2], qb[3]];
let natural = delaunay2(&pts);
let pick_diagonal = |q: [Point2; 4], idx: [usize; 4]| -> ((usize, usize), Point2, Point2) {
let ac_exists = find_edge_by_coords(&natural, q[0], q[2]).is_some();
if ac_exists {
((idx[1], idx[3]), q[1], q[3])
} else {
((idx[0], idx[2]), q[0], q[2])
}
};
let (constraint_a, ca0, ca1) = pick_diagonal(qa, [0, 1, 2, 3]);
let (constraint_b, cb0, cb1) = pick_diagonal(qb, [4, 5, 6, 7]);
let cdt = constrained_delaunay2(&pts, &[constraint_a, constraint_b]).unwrap();
let edge_a = find_edge_by_coords(cdt.triangulation(), ca0, ca1)
.expect("quad A's constrained diagonal must be present");
let edge_b = find_edge_by_coords(cdt.triangulation(), cb0, cb1)
.expect("quad B's constrained diagonal must be present");
assert!(cdt.is_constrained(edge_a), "quad A's diagonal must survive");
assert!(cdt.is_constrained(edge_b), "quad B's diagonal must survive");
assert!(
validate_cdt_topology(&cdt).is_empty(),
"constrained-aware validator must not flag either constrained edge"
);
let unconstrained_errors = cdt.triangulation().validate_topology();
let flags_edge = |x: Point2, y: Point2| {
let coord = |id: VertexId| {
cdt.triangulation()
.vertices()
.find(|&(vid, _)| vid == id)
.unwrap()
.1
};
unconstrained_errors.iter().any(|e| match e {
TopologyError::NotLocallyDelaunay { u, v } => {
let (pu, pv) = (coord(*u), coord(*v));
(pu == x && pv == y) || (pu == y && pv == x)
}
_ => false,
})
};
assert!(
flags_edge(ca0, ca1),
"test setup didn't pick a non-Delaunay diagonal for quad A: {unconstrained_errors:?}"
);
assert!(
flags_edge(cb0, cb1),
"test setup didn't pick a non-Delaunay diagonal for quad B: {unconstrained_errors:?}"
);
}
#[test]
fn constraint_through_a_collinear_third_vertex_is_rejected() {
let p0 = p(0.0, 0.0);
let p1 = p(2.0, 0.0);
let p2 = p(4.0, 0.0);
let p3 = p(2.0, 2.0);
let p4 = p(2.0, -2.0);
let pts = [p0, p1, p2, p3, p4];
assert_eq!(
constrained_delaunay2(&pts, &[(0, 2)]),
Err(CdtError::ConstraintInsertionFailed)
);
}
#[test]
fn constraint_already_a_delaunay_edge_is_a_noop_flip() {
let pts = [p(0.0, 0.0), p(4.0, 0.0), p(0.0, 4.0)];
let cdt = constrained_delaunay2(&pts, &[(0, 1)]).unwrap();
let edge = find_edge_by_coords(cdt.triangulation(), pts[0], pts[1]).unwrap();
assert!(cdt.is_constrained(edge));
}
#[test]
fn deterministic_regardless_of_constraint_order() {
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 a = constrained_delaunay2(&pts, &[(0, 1), (2, 3)]).unwrap();
let b = constrained_delaunay2(&pts, &[(2, 3), (0, 1)]).unwrap();
assert_eq!(a.triangulation().triangles(), b.triangulation().triangles());
}
#[test]
fn flip_count_stays_well_below_the_bound() {
reset_flip_counters();
let mut rng = 0x9E37_79B9_7F4A_7C15_u64;
let mut next = || {
rng ^= rng << 13;
rng ^= rng >> 7;
rng ^= rng << 17;
(rng % 13) as f64
};
for _ in 0..40 {
let mut pts = Vec::new();
for _ in 0..8 {
pts.push(p(next(), next()));
}
pts.dedup_by(|a, b| a == b);
if pts.len() < 3 {
continue;
}
for i in 0..pts.len() {
for j in (i + 1)..pts.len() {
if pts[i] == pts[j] {
continue;
}
let _ = constrained_delaunay2(&pts, &[(i, j)]);
}
}
}
let max_cdt = MAX_CDT_FLIPS.with(|c| c.get());
let max_cdt_passes = MAX_CDT_PASSES.with(|c| c.get());
let max_restore = MAX_RESTORE_FLIPS.with(|c| c.get());
eprintln!(
"cdt: measured max insertion flips = {max_cdt} (passes = {max_cdt_passes}), max restore flips = {max_restore}"
);
assert!(
max_cdt < 20,
"insertion flip count {max_cdt} closer to the bound than expected"
);
assert!(
max_cdt_passes < 20,
"insertion pass count {max_cdt_passes} closer to the bound than expected"
);
assert!(
max_restore < 20,
"restore flip count {max_restore} closer to the bound than expected"
);
}
#[test]
fn flip_count_stays_well_below_the_bound_many_constraints() {
reset_flip_counters();
let mut rng = 0x1BD1_1BDA_A9FC_1A22_u64;
let mut next = || {
rng ^= rng << 13;
rng ^= rng >> 7;
rng ^= rng << 17;
(rng % 13) as f64
};
let mut trials_run = 0u32;
for n in [6usize, 8, 10, 12, 14] {
for _ in 0..20 {
let mut pts: Vec<Point2> = (0..n).map(|_| p(next(), next())).collect();
pts.dedup_by(|a, b| a == b);
if pts.len() < 3 {
continue;
}
let cx = pts.iter().map(Point2::x).sum::<f64>() / pts.len() as f64;
let cy = pts.iter().map(Point2::y).sum::<f64>() / pts.len() as f64;
pts.sort_by(|a, b| {
let angle = |p: &Point2| (p.y() - cy).atan2(p.x() - cx);
angle(a).total_cmp(&angle(b))
});
let m = pts.len();
let constraints: Vec<(usize, usize)> = (0..m).map(|i| (i, (i + 1) % m)).collect();
if constrained_delaunay2(&pts, &constraints).is_ok() {
trials_run += 1;
}
}
}
let max_cdt = MAX_CDT_FLIPS.with(|c| c.get());
let max_cdt_passes = MAX_CDT_PASSES.with(|c| c.get());
let max_restore = MAX_RESTORE_FLIPS.with(|c| c.get());
eprintln!(
"cdt (many constraints): {trials_run} trials succeeded, measured max insertion \
flips = {max_cdt} (passes = {max_cdt_passes}), max restore flips = {max_restore}"
);
assert!(
trials_run > 0,
"every trial failed validation -- measurement below is vacuous"
);
assert!(
max_restore > 0,
"restore flip count was never above zero -- this mode never exercised a real flip"
);
assert!(
max_cdt < 40,
"insertion flip count {max_cdt} closer to the bound than expected"
);
assert!(
max_cdt_passes < 40,
"insertion pass count {max_cdt_passes} closer to the bound than expected"
);
assert!(
max_restore < 40,
"restore flip count {max_restore} closer to the bound than expected"
);
}
}