use std::collections::{HashMap, HashSet, VecDeque};
use super::Triangulation2;
use super::cdt::constrained_delaunay2;
#[cfg(test)]
use super::delaunay2::TopologyError;
use super::delaunay2::assemble_triangulation;
use super::ids::{FaceId, VertexId};
use crate::polygon::{Polygon2, PolygonBasicValidity, PolygonSelfIntersection};
use crate::predicates::{Orientation, orient2d};
use crate::primitives::Point2;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum PolygonTriangulationError {
TooFewVertices,
DegenerateEdge,
ZeroArea,
SelfIntersecting(PolygonSelfIntersection),
ConstraintInsertionFailed,
}
pub fn triangulate_polygon(
polygon: &Polygon2,
) -> Result<Triangulation2, PolygonTriangulationError> {
match polygon.basic_validity() {
PolygonBasicValidity::TooFewVertices => {
return Err(PolygonTriangulationError::TooFewVertices);
}
PolygonBasicValidity::ConsecutiveDuplicateVertices => {
return Err(PolygonTriangulationError::DegenerateEdge);
}
PolygonBasicValidity::ZeroArea => {
return Err(PolygonTriangulationError::ZeroArea);
}
PolygonBasicValidity::Valid => {}
}
if let Some(found) = polygon.find_self_intersection() {
return Err(PolygonTriangulationError::SelfIntersecting(found));
}
let points = polygon.vertices();
let n = points.len();
let constraints: Vec<(usize, usize)> = (0..n).map(|i| (i, (i + 1) % n)).collect();
let cdt = constrained_delaunay2(points, &constraints)
.map_err(|_| PolygonTriangulationError::ConstraintInsertionFailed)?;
let coord: HashMap<VertexId, Point2> = cdt.triangulation().vertices().collect();
let seed = interior_seed_face(&cdt, &coord, points[0], points[1], polygon.orientation())
.ok_or(PolygonTriangulationError::ConstraintInsertionFailed)?;
let interior = flood_fill_interior(&cdt, seed);
let vertex_pos: Vec<Point2> = cdt.triangulation().vertices().map(|(_, p)| p).collect();
let faces: Vec<[VertexId; 3]> = cdt
.triangulation()
.faces()
.filter(|f| interior.contains(f))
.map(|f| cdt.triangulation().face_vertices(f))
.collect();
Ok(assemble_triangulation(vertex_pos, faces))
}
fn interior_seed_face(
cdt: &super::ConstrainedTriangulation2,
coord: &HashMap<VertexId, Point2>,
p0: Point2,
p1: Point2,
orientation: Orientation,
) -> Option<FaceId> {
let vertex_of = |p: Point2| coord.iter().find(|&(_, &q)| q == p).map(|(&id, _)| id);
let u = vertex_of(p0)?;
let v = vertex_of(p1)?;
let edge = cdt.triangulation().edges().find(|&e| {
let (a, b) = cdt.triangulation().edge_vertices(e);
(a == u && b == v) || (a == v && b == u)
})?;
for face in cdt
.triangulation()
.adjacent_faces(edge)
.into_iter()
.flatten()
{
let tri = cdt.triangulation().face_vertices(face);
let Some(&apex) = tri.iter().find(|&&x| x != u && x != v) else {
continue;
};
let side = orient2d(p0, p1, coord[&apex]);
let is_interior = match orientation {
Orientation::CounterClockwise => side == Orientation::CounterClockwise,
Orientation::Clockwise => side == Orientation::Clockwise,
Orientation::Collinear => false,
};
if is_interior {
return Some(face);
}
}
None
}
fn flood_fill_interior(cdt: &super::ConstrainedTriangulation2, seed: FaceId) -> HashSet<FaceId> {
let mut links: HashMap<FaceId, Vec<FaceId>> = HashMap::new();
for edge in cdt.triangulation().edges() {
if cdt.is_constrained(edge) {
continue;
}
if let [Some(fa), Some(fb)] = cdt.triangulation().adjacent_faces(edge) {
links.entry(fa).or_default().push(fb);
links.entry(fb).or_default().push(fa);
}
}
let mut interior = HashSet::new();
let mut queue = VecDeque::new();
interior.insert(seed);
queue.push_back(seed);
while let Some(face) = queue.pop_front() {
for &neighbor in links.get(&face).into_iter().flatten() {
if interior.insert(neighbor) {
queue.push_back(neighbor);
}
}
}
interior
}
#[cfg(test)]
mod tests {
use super::*;
fn p(x: f64, y: f64) -> Point2 {
Point2::new(x, y).unwrap()
}
fn tri_area(tri: crate::primitives::Triangle2) -> f64 {
let (a, b, c) = (tri.a(), tri.b(), tri.c());
((b.x() - a.x()) * (c.y() - a.y()) - (c.x() - a.x()) * (b.y() - a.y())).abs() / 2.0
}
fn validate_ignoring_hull_coverage(t: &Triangulation2) -> Vec<TopologyError> {
t.validate_topology()
.into_iter()
.filter(|e| !matches!(e, TopologyError::EulerFormulaViolated { .. }))
.collect()
}
#[test]
fn triangle_triangulates_to_itself() {
let poly = Polygon2::new(vec![p(0.0, 0.0), p(4.0, 0.0), p(0.0, 4.0)]);
let t = triangulate_polygon(&poly).unwrap();
assert_eq!(t.len(), 1);
assert!(t.validate_topology().is_empty());
}
#[test]
fn convex_square_triangulates_to_two_triangles() {
let poly = Polygon2::new(vec![p(0.0, 0.0), p(4.0, 0.0), p(4.0, 4.0), p(0.0, 4.0)]);
let t = triangulate_polygon(&poly).unwrap();
assert_eq!(t.len(), 2);
assert!(t.validate_topology().is_empty());
for tri in t.triangles() {
assert_eq!(tri.orientation(), Orientation::CounterClockwise);
}
}
#[test]
fn clockwise_input_triangulates_the_same_region() {
let ccw = Polygon2::new(vec![p(0.0, 0.0), p(4.0, 0.0), p(4.0, 4.0), p(0.0, 4.0)]);
let cw = Polygon2::new(vec![p(0.0, 0.0), p(0.0, 4.0), p(4.0, 4.0), p(4.0, 0.0)]);
assert_eq!(ccw.orientation(), Orientation::CounterClockwise);
assert_eq!(cw.orientation(), Orientation::Clockwise);
let t_ccw = triangulate_polygon(&ccw).unwrap();
let t_cw = triangulate_polygon(&cw).unwrap();
assert_eq!(t_ccw.len(), 2);
assert_eq!(t_cw.len(), 2);
let area =
|t: &Triangulation2| -> f64 { t.triangles().iter().map(|&tri| tri_area(tri)).sum() };
assert_eq!(area(&t_ccw), 16.0);
assert_eq!(area(&t_cw), 16.0);
}
#[test]
fn l_shape_discards_the_concave_pocket() {
let poly = Polygon2::new(vec![
p(0.0, 0.0),
p(4.0, 0.0),
p(4.0, 2.0),
p(2.0, 2.0),
p(2.0, 4.0),
p(0.0, 4.0),
]);
let expected_area = 12.0; let t = triangulate_polygon(&poly).unwrap();
let errs = validate_ignoring_hull_coverage(&t);
assert!(errs.is_empty(), "{errs:?} triangles={:?}", t.triangles());
assert_eq!(t.len(), poly.len() - 2);
let area: f64 = t.triangles().iter().map(|&tri| tri_area(tri)).sum();
assert_eq!(area, expected_area);
for tri in t.triangles() {
assert_eq!(tri.orientation(), Orientation::CounterClockwise);
}
for v in t.vertices() {
assert!(poly.vertices().contains(&v.1));
}
}
#[test]
fn too_few_vertices_is_rejected() {
let poly = Polygon2::new(vec![p(0.0, 0.0), p(1.0, 0.0)]);
assert_eq!(
triangulate_polygon(&poly),
Err(PolygonTriangulationError::TooFewVertices)
);
}
#[test]
fn consecutive_duplicate_vertex_is_rejected() {
let poly = Polygon2::new(vec![p(0.0, 0.0), p(0.0, 0.0), p(1.0, 0.0), p(0.0, 1.0)]);
assert_eq!(
triangulate_polygon(&poly),
Err(PolygonTriangulationError::DegenerateEdge)
);
}
#[test]
fn collinear_zero_area_is_rejected() {
let poly = Polygon2::new(vec![p(0.0, 0.0), p(1.0, 0.0), p(2.0, 0.0)]);
assert_eq!(
triangulate_polygon(&poly),
Err(PolygonTriangulationError::ZeroArea)
);
}
#[test]
fn self_intersecting_bowtie_is_rejected() {
let poly = Polygon2::new(vec![p(0.0, 0.0), p(6.0, 6.0), p(6.0, 0.0), p(0.0, 2.0)]);
assert_ne!(poly.basic_validity(), PolygonBasicValidity::ZeroArea);
match triangulate_polygon(&poly) {
Err(PolygonTriangulationError::SelfIntersecting(found)) => {
assert_eq!(found.edge_a, 0);
assert_eq!(found.edge_b, 2);
}
other => panic!("expected SelfIntersecting, got {other:?}"),
}
}
#[test]
fn deterministic_regardless_of_starting_vertex() {
let poly_a = Polygon2::new(vec![
p(0.0, 0.0),
p(4.0, 0.0),
p(4.0, 2.0),
p(2.0, 2.0),
p(2.0, 4.0),
p(0.0, 4.0),
]);
let poly_b = Polygon2::new(vec![
p(2.0, 2.0),
p(2.0, 4.0),
p(0.0, 4.0),
p(0.0, 0.0),
p(4.0, 0.0),
p(4.0, 2.0),
]);
let t_a = triangulate_polygon(&poly_a).unwrap();
let t_b = triangulate_polygon(&poly_b).unwrap();
assert_eq!(t_a.triangles(), t_b.triangles());
}
#[test]
fn seed_edge_with_two_incident_faces_still_finds_the_interior_side() {
let poly = Polygon2::new(vec![
p(4.0, 2.0),
p(2.0, 2.0),
p(2.0, 4.0),
p(0.0, 4.0),
p(0.0, 0.0),
p(4.0, 0.0),
]);
let t = triangulate_polygon(&poly).unwrap();
assert_eq!(t.len(), poly.len() - 2);
let area: f64 = t.triangles().iter().map(|&tri| tri_area(tri)).sum();
assert_eq!(area, 12.0);
let errs = validate_ignoring_hull_coverage(&t);
assert!(errs.is_empty(), "{errs:?}");
}
#[test]
fn plus_shape_discards_all_four_separate_pockets() {
let poly = Polygon2::new(vec![
p(2.0, 0.0),
p(4.0, 0.0),
p(4.0, 2.0),
p(6.0, 2.0),
p(6.0, 4.0),
p(4.0, 4.0),
p(4.0, 6.0),
p(2.0, 6.0),
p(2.0, 4.0),
p(0.0, 4.0),
p(0.0, 2.0),
p(2.0, 2.0),
]);
assert_eq!(poly.orientation(), Orientation::CounterClockwise);
let t = triangulate_polygon(&poly).unwrap();
assert_eq!(t.len(), poly.len() - 2);
let area: f64 = t.triangles().iter().map(|&tri| tri_area(tri)).sum();
assert_eq!(area, 20.0); let errs = validate_ignoring_hull_coverage(&t);
assert!(errs.is_empty(), "{errs:?}");
}
}