Skip to main content

section_properties/mesh/
triangulation.rs

1//! Triangulation algorithms for polygon mesh generation.
2//!
3//! Implements ear clipping for simple polygons and Delaunay refinement.
4
5use crate::geometry::{Point, Polygon};
6use crate::section::Section;
7
8/// Triangle defined by three vertex indices (CCW orientation).
9#[derive(Debug, Clone, Copy, PartialEq)]
10pub struct Triangle {
11    pub v: [usize; 3],
12}
13
14impl Triangle {
15    pub fn new(a: usize, b: usize, c: usize) -> Self {
16        Self { v: [a, b, c] }
17    }
18
19    /// Get the three vertex indices.
20    pub fn vertices(&self) -> [usize; 3] {
21        self.v
22    }
23
24    /// Check if point is inside triangle (using barycentric coordinates).
25    pub fn contains_point(&self, points: &[Point], p: Point) -> bool {
26        let a = points[self.v[0]];
27        let b = points[self.v[1]];
28        let c = points[self.v[2]];
29
30        let v0 = Point::new(c.x - a.x, c.y - a.y);
31        let v1 = Point::new(b.x - a.x, b.y - a.y);
32        let v2 = Point::new(p.x - a.x, p.y - a.y);
33
34        let dot00 = v0.x * v0.x + v0.y * v0.y;
35        let dot01 = v0.x * v1.x + v0.y * v1.y;
36        let dot02 = v0.x * v2.x + v0.y * v2.y;
37        let dot11 = v1.x * v1.x + v1.y * v1.y;
38        let dot12 = v1.x * v2.x + v1.y * v2.y;
39
40        let inv_denom = 1.0 / (dot00 * dot11 - dot01 * dot01);
41        let u = (dot11 * dot02 - dot01 * dot12) * inv_denom;
42        let v = (dot00 * dot12 - dot01 * dot02) * inv_denom;
43
44        u >= -1e-10 && v >= -1e-10 && (u + v) <= 1.0 + 1e-10
45    }
46
47    /// Compute triangle area (signed, positive for CCW).
48    pub fn signed_area(&self, points: &[Point]) -> f64 {
49        let a = points[self.v[0]];
50        let b = points[self.v[1]];
51        let c = points[self.v[2]];
52        0.5 * ((b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y))
53    }
54
55    /// Compute triangle circumcircle (center and radius squared).
56    pub fn circumcircle(&self, points: &[Point]) -> (Point, f64) {
57        let a = points[self.v[0]];
58        let b = points[self.v[1]];
59        let c = points[self.v[2]];
60
61        let d = 2.0 * (a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y));
62        if d.abs() < 1e-12 {
63            return (Point::new(0.0, 0.0), f64::INFINITY);
64        }
65
66        let ux = ((a.x * a.x + a.y * a.y) * (b.y - c.y)
67            + (b.x * b.x + b.y * b.y) * (c.y - a.y)
68            + (c.x * c.x + c.y * c.y) * (a.y - b.y))
69            / d;
70        let uy = ((a.x * a.x + a.y * a.y) * (c.x - b.x)
71            + (b.x * b.x + b.y * b.y) * (a.x - c.x)
72            + (c.x * c.x + c.y * c.y) * (b.x - a.x))
73            / d;
74
75        let center = Point::new(ux, uy);
76        let r2 = (a.x - ux).powi(2) + (a.y - uy).powi(2);
77        (center, r2)
78    }
79}
80
81/// Triangulation result containing triangles and boundary information.
82#[derive(Debug, Clone)]
83pub struct Triangulation {
84    pub triangles: Vec<Triangle>,
85    pub boundary_edges: Vec<[usize; 2]>,
86    pub hole_edges: Vec<Vec<[usize; 2]>>,
87}
88
89impl Triangulation {
90    pub fn new() -> Self {
91        Self {
92            triangles: Vec::new(),
93            boundary_edges: Vec::new(),
94            hole_edges: Vec::new(),
95        }
96    }
97
98    pub fn n_triangles(&self) -> usize {
99        self.triangles.len()
100    }
101}
102
103impl Default for Triangulation {
104    fn default() -> Self {
105        Self::new()
106    }
107}
108
109/// Check if a vertex is an "ear" in a polygon.
110fn is_ear(polygon: &[usize], _vertices: &[Point], i: usize, all_vertices: &[Point]) -> bool {
111    let n = polygon.len();
112    if n < 3 {
113        return false;
114    }
115
116    let prev = polygon[(i + n - 1) % n];
117    let curr = polygon[i];
118    let next = polygon[(i + 1) % n];
119
120    let a = all_vertices[prev];
121    let b = all_vertices[curr];
122    let c = all_vertices[next];
123
124    // Check if angle is convex (CCW polygon -> positive signed area)
125    let cross = (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x);
126    if cross <= 1e-12 {
127        return false; // Not a convex vertex
128    }
129
130    // Check if any other vertex lies inside this triangle
131    for &idx in polygon.iter() {
132        if idx == prev || idx == curr || idx == next {
133            continue;
134        }
135        let p = all_vertices[idx];
136        // Barycentric test
137        let v0 = Point::new(c.x - a.x, c.y - a.y);
138        let v1 = Point::new(b.x - a.x, b.y - a.y);
139        let v2 = Point::new(p.x - a.x, p.y - a.y);
140
141        let dot00 = v0.x * v0.x + v0.y * v0.y;
142        let dot01 = v0.x * v1.x + v0.y * v1.y;
143        let dot02 = v0.x * v2.x + v0.y * v2.y;
144        let dot11 = v1.x * v1.x + v1.y * v1.y;
145        let dot12 = v1.x * v2.x + v1.y * v2.y;
146
147        let inv_denom = 1.0 / (dot00 * dot11 - dot01 * dot01);
148        let u = (dot11 * dot02 - dot01 * dot12) * inv_denom;
149        let v = (dot00 * dot12 - dot01 * dot02) * inv_denom;
150
151        if u > 1e-10 && v > 1e-10 && (u + v) < 1.0 - 1e-10 {
152            return false; // Another vertex inside ear
153        }
154    }
155
156    // The new diagonal (prev -> next) must be interior. If another polygon
157    // vertex lies exactly on that open segment, clipping this "ear" is invalid:
158    // it leaves a self-intersecting remainder, no further ear is found, and the
159    // fan fallback then covers the convex hull instead of the polygon. That
160    // silently inflated the mesh area for I-shaped sections (7.75x) and
161    // corrupted the warping FEM torsion constant.
162    //
163    // Only the diagonal is checked (not the two polygon edges prev-curr and
164    // curr-next, which may legitimately carry collinear vertices in bridged
165    // hole/keyhole polygons).
166    let ab = Point::new(c.x - a.x, c.y - a.y); // prev -> next
167    let ab_len2 = ab.x * ab.x + ab.y * ab.y;
168    let diag_tol = 1e-9 * ab_len2.sqrt().max(1.0);
169    for &idx in polygon.iter() {
170        if idx == prev || idx == curr || idx == next {
171            continue;
172        }
173        let p = all_vertices[idx];
174        let ap = Point::new(p.x - a.x, p.y - a.y);
175        let cross = ab.x * ap.y - ab.y * ap.x;
176        let dist = cross.abs() / ab_len2.max(f64::MIN_POSITIVE).sqrt();
177        if dist <= diag_tol {
178            let t = (ap.x * ab.x + ap.y * ab.y) / ab_len2.max(f64::MIN_POSITIVE);
179            if t > 1e-9 && t < 1.0 - 1e-9 {
180                return false; // Diagonal passes through another vertex
181            }
182        }
183    }
184
185    true
186}
187
188/// Ear clipping triangulation for simple polygons (no holes).
189pub fn triangulate_polygon_ear_clipping(polygon: &Polygon) -> Vec<Triangle> {
190    let vertices = &polygon.vertices;
191    let n = vertices.len();
192    if n < 3 {
193        return Vec::new();
194    }
195
196    // Ensure CCW orientation
197    let signed_area = polygon.signed_area();
198    let mut vertex_indices: Vec<usize> = (0..n).collect();
199    if signed_area < 0.0 {
200        vertex_indices.reverse();
201    }
202
203    let mut triangles = Vec::new();
204    let mut remaining = vertex_indices.clone();
205
206    let mut guard = 0;
207    while remaining.len() > 3 && guard < n * n {
208        guard += 1;
209        let mut ear_found = false;
210
211        for i in 0..remaining.len() {
212            if is_ear(&remaining, vertices, i, vertices) {
213                let prev = remaining[(i + remaining.len() - 1) % remaining.len()];
214                let curr = remaining[i];
215                let next = remaining[(i + 1) % remaining.len()];
216
217                triangles.push(Triangle::new(prev, curr, next));
218                remaining.remove(i);
219                ear_found = true;
220                break;
221            }
222        }
223
224        if !ear_found {
225            // Polygon may have self-intersections or be degenerate
226            // Fall back to fan triangulation from first vertex
227            for i in 1..remaining.len() - 1 {
228                triangles.push(Triangle::new(remaining[0], remaining[i], remaining[i + 1]));
229            }
230            break;
231        }
232    }
233
234    if remaining.len() == 3 {
235        triangles.push(Triangle::new(remaining[0], remaining[1], remaining[2]));
236    }
237
238    triangles
239}
240
241/// Strict interior intersection of segments (shared endpoints excluded).
242fn segments_properly_intersect(p1: Point, p2: Point, q1: Point, q2: Point) -> bool {
243    fn d(a: Point, b: Point, c: Point) -> f64 {
244        (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x)
245    }
246    let d1 = d(q1, q2, p1);
247    let d2 = d(q1, q2, p2);
248    let d3 = d(p1, p2, q1);
249    let d4 = d(p1, p2, q2);
250    ((d1 > 0.0 && d2 < 0.0) || (d1 < 0.0 && d2 > 0.0))
251        && ((d3 > 0.0 && d4 < 0.0) || (d3 < 0.0 && d4 > 0.0))
252}
253
254/// Check that the bridge segment `a`-`b` does not cross any edge of `chain`
255/// (edges sharing an endpoint with the bridge are ignored) and its midpoint
256/// lies inside the material region.
257fn bridge_is_valid(chain: &[Point], a: Point, b: Point) -> bool {
258    let n = chain.len();
259    for k in 0..n {
260        let c = chain[k];
261        let e = chain[(k + 1) % n];
262        let touches = c == a || e == a || c == b || e == b;
263        if !touches && segments_properly_intersect(a, b, c, e) {
264            return false;
265        }
266    }
267    true
268}
269
270/// Merge hole boundaries into the outer boundary using keyhole bridges so
271/// that a single simple-polygon ear-clipping triangulates the material
272/// exactly (hole boundaries become mesh edges). Returns vertex list.
273fn merge_holes_into_outer(outer: &Polygon, holes: &[Polygon]) -> Vec<Point> {
274    let mut verts = outer.vertices.clone();
275
276    // Sort holes by area (largest first) for stability.
277    let mut ordered: Vec<&Polygon> = holes.iter().collect();
278    ordered.sort_by(|x, y| y.area().partial_cmp(&x.area()).unwrap());
279
280    for hole in ordered {
281        let hv = &hole.vertices;
282        let nh = hv.len();
283        let nv = verts.len();
284
285        // Candidate pairs sorted by distance.
286        let mut candidates: Vec<(f64, usize, usize)> = Vec::new();
287        for i in 0..nv {
288            for j in 0..nh {
289                let dx = verts[i].x - hv[j].x;
290                let dy = verts[i].y - hv[j].y;
291                candidates.push((dx * dx + dy * dy, i, j));
292            }
293        }
294        candidates.sort_by(|x, y| x.0.partial_cmp(&y.0).unwrap());
295
296        // Bridge midpoints must lie in material: outside every hole and
297        // inside the outer boundary.
298        let mut merged: Option<Vec<Point>> = None;
299        for &(_, i, j) in &candidates {
300            let a = verts[i];
301            let b = hv[j];
302            let mid = Point::new(0.5 * (a.x + b.x), 0.5 * (a.y + b.y));
303            if !outer.contains_point(mid) || holes.iter().any(|h| h.contains_point(mid)) {
304                continue;
305            }
306            if !bridge_is_valid(&verts, a, b) {
307                continue;
308            }
309            let mut m: Vec<Point> = Vec::with_capacity(nv + nh + 2);
310            m.extend_from_slice(&verts[..=i]);
311            for k in 0..=nh {
312                m.push(hv[(j + k) % nh]);
313            }
314            m.push(verts[i]);
315            m.extend_from_slice(&verts[i + 1..]);
316            merged = Some(m);
317            break;
318        }
319
320        match merged {
321            Some(m) => verts = m,
322            // Fallback: leave this hole unbridged; caller's carving handles it.
323            None => continue,
324        }
325    }
326
327    verts
328}
329
330/// Triangulate a section (outer + holes), keeping hole boundaries as exact
331/// mesh edges via keyhole bridging.
332pub fn triangulate_section_bridged(
333    outer: &Polygon,
334    holes: &[Polygon],
335) -> (Vec<Point>, Vec<[usize; 3]>) {
336    if holes.is_empty() {
337        let tris = triangulate_polygon_ear_clipping(outer);
338        return (outer.vertices.clone(), tris.iter().map(|t| t.v).collect());
339    }
340
341    let merged_points = merge_holes_into_outer(outer, holes);
342    let poly = Polygon::new(merged_points.clone());
343    let tris = triangulate_polygon_ear_clipping(&poly);
344
345    // Map back through Polygon's dedup: rebuild index triples by coordinate.
346    let mut nodes: Vec<Point> = Vec::new();
347    let mut index_of: std::collections::HashMap<(u64, u64), usize> =
348        std::collections::HashMap::new();
349    let key = |p: &Point| -> (u64, u64) { (p.x.to_bits(), p.y.to_bits()) };
350    let mut elements = Vec::with_capacity(tris.len());
351    for tri in &tris {
352        let mut tri_idx = [0usize; 3];
353        for (k, vi) in tri.v.iter().enumerate() {
354            let p = poly.vertices[*vi];
355            let next = nodes.len();
356            let idx = *index_of.entry(key(&p)).or_insert_with(|| {
357                nodes.push(p);
358                next
359            });
360            tri_idx[k] = idx;
361        }
362        // Keep even near-degenerate bridge slivers: they carry connectivity.
363        elements.push(tri_idx);
364    }
365
366    (nodes, elements)
367}
368
369/// Delaunay triangulation using Bowyer-Watson algorithm (incremental).
370pub fn triangulate_delaunay(points: &[Point]) -> Vec<Triangle> {
371    if points.len() < 3 {
372        return Vec::new();
373    }
374
375    // Super-triangle encompassing all points
376    let mut min_x = f64::INFINITY;
377    let mut max_x = f64::NEG_INFINITY;
378    let mut min_y = f64::INFINITY;
379    let mut max_y = f64::NEG_INFINITY;
380
381    for p in points {
382        min_x = min_x.min(p.x);
383        max_x = max_x.max(p.x);
384        min_y = min_y.min(p.y);
385        max_y = max_y.max(p.y);
386    }
387
388    let dx = max_x - min_x;
389    let dy = max_y - min_y;
390    let delta_max = dx.max(dy);
391    let mid_x = (min_x + max_x) / 2.0;
392    let mid_y = (min_y + max_y) / 2.0;
393
394    let super_a = Point::new(mid_x - 20.0 * delta_max, mid_y - delta_max);
395    let super_b = Point::new(mid_x, mid_y + 20.0 * delta_max);
396    let super_c = Point::new(mid_x + 20.0 * delta_max, mid_y - delta_max);
397
398    let mut all_points = points.to_vec();
399    let super_a_idx = all_points.len();
400    all_points.push(super_a);
401    let super_b_idx = all_points.len();
402    all_points.push(super_b);
403    let super_c_idx = all_points.len();
404    all_points.push(super_c);
405
406    let mut triangles = vec![Triangle::new(super_a_idx, super_b_idx, super_c_idx)];
407
408    // Insert points one by one
409    for i in 0..points.len() {
410        let p = points[i];
411        let mut bad_triangles = Vec::new();
412
413        // Find all triangles whose circumcircle contains the point
414        for (ti, tri) in triangles.iter().enumerate() {
415            let (center, r2) = tri.circumcircle(&all_points);
416            let dist2 = (p.x - center.x).powi(2) + (p.y - center.y).powi(2);
417            if dist2 <= r2 + 1e-10 {
418                bad_triangles.push(ti);
419            }
420        }
421
422        // Find boundary edges of the polygonal hole
423        let mut edge_count = std::collections::HashMap::new();
424        for &ti in &bad_triangles {
425            let tri = triangles[ti];
426            for edge in [
427                [tri.v[0], tri.v[1]],
428                [tri.v[1], tri.v[2]],
429                [tri.v[2], tri.v[0]],
430            ] {
431                let key = if edge[0] < edge[1] {
432                    edge
433                } else {
434                    [edge[1], edge[0]]
435                };
436                *edge_count.entry(key).or_insert(0) += 1;
437            }
438        }
439
440        // Remove bad triangles (in reverse order to keep indices valid)
441        for &ti in bad_triangles.iter().rev() {
442            triangles.remove(ti);
443        }
444
445        // Re-triangulate the hole
446        for (edge, &count) in &edge_count {
447            if count == 1 {
448                // Boundary edge - form new triangle with the inserted point
449                triangles.push(Triangle::new(edge[0], edge[1], i));
450            }
451        }
452    }
453
454    // Remove triangles that use super-triangle vertices
455    triangles.retain(|tri| {
456        tri.v[0] < points.len() && tri.v[1] < points.len() && tri.v[2] < points.len()
457    });
458
459    triangles
460}
461
462/// Triangulate a section (outer boundary + holes) using constrained Delaunay.
463pub fn triangulate_section(
464    section: &Section,
465    params: crate::mesh::MeshParams,
466) -> crate::mesh::Mesh {
467    let outer = &section.outer;
468    let holes = &section.holes;
469
470    // Prefer bridged triangulation: hole boundaries become exact mesh edges.
471    let (mut nodes, mut elements) = triangulate_section_bridged(outer, holes);
472
473    // Refine uniformly to honour the target element size (ear clipping
474    // produces only boundary vertices otherwise).
475    refine_mesh_uniform(
476        &mut nodes,
477        &mut elements,
478        params.target_size.max(1e-6),
479        params.max_iterations.clamp(1, 12),
480        params.max_nodes,
481    );
482
483    let outer_start = 0;
484    let outer_end = outer.vertices.len();
485    let boundary_indices: Vec<usize> = (outer_start..outer_end).collect();
486
487    let mut hole_boundary_indices = Vec::new();
488    if holes.is_empty() {
489        // Bridged path already handled everything; identify hole nodes by
490        // coordinate match for API completeness.
491    } else {
492        for hole in holes {
493            let idx: Vec<usize> = hole
494                .vertices
495                .iter()
496                .filter_map(|p| nodes.iter().position(|q| q == p))
497                .collect();
498            hole_boundary_indices.push(idx);
499        }
500    }
501
502    let mut mesh = crate::mesh::Mesh::new();
503    mesh.nodes = nodes;
504    mesh.elements = elements;
505    mesh.boundary_nodes = boundary_indices;
506    mesh.hole_boundary_nodes = hole_boundary_indices;
507    mesh.element_materials = vec![0; mesh.elements.len()];
508
509    mesh
510}
511
512/// Uniform (red) refinement by edge midpoint subdivision until all edges are
513/// below `target_size`. Keeps the mesh conforming; original vertex order is
514/// preserved so boundary index ranges stay valid.
515pub(crate) fn refine_mesh_uniform(
516    nodes: &mut Vec<Point>,
517    elements: &mut Vec<[usize; 3]>,
518    target_size: f64,
519    max_iterations: usize,
520    max_nodes: usize,
521) {
522    use std::collections::HashMap;
523
524    for _ in 0..max_iterations {
525        let needs = elements.iter().any(|tri| {
526            let p0 = nodes[tri[0]];
527            let p1 = nodes[tri[1]];
528            let p2 = nodes[tri[2]];
529            let d01 = ((p1.x - p0.x).powi(2) + (p1.y - p0.y).powi(2)).sqrt();
530            let d12 = ((p2.x - p1.x).powi(2) + (p2.y - p1.y).powi(2)).sqrt();
531            let d20 = ((p0.x - p2.x).powi(2) + (p0.y - p2.y).powi(2)).sqrt();
532            d01.max(d12).max(d20) > target_size
533        });
534        if !needs || nodes.len() >= max_nodes / 4 {
535            break;
536        }
537
538        let mut edge_map: HashMap<(usize, usize), usize> = HashMap::new();
539        let mut new_elements = Vec::with_capacity(elements.len() * 4);
540        for &elem in elements.iter() {
541            let mut mid = |a: usize, b: usize| -> usize {
542                let key = if a < b { (a, b) } else { (b, a) };
543                if let Some(&m) = edge_map.get(&key) {
544                    return m;
545                }
546                let pa = nodes[a];
547                let pb = nodes[b];
548                let idx = nodes.len();
549                nodes.push(Point::new(0.5 * (pa.x + pb.x), 0.5 * (pa.y + pb.y)));
550                edge_map.insert(key, idx);
551                idx
552            };
553            let m01 = mid(elem[0], elem[1]);
554            let m12 = mid(elem[1], elem[2]);
555            let m20 = mid(elem[2], elem[0]);
556            new_elements.push([elem[0], m01, m20]);
557            new_elements.push([m01, elem[1], m12]);
558            new_elements.push([m20, m12, elem[2]]);
559            new_elements.push([m01, m12, m20]);
560        }
561        *elements = new_elements;
562    }
563}
564
565/// Triangulate a simple polygon (no holes).
566pub fn triangulate_polygon(polygon: &Polygon) -> Vec<Triangle> {
567    triangulate_polygon_ear_clipping(polygon)
568}
569
570/// Refine triangulation using Delaunay edge flips.
571pub fn refine_delaunay(triangles: &mut [Triangle], points: &[Point]) {
572    let mut changed = true;
573    let mut iterations = 0;
574
575    while changed && iterations < 10 {
576        changed = false;
577        iterations += 1;
578
579        // Build edge to triangle adjacency
580        let mut edge_map: std::collections::HashMap<[usize; 2], Vec<usize>> =
581            std::collections::HashMap::new();
582        for (ti, tri) in triangles.iter().enumerate() {
583            for edge in [
584                [tri.v[0], tri.v[1]],
585                [tri.v[1], tri.v[2]],
586                [tri.v[2], tri.v[0]],
587            ] {
588                let key = if edge[0] < edge[1] {
589                    edge
590                } else {
591                    [edge[1], edge[0]]
592                };
593                edge_map.entry(key).or_default().push(ti);
594            }
595        }
596
597        // Check each interior edge for Delaunay condition
598        for (edge, adj_tris) in &edge_map {
599            if adj_tris.len() == 2 {
600                let t1 = triangles[adj_tris[0]];
601                let t2 = triangles[adj_tris[1]];
602
603                // Find opposite vertices
604                let opp1 =
605                    t1.v.iter()
606                        .find(|&&v| v != edge[0] && v != edge[1])
607                        .copied()
608                        .unwrap();
609                let opp2 =
610                    t2.v.iter()
611                        .find(|&&v| v != edge[0] && v != edge[1])
612                        .copied()
613                        .unwrap();
614
615                // Check if edge is locally Delaunay
616                let (center1, r2_1) = t1.circumcircle(points);
617                let p2 = points[opp2];
618                let dist2 = (p2.x - center1.x).powi(2) + (p2.y - center1.y).powi(2);
619
620                if dist2 < r2_1 - 1e-10 {
621                    // Flip edge
622                    let new_t1 = Triangle::new(edge[0], opp1, opp2);
623                    let new_t2 = Triangle::new(edge[1], opp2, opp1);
624                    triangles[adj_tris[0]] = new_t1;
625                    triangles[adj_tris[1]] = new_t2;
626                    changed = true;
627                }
628            }
629        }
630    }
631}
632
633#[cfg(test)]
634mod tests {
635    use super::*;
636    use crate::geometry::{Point, Polygon};
637
638    #[test]
639    fn ear_clipping_triangle() {
640        let poly = Polygon::new(vec![
641            Point::new(0.0, 0.0),
642            Point::new(1.0, 0.0),
643            Point::new(0.0, 1.0),
644        ]);
645        let tris = triangulate_polygon_ear_clipping(&poly);
646        assert_eq!(tris.len(), 1);
647    }
648
649    #[test]
650    fn ear_clipping_square() {
651        let poly = Polygon::new(vec![
652            Point::new(0.0, 0.0),
653            Point::new(1.0, 0.0),
654            Point::new(1.0, 1.0),
655            Point::new(0.0, 1.0),
656        ]);
657        let tris = triangulate_polygon_ear_clipping(&poly);
658        assert_eq!(tris.len(), 2);
659    }
660
661    #[test]
662    fn ear_clipping_pentagon() {
663        let poly = Polygon::new(vec![
664            Point::new(0.0, 0.0),
665            Point::new(2.0, 0.0),
666            Point::new(2.0, 1.0),
667            Point::new(1.0, 2.0),
668            Point::new(0.0, 1.0),
669        ]);
670        let tris = triangulate_polygon_ear_clipping(&poly);
671        assert_eq!(tris.len(), 3);
672    }
673
674    #[test]
675    fn delaunay_simple() {
676        let points = vec![
677            Point::new(0.0, 0.0),
678            Point::new(1.0, 0.0),
679            Point::new(0.0, 1.0),
680            Point::new(1.0, 1.0),
681        ];
682        let tris = triangulate_delaunay(&points);
683        assert_eq!(tris.len(), 2);
684    }
685
686    #[test]
687    fn triangle_contains_point() {
688        let points = vec![
689            Point::new(0.0, 0.0),
690            Point::new(1.0, 0.0),
691            Point::new(0.0, 1.0),
692        ];
693        let tri = Triangle::new(0, 1, 2);
694        assert!(tri.contains_point(&points, Point::new(0.25, 0.25)));
695        assert!(!tri.contains_point(&points, Point::new(0.75, 0.75)));
696    }
697
698    #[test]
699    fn triangle_circumcircle() {
700        let points = vec![
701            Point::new(0.0, 0.0),
702            Point::new(1.0, 0.0),
703            Point::new(0.0, 1.0),
704        ];
705        let tri = Triangle::new(0, 1, 2);
706        let (center, r2) = tri.circumcircle(&points);
707        assert!((center.x - 0.5).abs() < 1e-6);
708        assert!((center.y - 0.5).abs() < 1e-6);
709        assert!((r2 - 0.5).abs() < 1e-6);
710    }
711}
712
713/// Mesh density control for automated sizing based on section bounding box.
714#[derive(Debug, Clone, Copy, PartialEq)]
715pub enum MeshControl {
716    /// Coarse mesh: target_size = max_dim / 4
717    Coarse,
718    /// Normal mesh: target_size = max_dim / 6 (default)
719    Normal,
720    /// Fine mesh: target_size = max_dim / 10
721    Fine,
722    /// Very fine mesh: target_size = max_dim / 20
723    VeryFine,
724    /// Custom target size (absolute value, not relative to max_dim)
725    Custom(f64),
726}
727
728impl Default for MeshControl {
729    fn default() -> Self {
730        MeshControl::Normal
731    }
732}
733
734impl MeshControl {
735    /// Compute target_size from section bounding box diagonal.
736    pub fn compute_target_size(self, max_dim: f64) -> f64 {
737        match self {
738            MeshControl::Coarse => max_dim / 4.0,
739            MeshControl::Normal => max_dim / 6.0,
740            MeshControl::Fine => max_dim / 10.0,
741            MeshControl::VeryFine => max_dim / 20.0,
742            MeshControl::Custom(size) => size,
743        }
744    }
745
746    /// Compute target_size with thin-walled adjustment.
747    pub fn compute_target_size_thin_walled(self, max_dim: f64, min_edge: f64) -> f64 {
748        let base = self.compute_target_size(max_dim);
749        match self {
750            MeshControl::Coarse | MeshControl::Normal => {
751                // For thin-walled sections:
752                // - Floor at max_dim/20 to prevent overly fine mesh
753                // - Ceiling at min_edge/2 to resolve wall thickness
754                // - The .min(min_edge/2.0) CAN go below max_dim/20 if min_edge is very small,
755                //   which is intended for very thin walls — but a tiny discretisation edge
756                //   (e.g. a root-radius arc segment) must not blow the mesh up, so never go
757                //   finer than max_dim/40.
758                base.max(max_dim / 20.0)
759                    .min(min_edge / 2.0)
760                    .max(max_dim / 40.0)
761            }
762            MeshControl::Fine | MeshControl::VeryFine => {
763                // For fine meshes, use min edge length but cap at base
764                (min_edge / 2.0).min(base).max(max_dim / 50.0)
765            }
766            MeshControl::Custom(_) => base,
767        }
768    }
769}
770
771/// Create MeshParams from MeshControl and section dimensions.
772pub fn mesh_params_from_control(
773    control: MeshControl,
774    max_dim: f64,
775    min_edge: f64,
776    is_thin_walled: bool,
777) -> crate::mesh::MeshParams {
778    let target_size = if is_thin_walled {
779        control.compute_target_size_thin_walled(max_dim, min_edge)
780    } else {
781        control.compute_target_size(max_dim)
782    };
783    crate::mesh::MeshParams {
784        target_size,
785        max_size: target_size * 2.0,
786        min_size: target_size * 0.3,
787        quality_threshold: 0.3,
788        use_delaunay: true,
789        // Limit uniform-refinement passes for thin-walled sections. Uniform
790        // red-refinement quadruples the element count per pass (42 -> 168 ->
791        // 672 -> 2688 -> 10752 ...) with no intermediate sizes, so the default
792        // 10 passes over-shoots to a huge mesh whose skyline factor is
793        // impractically slow on long/narrow thin-walled sections. A small
794        // iteration cap keeps the mesh moderate while still resolving the wall.
795        max_iterations: if is_thin_walled { 3 } else { 10 },
796        max_nodes: 20000,
797    }
798}