pub type Tri = [usize; 3];
const MAX_CDT_POINTS: usize = 20_000;
fn orient(a: [f64; 2], b: [f64; 2], c: [f64; 2]) -> f64 {
super::predicates::orient2d(a, b, c)
}
fn seg_cross(p0: [f64; 2], p1: [f64; 2], q0: [f64; 2], q1: [f64; 2]) -> bool {
let d1 = orient(p0, p1, q0);
let d2 = orient(p0, p1, q1);
let d3 = orient(q0, q1, p0);
let d4 = orient(q0, q1, p1);
(d1 * d2 < 0.0) && (d3 * d4 < 0.0)
}
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]);
let a2 = ax * ax + ay * ay;
let b2 = bx * bx + by * by;
let c2 = cx * cx + cy * cy;
ax * (by * c2 - b2 * cy) - ay * (bx * c2 - b2 * cx) + a2 * (bx * cy - by * cx)
}
fn in_circle_errbound(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]);
let a2 = ax * ax + ay * ay;
let b2 = bx * bx + by * by;
let c2 = cx * cx + cy * cy;
let perm = ax.abs() * ((by * c2).abs() + (b2 * cy).abs())
+ ay.abs() * ((bx * c2).abs() + (b2 * cx).abs())
+ a2.abs() * ((bx * cy).abs() + (by * cx).abs());
ICC_REL * perm
}
const ICC_REL: f64 = 1.0e-12;
pub fn triangulate_constrained(pts: &[[f64; 2]], constraints: &[[usize; 2]]) -> Option<Vec<Tri>> {
if pts.len() < 3 {
return None;
}
if pts.len() > MAX_CDT_POINTS {
return None;
}
let mut tris: Vec<Tri> = vec![if orient(pts[0], pts[1], pts[2]) >= 0.0 {
[0, 1, 2]
} else {
[0, 2, 1]
}];
for i in 3..pts.len() {
insert_point(&mut tris, pts, i)?;
}
for &[u, v] in constraints {
recover_edge(&mut tris, pts, u, v)?;
}
let mut cons: std::collections::HashSet<(usize, usize)> = std::collections::HashSet::new();
for &[u, v] in constraints {
cons.insert((u.min(v), u.max(v)));
}
delaunay_flip(&mut tris, pts, &cons);
Some(tris)
}
fn delaunay_flip(
tris: &mut [Tri],
pts: &[[f64; 2]],
cons: &std::collections::HashSet<(usize, usize)>,
) {
let mut adj: EdgeMap = std::collections::HashMap::with_capacity(tris.len() * 3);
for (k, t) in tris.iter().enumerate() {
attach_tri(&mut adj, *t, k);
}
let mut work: Vec<Edge> = adj.keys().copied().collect();
work.sort_unstable();
work.reverse();
let mut queued: std::collections::HashSet<Edge> = work.iter().copied().collect();
let cap = 64 * tris.len() + 4096;
let mut guard = 0usize;
while let Some(e) = work.pop() {
queued.remove(&e);
guard += 1;
if guard > cap {
return;
}
let (a, b) = e;
if cons.contains(&e) {
continue;
}
let Some(&(k1, k2, count)) = adj.get(&e) else {
continue;
};
if count != 2 {
continue; }
let (Some(c), Some(d)) = (apex(tris[k1], a, b), apex(tris[k2], a, b)) else {
continue;
};
let convex = orient(pts[a], pts[b], pts[c]) * orient(pts[a], pts[b], pts[d]) < 0.0
&& orient(pts[c], pts[d], pts[a]) * orient(pts[c], pts[d], pts[b]) < 0.0;
if !convex {
continue;
}
let ccw_tri = ccw([a, b, c], pts);
let (p0, p1, p2, pd) = (pts[ccw_tri[0]], pts[ccw_tri[1]], pts[ccw_tri[2]], pts[d]);
if in_circle(p0, p1, p2, pd) <= in_circle_errbound(p0, p1, p2, pd).max(1e-9) {
continue;
}
let (old1, old2) = (tris[k1], tris[k2]);
detach_tri(&mut adj, old1, k1);
detach_tri(&mut adj, old2, k2);
let (new1, new2) = (ccw([c, d, a], pts), ccw([d, c, b], pts));
tris[k1] = new1;
tris[k2] = new2;
attach_tri(&mut adj, new1, k1);
attach_tri(&mut adj, new2, k2);
for (x, y) in [(a, c), (c, b), (b, d), (d, a)] {
let key = edge_key(x, y);
if !cons.contains(&key) && queued.insert(key) {
work.push(key);
}
}
}
}
type Edge = (usize, usize);
type EdgeMap = std::collections::HashMap<Edge, (usize, usize, u32)>;
const NO_TRI: usize = usize::MAX;
fn edge_key(a: usize, b: usize) -> Edge {
(a.min(b), a.max(b))
}
fn attach_tri(adj: &mut EdgeMap, t: Tri, k: usize) {
for e in 0..3 {
let slot = adj
.entry(edge_key(t[e], t[(e + 1) % 3]))
.or_insert((NO_TRI, NO_TRI, 0));
if slot.0 == NO_TRI {
slot.0 = k;
} else if slot.1 == NO_TRI {
slot.1 = k;
}
slot.2 += 1;
}
}
fn detach_tri(adj: &mut EdgeMap, t: Tri, k: usize) {
for e in 0..3 {
let key = edge_key(t[e], t[(e + 1) % 3]);
let Some(slot) = adj.get_mut(&key) else {
continue;
};
if slot.0 == k {
slot.0 = slot.1;
slot.1 = NO_TRI;
} else if slot.1 == k {
slot.1 = NO_TRI;
}
slot.2 = slot.2.saturating_sub(1);
if slot.2 == 0 {
adj.remove(&key);
}
}
}
fn insert_point(tris: &mut Vec<Tri>, pts: &[[f64; 2]], i: usize) -> Option<()> {
let p = pts[i];
const EPS: f64 = 1e-9;
let mut host = None;
for (k, t) in tris.iter().enumerate() {
let (a, b, c) = (pts[t[0]], pts[t[1]], pts[t[2]]);
let (oa, ob, oc) = (orient(a, b, p), orient(b, c, p), orient(c, a, p));
if oa >= -EPS && ob >= -EPS && oc >= -EPS {
host = Some((k, oa < EPS, ob < EPS, oc < EPS));
break;
}
}
let (k, on_ab, on_bc, on_ca) = host?;
let t = tris[k];
let edge = if on_ab {
Some((t[0], t[1]))
} else if on_bc {
Some((t[1], t[2]))
} else if on_ca {
Some((t[2], t[0]))
} else {
None
};
if let Some((a, b)) = edge {
let affected: Vec<usize> = tris
.iter()
.enumerate()
.filter(|(_, tr)| has_edge(**tr, a, b))
.map(|(idx, _)| idx)
.collect();
let mut new_tris = Vec::new();
for &idx in &affected {
let tr = tris[idx];
let apex = tr.iter().copied().find(|&x| x != a && x != b)?;
let (x, y) = ordered_edge(tr, a, b);
new_tris.push([x, i, apex]);
new_tris.push([i, y, apex]);
}
let mut aff = affected;
aff.sort_unstable_by(|x, y| y.cmp(x));
for idx in aff {
tris.swap_remove(idx);
}
tris.extend(new_tris);
} else {
tris.swap_remove(k);
tris.push([t[0], t[1], i]);
tris.push([t[1], t[2], i]);
tris.push([t[2], t[0], i]);
}
Some(())
}
fn ordered_edge(t: Tri, a: usize, b: usize) -> (usize, usize) {
for k in 0..3 {
let (x, y) = (t[k], t[(k + 1) % 3]);
if (x == a && y == b) || (x == b && y == a) {
return (x, y);
}
}
(a, b)
}
fn has_edge(t: Tri, a: usize, b: usize) -> bool {
t.contains(&a) && t.contains(&b)
}
fn edge_exists(tris: &[Tri], u: usize, v: usize) -> bool {
tris.iter().any(|t| has_edge(*t, u, v))
}
fn apex(t: Tri, a: usize, b: usize) -> Option<usize> {
t.iter().copied().find(|&x| x != a && x != b)
}
fn recover_edge(tris: &mut Vec<Tri>, pts: &[[f64; 2]], u: usize, v: usize) -> Option<()> {
if u == v || edge_exists(tris, u, v) {
return Some(());
}
let (su, sv) = (pts[u], pts[v]);
let mut guard = 0;
let cap = 16 * tris.len() + 128;
loop {
guard += 1;
if guard > cap {
return None; }
if edge_exists(tris, u, v) {
return Some(());
}
let mut reducing: Option<(usize, usize, usize, usize, usize, usize)> = None;
let mut fallback: Option<(usize, usize, usize, usize, usize, usize)> = None;
'search: for k1 in 0..tris.len() {
let t1 = tris[k1];
for e in 0..3 {
let (a, b) = (t1[e], t1[(e + 1) % 3]);
if a == u || a == v || b == u || b == v {
continue;
}
if !seg_cross(su, sv, pts[a], pts[b]) {
continue;
}
let Some(k2) = (0..tris.len()).find(|&j| j != k1 && has_edge(tris[j], a, b)) else {
continue;
};
let (Some(c), Some(d)) = (apex(t1, a, b), apex(tris[k2], a, b)) else {
continue;
};
if orient(pts[a], pts[b], pts[c]) * orient(pts[a], pts[b], pts[d]) < 0.0
&& orient(pts[c], pts[d], pts[a]) * orient(pts[c], pts[d], pts[b]) < 0.0
{
if !seg_cross(su, sv, pts[c], pts[d]) {
reducing = Some((k1, k2, a, b, c, d));
break 'search;
}
if fallback.is_none() {
fallback = Some((k1, k2, a, b, c, d));
}
}
}
}
let Some((k1, k2, a, b, c, d)) = reducing.or(fallback) else {
return None; };
let (hi, lo) = (k1.max(k2), k1.min(k2));
tris.swap_remove(hi);
tris.swap_remove(lo);
tris.push(ccw([c, d, a], pts));
tris.push(ccw([d, c, b], pts));
}
}
fn ccw(t: Tri, pts: &[[f64; 2]]) -> Tri {
if orient(pts[t[0]], pts[t[1]], pts[t[2]]) >= 0.0 {
t
} else {
[t[0], t[2], t[1]]
}
}
#[cfg(test)]
mod tests {
use super::*;
fn tri_area(pts: &[[f64; 2]], t: Tri) -> f64 {
0.5 * orient(pts[t[0]], pts[t[1]], pts[t[2]]).abs()
}
fn total_area(pts: &[[f64; 2]], tris: &[Tri]) -> f64 {
tris.iter().map(|t| tri_area(pts, *t)).sum()
}
const CORNERS: [[f64; 2]; 3] = [[0.0, 0.0], [4.0, 0.0], [0.0, 4.0]];
#[test]
fn plain_triangle() {
let out = triangulate_constrained(&CORNERS, &[]).unwrap();
assert_eq!(out.len(), 1);
}
#[test]
fn interior_point_no_constraint() {
let mut pts = CORNERS.to_vec();
pts.push([1.0, 1.0]);
let out = triangulate_constrained(&pts, &[]).unwrap();
assert_eq!(out.len(), 3);
assert!((total_area(&pts, &out) - 8.0).abs() < 1e-9);
}
#[test]
fn interior_interior_constraint_recovered() {
let mut pts = CORNERS.to_vec();
pts.push([1.0, 1.0]); pts.push([2.0, 0.5]); let out = triangulate_constrained(&pts, &[[3, 4]]).unwrap();
assert!(edge_exists(&out, 3, 4), "constraint edge present");
assert!(
(total_area(&pts, &out) - 8.0).abs() < 1e-9,
"area conserved"
);
for t in &out {
assert!(tri_area(&pts, *t) > 1e-9, "no degenerate triangle");
}
}
#[test]
fn interior_to_boundary_constraint() {
let mut pts = CORNERS.to_vec();
pts.push([1.0, 1.0]); pts.push([2.0, 2.0]); let out = triangulate_constrained(&pts, &[[3, 4]]).unwrap();
assert!(edge_exists(&out, 3, 4));
assert!((total_area(&pts, &out) - 8.0).abs() < 1e-9);
}
#[test]
fn large_face_ring_recovers_fast() {
use std::f64::consts::TAU;
let n = 120usize;
let mut pts = vec![[-20.0, -20.0], [20.0, -20.0], [0.0, 20.0]]; for i in 0..n {
let a = i as f64 * TAU / n as f64;
pts.push([3.0 * a.cos(), 3.0 * a.sin()]);
}
let cons: Vec<[usize; 2]> = (0..n).map(|i| [3 + i, 3 + (i + 1) % n]).collect();
let out = triangulate_constrained(&pts, &cons).expect("large constrained CDT");
for i in 0..n {
assert!(
edge_exists(&out, 3 + i, 3 + (i + 1) % n),
"ring edge {i} recovered"
);
}
assert!(
(total_area(&pts, &out) - 800.0).abs() < 1e-6,
"area conserved (½·40·40)"
);
assert!(
out.iter().all(|t| tri_area(&pts, *t) > 1e-9),
"no degenerate triangles"
);
}
}
#[cfg(test)]
mod degen {
use super::*;
fn area(pts: &[[f64; 2]], t: Tri) -> f64 {
0.5 * orient(pts[t[0]], pts[t[1]], pts[t[2]]).abs()
}
#[test]
fn point_on_edge_with_constraint() {
let pts = vec![
[0.0, 0.0],
[4.0, 0.0],
[0.0, 4.0], [1.0, 1.0], [2.0, 2.0], ];
let tris = triangulate_constrained(&pts, &[[3, 4]]).expect("CDT on point-on-edge");
let tot: f64 = tris.iter().map(|t| area(&pts, *t)).sum();
assert!(
(tot - 8.0).abs() < 1e-9,
"area conserved with a vertex on the edge"
);
assert!(edge_exists(&tris, 3, 4), "constraint recovered");
assert!(
tris.iter().all(|t| area(&pts, *t) > 1e-12),
"no degenerate slivers"
);
}
#[test]
fn rectangle_face_with_super_triangle() {
let sup = 400.0;
let mut pts = vec![[-sup, -sup], [sup, -sup], [0.0, sup]]; pts.extend([
[1.5307, 12.0],
[0.0, 12.0],
[1.5307, 0.0],
[0.0, 0.0], [1.4032, 11.0],
[1.5307, 11.0],
[1.5307, 1.0],
[0.1276, 1.0], [0.0, 11.0],
[0.0, 1.0], ]);
let cons = [
[4, 11],
[11, 12],
[12, 6], [5, 9],
[9, 8],
[8, 3], [3, 4],
[6, 5], [11, 7],
[7, 8], [12, 10],
[10, 9], ];
let tris = triangulate_constrained(&pts, &cons).expect("CDT on rectangle face");
let inside = |t: &Tri| {
let c = [
(pts[t[0]][0] + pts[t[1]][0] + pts[t[2]][0]) / 3.0,
(pts[t[0]][1] + pts[t[1]][1] + pts[t[2]][1]) / 3.0,
];
c[0] > 0.0 && c[0] < 1.5307 && c[1] > 0.0 && c[1] < 12.0
};
let a: f64 = tris
.iter()
.filter(|t| inside(t))
.map(|t| area(&pts, *t))
.sum();
assert!(
(a - 1.5307 * 12.0).abs() < 1e-6,
"rectangle area conserved, got {a}"
);
}
#[test]
fn constraint_along_edge() {
let pts = vec![[0.0, 0.0], [4.0, 0.0], [0.0, 4.0], [3.0, 1.0], [1.0, 3.0]];
let tris = triangulate_constrained(&pts, &[[3, 4]]).expect("CDT along-edge constraint");
assert!(edge_exists(&tris, 3, 4), "along-edge constraint recovered");
}
}