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::intersections::{SegmentIntersectionKind, segment_intersection_kind};
use crate::polygon::{
PointPolygonRelation, Polygon2, PolygonBasicValidity, PolygonSelfIntersection,
};
use crate::predicates::{Orientation, orient2d};
use crate::primitives::Point2;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[non_exhaustive]
pub enum PolygonTriangulationError {
TooFewVertices,
DegenerateEdge,
ZeroArea,
SelfIntersecting(PolygonSelfIntersection),
ConstraintInsertionFailed,
InvalidHole(usize, PolygonBasicValidity),
HoleSelfIntersecting(usize, PolygonSelfIntersection),
HoleIntersectsOuter(usize, SegmentIntersectionKind),
HoleOutsideOuter(usize),
HolesIntersect(usize, usize, SegmentIntersectionKind),
NestedHole(usize, usize),
}
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();
if faces.len() != n - 2 {
return Err(PolygonTriangulationError::ConstraintInsertionFailed);
}
Ok(assemble_triangulation(vertex_pos, faces))
}
pub fn triangulate_polygon_with_holes(
outer: &Polygon2,
holes: &[Polygon2],
) -> Result<Triangulation2, PolygonTriangulationError> {
match outer.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) = outer.find_self_intersection() {
return Err(PolygonTriangulationError::SelfIntersecting(found));
}
validate_holes(outer, holes)?;
let mut points: Vec<Point2> = outer.vertices().to_vec();
let mut hole_offsets = Vec::with_capacity(holes.len());
for hole in holes {
hole_offsets.push(points.len());
points.extend_from_slice(hole.vertices());
}
let n_outer = outer.len();
let mut constraints: Vec<(usize, usize)> =
(0..n_outer).map(|i| (i, (i + 1) % n_outer)).collect();
for (hole, &offset) in holes.iter().zip(&hole_offsets) {
let n_hole = hole.len();
constraints.extend((0..n_hole).map(|i| (offset + i, offset + (i + 1) % n_hole)));
}
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,
outer.vertices()[0],
outer.vertices()[1],
outer.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();
let expected_faces = points.len() + 2 * holes.len() - 2;
if faces.len() != expected_faces {
return Err(PolygonTriangulationError::ConstraintInsertionFailed);
}
Ok(assemble_triangulation(vertex_pos, faces))
}
fn find_ring_intersection(a: &Polygon2, b: &Polygon2) -> Option<SegmentIntersectionKind> {
for i in 0..a.len() {
for j in 0..b.len() {
let kind = segment_intersection_kind(a.edge(i), b.edge(j));
if kind != SegmentIntersectionKind::None {
return Some(kind);
}
}
}
None
}
fn ring_contains_ring(container: &Polygon2, inner: &Polygon2) -> bool {
inner
.vertices()
.first()
.is_some_and(|&v| container.relation_to(v) == PointPolygonRelation::Inside)
}
fn validate_holes(outer: &Polygon2, holes: &[Polygon2]) -> Result<(), PolygonTriangulationError> {
for (i, hole) in holes.iter().enumerate() {
match hole.basic_validity() {
PolygonBasicValidity::Valid => {}
other => return Err(PolygonTriangulationError::InvalidHole(i, other)),
}
if let Some(found) = hole.find_self_intersection() {
return Err(PolygonTriangulationError::HoleSelfIntersecting(i, found));
}
}
for (i, hole) in holes.iter().enumerate() {
match find_ring_intersection(outer, hole) {
Some(kind) => return Err(PolygonTriangulationError::HoleIntersectsOuter(i, kind)),
None if !ring_contains_ring(outer, hole) => {
return Err(PolygonTriangulationError::HoleOutsideOuter(i));
}
None => {}
}
}
for i in 0..holes.len() {
for j in (i + 1)..holes.len() {
match find_ring_intersection(&holes[i], &holes[j]) {
Some(kind) => return Err(PolygonTriangulationError::HolesIntersect(i, j, kind)),
None if ring_contains_ring(&holes[j], &holes[i]) => {
return Err(PolygonTriangulationError::NestedHole(i, j));
}
None if ring_contains_ring(&holes[i], &holes[j]) => {
return Err(PolygonTriangulationError::NestedHole(j, i));
}
None => {}
}
}
}
Ok(())
}
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:?}");
}
fn rect(x0: f64, y0: f64, x1: f64, y1: f64) -> Polygon2 {
Polygon2::new(vec![p(x0, y0), p(x1, y0), p(x1, y1), p(x0, y1)])
}
fn rect_cw(x0: f64, y0: f64, x1: f64, y1: f64) -> Polygon2 {
Polygon2::new(vec![p(x0, y0), p(x0, y1), p(x1, y1), p(x1, y0)])
}
fn tri_centroid(tri: crate::primitives::Triangle2) -> Point2 {
let (a, b, c) = (tri.a(), tri.b(), tri.c());
p((a.x() + b.x() + c.x()) / 3.0, (a.y() + b.y() + c.y()) / 3.0)
}
fn assert_boundary_edges_preserved(ring: &Polygon2, t: &Triangulation2) {
let vid_of = |pt: Point2| -> VertexId {
t.vertices()
.find(|&(_, q)| q == pt)
.unwrap_or_else(|| panic!("{pt:?} not a triangulation vertex"))
.0
};
for i in 0..ring.len() {
let edge = ring.edge(i);
let (u, v) = (vid_of(edge.a()), vid_of(edge.b()));
let exists = t.edges().any(|e| {
let (a, b) = t.edge_vertices(e);
(a == u && b == v) || (a == v && b == u)
});
assert!(exists, "boundary edge {i} ({edge:?}) missing from result");
}
}
fn assert_valid_holes_result(outer: &Polygon2, holes: &[Polygon2], t: &Triangulation2) {
let n: usize = outer.len() + holes.iter().map(|h| h.len()).sum::<usize>();
let h = holes.len();
assert_eq!(t.len(), n + 2 * h - 2, "triangle count");
for tri in t.triangles() {
assert_eq!(
tri.orientation(),
Orientation::CounterClockwise,
"not CCW: {tri:?}"
);
}
let outer_area = outer.signed_area().abs();
let holes_area: f64 = holes.iter().map(|hh| hh.signed_area().abs()).sum();
let total_area: f64 = t.triangles().iter().map(|&tri| tri_area(tri)).sum();
let want_area = outer_area - holes_area;
assert!(
(total_area - want_area).abs() < 1e-6,
"area conservation: got {total_area}, want {want_area}"
);
for &tri in t.triangles() {
let c = tri_centroid(tri);
assert_eq!(
outer.relation_to(c),
PointPolygonRelation::Inside,
"triangle centroid not inside outer: {tri:?}"
);
for hh in holes {
assert_eq!(
hh.relation_to(c),
PointPolygonRelation::Outside,
"triangle centroid inside a hole: {tri:?}"
);
}
}
assert_boundary_edges_preserved(outer, t);
for hh in holes {
assert_boundary_edges_preserved(hh, t);
}
let errs = validate_ignoring_hull_coverage(t);
assert!(errs.is_empty(), "{errs:?}");
}
#[test]
fn square_with_a_square_hole() {
let outer = rect(0.0, 0.0, 4.0, 4.0);
let holes = [rect(1.0, 1.0, 2.0, 2.0)];
let t = triangulate_polygon_with_holes(&outer, &holes).unwrap();
assert_valid_holes_result(&outer, &holes, &t);
}
#[test]
fn multiple_holes() {
let outer = rect(0.0, 0.0, 10.0, 10.0);
let holes = [rect(1.0, 1.0, 3.0, 3.0), rect(6.0, 6.0, 8.0, 8.0)];
let t = triangulate_polygon_with_holes(&outer, &holes).unwrap();
assert_valid_holes_result(&outer, &holes, &t);
}
#[test]
fn narrow_channel_outer_boundary_with_a_hole() {
let outer = Polygon2::new(vec![
p(0.0, 0.0),
p(10.0, 0.0),
p(10.0, 10.0),
p(7.0, 10.0),
p(7.0, 3.0),
p(3.0, 3.0),
p(3.0, 10.0),
p(0.0, 10.0),
]);
let holes = [rect(4.0, 0.5, 6.0, 1.5)];
let t = triangulate_polygon_with_holes(&outer, &holes).unwrap();
assert_valid_holes_result(&outer, &holes, &t);
}
#[test]
fn hole_very_close_to_the_outer_boundary() {
let outer = rect(0.0, 0.0, 10.0, 10.0);
let holes = [rect(0.1, 0.1, 2.0, 2.0)];
let t = triangulate_polygon_with_holes(&outer, &holes).unwrap();
assert_valid_holes_result(&outer, &holes, &t);
}
#[test]
fn cw_outer_ccw_hole() {
let outer = rect_cw(0.0, 0.0, 4.0, 4.0);
assert_eq!(outer.orientation(), Orientation::Clockwise);
let holes = [rect(1.0, 1.0, 2.0, 2.0)];
assert_eq!(holes[0].orientation(), Orientation::CounterClockwise);
let t = triangulate_polygon_with_holes(&outer, &holes).unwrap();
assert_valid_holes_result(&outer, &holes, &t);
}
#[test]
fn ccw_outer_cw_hole() {
let outer = rect(0.0, 0.0, 4.0, 4.0);
assert_eq!(outer.orientation(), Orientation::CounterClockwise);
let holes = [rect_cw(1.0, 1.0, 2.0, 2.0)];
assert_eq!(holes[0].orientation(), Orientation::Clockwise);
let t = triangulate_polygon_with_holes(&outer, &holes).unwrap();
assert_valid_holes_result(&outer, &holes, &t);
}
#[test]
fn hole_entirely_outside_outer_is_rejected() {
let outer = rect(0.0, 0.0, 4.0, 4.0);
let holes = [rect(10.0, 10.0, 12.0, 12.0)];
assert_eq!(
triangulate_polygon_with_holes(&outer, &holes),
Err(PolygonTriangulationError::HoleOutsideOuter(0))
);
}
#[test]
fn hole_touching_the_outer_boundary_is_rejected() {
let outer = rect(0.0, 0.0, 4.0, 4.0);
let holes = [Polygon2::new(vec![
p(2.0, 0.0),
p(3.0, 1.0),
p(2.0, 2.0),
p(1.0, 1.0),
])];
match triangulate_polygon_with_holes(&outer, &holes) {
Err(PolygonTriangulationError::HoleIntersectsOuter(
0,
SegmentIntersectionKind::EndpointTouch,
)) => {}
other => panic!("expected HoleIntersectsOuter(0, EndpointTouch), got {other:?}"),
}
}
#[test]
fn hole_crossing_the_outer_boundary_is_rejected() {
let outer = rect(0.0, 0.0, 4.0, 4.0);
let holes = [rect(-1.0, -1.0, 1.0, 1.0)];
match triangulate_polygon_with_holes(&outer, &holes) {
Err(PolygonTriangulationError::HoleIntersectsOuter(
0,
SegmentIntersectionKind::Proper,
)) => {}
other => panic!("expected HoleIntersectsOuter(0, Proper), got {other:?}"),
}
}
#[test]
fn holes_touching_each_other_is_rejected() {
let outer = rect(0.0, 0.0, 10.0, 10.0);
let holes = [rect(1.0, 1.0, 3.0, 3.0), rect(3.0, 1.0, 5.0, 3.0)];
match triangulate_polygon_with_holes(&outer, &holes) {
Err(PolygonTriangulationError::HolesIntersect(
0,
1,
SegmentIntersectionKind::CollinearTouch,
)) => {}
other => panic!("expected HolesIntersect(0, 1, CollinearTouch), got {other:?}"),
}
}
#[test]
fn holes_crossing_each_other_is_rejected() {
let outer = rect(0.0, 0.0, 10.0, 10.0);
let holes = [rect(1.0, 1.0, 3.0, 3.0), rect(2.0, 2.0, 4.0, 4.0)];
match triangulate_polygon_with_holes(&outer, &holes) {
Err(PolygonTriangulationError::HolesIntersect(
0,
1,
SegmentIntersectionKind::Proper,
)) => {}
other => panic!("expected HolesIntersect(0, 1, Proper), got {other:?}"),
}
}
#[test]
fn nested_hole_is_rejected() {
let outer = rect(0.0, 0.0, 10.0, 10.0);
let holes = [rect(1.0, 1.0, 5.0, 5.0), rect(2.0, 2.0, 3.0, 3.0)];
assert_eq!(
triangulate_polygon_with_holes(&outer, &holes),
Err(PolygonTriangulationError::NestedHole(1, 0))
);
}
#[test]
fn hole_with_too_few_vertices_is_rejected() {
let outer = rect(0.0, 0.0, 4.0, 4.0);
let holes = [Polygon2::new(vec![p(1.0, 1.0), p(2.0, 1.0)])];
assert_eq!(
triangulate_polygon_with_holes(&outer, &holes),
Err(PolygonTriangulationError::InvalidHole(
0,
PolygonBasicValidity::TooFewVertices
))
);
}
#[test]
fn self_intersecting_hole_is_rejected() {
let outer = rect(0.0, 0.0, 10.0, 10.0);
let holes = [Polygon2::new(vec![
p(1.0, 1.0),
p(7.0, 7.0),
p(7.0, 1.0),
p(1.0, 3.0),
])];
match triangulate_polygon_with_holes(&outer, &holes) {
Err(PolygonTriangulationError::HoleSelfIntersecting(0, found)) => {
assert_eq!(found.edge_a, 0);
assert_eq!(found.edge_b, 2);
}
other => panic!("expected HoleSelfIntersecting, got {other:?}"),
}
}
#[test]
fn deterministic_regardless_of_hole_starting_vertex() {
let outer = rect(0.0, 0.0, 10.0, 10.0);
let hole_a = rect(2.0, 2.0, 4.0, 4.0);
let hole_b = Polygon2::new(vec![p(4.0, 4.0), p(2.0, 4.0), p(2.0, 2.0), p(4.0, 2.0)]);
let t_a = triangulate_polygon_with_holes(&outer, &[hole_a]).unwrap();
let t_b = triangulate_polygon_with_holes(&outer, &[hole_b]).unwrap();
assert_eq!(t_a.triangles(), t_b.triangles());
}
#[test]
fn no_holes_matches_triangulate_polygon() {
let outer = 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 a = triangulate_polygon(&outer).unwrap();
let b = triangulate_polygon_with_holes(&outer, &[]).unwrap();
assert_eq!(a.triangles(), b.triangles());
}
}