188 lines
6.4 KiB
Rust
188 lines
6.4 KiB
Rust
//! Polygon triangulation with holes: holes are bridged into the outer contour (each hole's
|
|
//! rightmost vertex joined to a visible outer vertex), then ears are clipped.
|
|
|
|
type P = [f64; 2];
|
|
|
|
/// Twice the signed area (positive = counter-clockwise in a Y-up frame).
|
|
pub fn signed_area(c: &[P]) -> f64 {
|
|
let n = c.len();
|
|
(0..n)
|
|
.map(|i| {
|
|
let (a, b) = (c[i], c[(i + 1) % n]);
|
|
a[0] * b[1] - b[0] * a[1]
|
|
})
|
|
.sum()
|
|
}
|
|
|
|
#[inline]
|
|
fn cross(o: P, a: P, b: P) -> f64 {
|
|
(a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
|
|
}
|
|
|
|
fn in_triangle(p: P, a: P, b: P, c: P) -> bool {
|
|
let d1 = cross(a, b, p);
|
|
let d2 = cross(b, c, p);
|
|
let d3 = cross(c, a, p);
|
|
d1 >= 0.0 && d2 >= 0.0 && d3 >= 0.0
|
|
}
|
|
|
|
/// Triangulate an outer contour with holes. Contours are closed polylines (last point not
|
|
/// repeated); orientation is normalised internally. Returns triangles as indices into the
|
|
/// contours concatenated in order (`outer`, then `holes`), counter-clockwise (Y up).
|
|
pub fn triangulate(outer: &[P], holes: &[Vec<P>]) -> Vec<[usize; 3]> {
|
|
if outer.len() < 3 {
|
|
return vec![];
|
|
}
|
|
let mut pts: Vec<P> = outer.to_vec();
|
|
for h in holes {
|
|
pts.extend_from_slice(h);
|
|
}
|
|
// Ring of global indices, outer counter-clockwise.
|
|
let mut ring: Vec<usize> = (0..outer.len()).collect();
|
|
if signed_area(outer) < 0.0 {
|
|
ring.reverse();
|
|
}
|
|
// Holes clockwise, rightmost first.
|
|
let mut hs: Vec<Vec<usize>> = vec![];
|
|
let mut off = outer.len();
|
|
for h in holes {
|
|
let mut r: Vec<usize> = (off..off + h.len()).collect();
|
|
off += h.len();
|
|
if h.len() < 3 {
|
|
continue;
|
|
}
|
|
if signed_area(h) > 0.0 {
|
|
r.reverse();
|
|
}
|
|
hs.push(r);
|
|
}
|
|
hs.sort_by(|a, b| {
|
|
let mx = |r: &Vec<usize>| r.iter().map(|&i| pts[i][0]).fold(f64::NEG_INFINITY, f64::max);
|
|
mx(b).total_cmp(&mx(a))
|
|
});
|
|
for h in hs {
|
|
bridge(&pts, &mut ring, &h);
|
|
}
|
|
ear_clip(&pts, ring)
|
|
}
|
|
|
|
/// Join hole `h` into `ring` through a bridge from the hole's rightmost vertex.
|
|
fn bridge(pts: &[P], ring: &mut Vec<usize>, h: &[usize]) {
|
|
let (hk, &m) = h.iter().enumerate().max_by(|a, b| pts[*a.1][0].total_cmp(&pts[*b.1][0])).unwrap_or((0, &h[0]));
|
|
let mp = pts[m];
|
|
// Nearest ring edge hit by the ray +x from M.
|
|
let n = ring.len();
|
|
let mut best: Option<(f64, usize)> = None;
|
|
for i in 0..n {
|
|
let (a, b) = (pts[ring[i]], pts[ring[(i + 1) % n]]);
|
|
if (a[1] > mp[1]) == (b[1] > mp[1]) && a[1] != mp[1] && b[1] != mp[1] {
|
|
continue;
|
|
}
|
|
if a[1] == b[1] {
|
|
continue;
|
|
}
|
|
let t = (mp[1] - a[1]) / (b[1] - a[1]);
|
|
if !(0.0..=1.0).contains(&t) {
|
|
continue;
|
|
}
|
|
let x = a[0] + t * (b[0] - a[0]);
|
|
if x >= mp[0] && best.is_none_or(|(bx, _)| x < bx) {
|
|
best = Some((x, i));
|
|
}
|
|
}
|
|
let Some((x, i)) = best else { return };
|
|
let (a, b) = (ring[i], ring[(i + 1) % n]);
|
|
// Candidate: the edge endpoint with the larger x.
|
|
let mut cand = if pts[a][0] > pts[b][0] { (i, a) } else { ((i + 1) % n, b) };
|
|
let ip = [x, mp[1]];
|
|
// Reflex ring vertices inside triangle (M, I, P) block the view: take the one with the
|
|
// smallest angle to the ray (closest on ties).
|
|
let pp = pts[cand.1];
|
|
let (t0, t1, t2) = if cross(mp, ip, pp) >= 0.0 { (mp, ip, pp) } else { (mp, pp, ip) };
|
|
let mut best_ang = f64::INFINITY;
|
|
for k in 0..n {
|
|
let v = ring[k];
|
|
if v == cand.1 {
|
|
continue;
|
|
}
|
|
let q = pts[v];
|
|
let prev = pts[ring[(k + n - 1) % n]];
|
|
let next = pts[ring[(k + 1) % n]];
|
|
let reflex = cross(prev, q, next) <= 0.0;
|
|
if reflex && in_triangle(q, t0, t1, t2) {
|
|
let ang = (q[1] - mp[1]).abs().atan2(q[0] - mp[0]);
|
|
let d = (q[0] - mp[0]).hypot(q[1] - mp[1]);
|
|
let cd = (pts[cand.1][0] - mp[0]).hypot(pts[cand.1][1] - mp[1]);
|
|
if ang < best_ang || (ang == best_ang && d < cd) {
|
|
best_ang = ang;
|
|
cand = (k, v);
|
|
}
|
|
}
|
|
}
|
|
let (k, _) = cand;
|
|
// ring[..=k], hole from M around back to M, ring[k] again, rest.
|
|
let mut out = Vec::with_capacity(ring.len() + h.len() + 2);
|
|
out.extend_from_slice(&ring[..=k]);
|
|
for j in 0..=h.len() {
|
|
out.push(h[(hk + j) % h.len()]);
|
|
}
|
|
out.extend_from_slice(&ring[k..]);
|
|
*ring = out;
|
|
}
|
|
|
|
fn ear_clip(pts: &[P], mut ring: Vec<usize>) -> Vec<[usize; 3]> {
|
|
let mut tris = vec![];
|
|
let mut guard = 0usize;
|
|
let mut i = 0usize;
|
|
while ring.len() > 3 {
|
|
let n = ring.len();
|
|
if guard > 2 * n {
|
|
// No ear found (degenerate/self-intersecting input): clip anyway to finish.
|
|
let (a, b, c) = (ring[(i + n - 1) % n], ring[i % n], ring[(i + 1) % n]);
|
|
tris.push([a, b, c]);
|
|
ring.remove(i % n);
|
|
guard = 0;
|
|
continue;
|
|
}
|
|
let ii = i % n;
|
|
let (a, b, c) = (ring[(ii + n - 1) % n], ring[ii], ring[(ii + 1) % n]);
|
|
let (pa, pb, pc) = (pts[a], pts[b], pts[c]);
|
|
let cr = cross(pa, pb, pc);
|
|
let scale = 1.0 + pa[0].abs() + pa[1].abs() + pc[0].abs() + pc[1].abs();
|
|
// A straight-through vertex is clipped as a zero-area triangle (keeps every contour edge
|
|
// in the triangulation, so caps meet walls without T-junctions).
|
|
let straight = cr.abs() <= 1e-12 * scale * scale && (pa[0] - pb[0]) * (pc[0] - pb[0]) + (pa[1] - pb[1]) * (pc[1] - pb[1]) <= 0.0;
|
|
let convex = cr > 0.0 && !straight;
|
|
let mut ear = convex || straight;
|
|
if convex {
|
|
for &v in &ring {
|
|
if v == a || v == b || v == c {
|
|
continue;
|
|
}
|
|
let q = pts[v];
|
|
// Bridged duplicates share positions with the ear's corners.
|
|
if q == pa || q == pb || q == pc {
|
|
continue;
|
|
}
|
|
if in_triangle(q, pa, pb, pc) {
|
|
ear = false;
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
if ear {
|
|
tris.push([a, b, c]);
|
|
ring.remove(ii);
|
|
guard = 0;
|
|
i = if ii == 0 { 0 } else { ii - 1 };
|
|
} else {
|
|
i = ii + 1;
|
|
guard += 1;
|
|
}
|
|
}
|
|
if ring.len() == 3 {
|
|
tris.push([ring[0], ring[1], ring[2]]);
|
|
}
|
|
tris
|
|
}
|