use super::predicates::{coplanar, orient2d};
use super::{cross, dot, normalize, sub, V3};
fn signed_area2(t: &[[f64; 2]; 3]) -> f64 {
orient2d(t[0], t[1], t[2])
}
fn line_seg_x(a: [f64; 2], b: [f64; 2], p: [f64; 2], q: [f64; 2]) -> [f64; 2] {
let d1 = orient2d(a, b, p);
let d2 = orient2d(a, b, q);
let t = d1 / (d1 - d2);
[p[0] + t * (q[0] - p[0]), p[1] + t * (q[1] - p[1])]
}
fn clip_by_edge(poly: &[[f64; 2]], a: [f64; 2], b: [f64; 2]) -> Vec<[f64; 2]> {
let n = poly.len();
let mut out = Vec::new();
if n == 0 {
return out;
}
let inside = |p: [f64; 2]| orient2d(a, b, p) >= 0.0;
for i in 0..n {
let cur = poly[i];
let prev = poly[(i + n - 1) % n];
let (cin, pin) = (inside(cur), inside(prev));
if cin {
if !pin {
out.push(line_seg_x(a, b, prev, cur));
}
out.push(cur);
} else if pin {
out.push(line_seg_x(a, b, prev, cur));
}
}
out
}
pub fn coplanar_overlap_poly(a: &[V3; 3], b: &[V3; 3]) -> Vec<V3> {
if !coplanar(a, b) {
return Vec::new();
}
let n = cross(sub(a[1], a[0]), sub(a[2], a[0]));
if dot(n, n) < 1e-18 {
return Vec::new();
}
let origin = a[0];
let ux = normalize(sub(a[1], a[0]));
let uy = normalize(cross(n, ux));
let to2 = |p: V3| [dot(sub(p, origin), ux), dot(sub(p, origin), uy)];
let a2 = [to2(a[0]), to2(a[1]), to2(a[2])];
let mut clip = [to2(b[0]), to2(b[1]), to2(b[2])];
if signed_area2(&clip) < 0.0 {
clip.reverse(); }
let mut poly: Vec<[f64; 2]> = a2.to_vec();
for e in 0..3 {
if poly.is_empty() {
break;
}
poly = clip_by_edge(&poly, clip[e], clip[(e + 1) % 3]);
}
if poly.len() < 3 {
return Vec::new();
}
poly.iter()
.map(|q| {
[
origin[0] + q[0] * ux[0] + q[1] * uy[0],
origin[1] + q[0] * ux[1] + q[1] * uy[1],
origin[2] + q[0] * ux[2] + q[1] * uy[2],
]
})
.collect()
}
pub fn coplanar_clip(a: &[V3; 3], b: &[V3; 3]) -> Vec<[V3; 3]> {
let poly = coplanar_overlap_poly(a, b);
if poly.len() < 3 {
return Vec::new();
}
let n = cross(sub(a[1], a[0]), sub(a[2], a[0]));
let mut out = Vec::new();
for i in 1..poly.len() - 1 {
let (p0, p1, p2) = (poly[0], poly[i], poly[i + 1]);
if dot(cross(sub(p1, p0), sub(p2, p0)), n) >= 0.0 {
out.push([p0, p1, p2]);
} else {
out.push([p0, p2, p1]);
}
}
out
}
#[cfg(test)]
mod tests {
use super::*;
fn area3(t: &[V3; 3]) -> f64 {
0.5 * {
let c = cross(sub(t[1], t[0]), sub(t[2], t[0]));
dot(c, c).sqrt()
}
}
fn total(ov: &[[V3; 3]]) -> f64 {
ov.iter().map(area3).sum()
}
#[test]
fn contained_overlap_is_the_inner_triangle() {
let a = [[0.0, 0.0, 0.0], [4.0, 0.0, 0.0], [0.0, 4.0, 0.0]]; let b = [[0.5, 0.5, 0.0], [1.5, 0.5, 0.0], [0.5, 1.5, 0.0]]; assert!((total(&coplanar_clip(&a, &b)) - 0.5).abs() < 1e-9);
}
#[test]
fn partial_overlap_area() {
let a = [[0.0, 0.0, 0.0], [2.0, 0.0, 0.0], [0.0, 2.0, 0.0]];
let b = [[0.0, 0.0, 0.0], [2.0, 0.0, 0.0], [2.0, 2.0, 0.0]];
assert!((total(&coplanar_clip(&a, &b)) - 1.0).abs() < 1e-9);
}
#[test]
fn disjoint_coplanar_is_empty() {
let a = [[0.0, 0.0, 0.0], [1.0, 0.0, 0.0], [0.0, 1.0, 0.0]];
let b = [[5.0, 5.0, 0.0], [6.0, 5.0, 0.0], [5.0, 6.0, 0.0]];
assert!(coplanar_clip(&a, &b).is_empty());
}
#[test]
fn non_coplanar_is_empty() {
let a = [[0.0, 0.0, 0.0], [2.0, 0.0, 0.0], [0.0, 2.0, 0.0]];
let b = [[0.5, 0.5, 0.0], [1.5, 0.5, 0.0], [0.5, 0.5, 1.0]]; assert!(coplanar_clip(&a, &b).is_empty());
}
}