use super::segment_cross;
use crate::common::barycentric::barycentric_within2;
use crate::geom2::Segment2;
use crate::geom2::hull::convex_hull_2d;
use crate::{Point2, Point3, Vector2};
fn inside_any(q: &Point2, faces: &[[Point2; 3]]) -> bool {
faces
.iter()
.any(|t| barycentric_within2(&t[0], &t[1], &t[2], q).is_some())
}
fn on_chain(q: &Point2, chain: &[Point2]) -> bool {
chain.windows(2).any(|s| {
let seg = Segment2::new_unchecked(s[0], s[1]);
(seg.closest_point(q) - q).norm() < 1.0e-9
})
}
pub(super) fn sliver_corners(
tri: &[Point2; 3],
other: &[[Point2; 3]],
chain: &[Point2],
) -> Vec<Point2> {
let mut out: Vec<Point2> = Vec::with_capacity(6);
let push = |out: &mut Vec<Point2>, q: Point2| {
if !out.iter().any(|z| (z - q).norm() < 1.0e-12) {
out.push(q);
}
};
for q in tri.iter() {
if !inside_any(q, other) || on_chain(q, chain) {
push(&mut out, *q);
}
}
for k in 0..3 {
let (u, v) = (tri[k], tri[(k + 1) % 3]);
for s in chain.windows(2) {
if let Some((t, _)) = segment_cross(&u, &v, &s[0], &s[1]) {
push(&mut out, Point2::from(u.coords * (1.0 - t) + v.coords * t));
}
}
}
for q in chain.iter().skip(1).take(chain.len().saturating_sub(2)) {
if barycentric_within2(&tri[0], &tri[1], &tri[2], q).is_some() {
push(&mut out, *q);
}
}
out
}
#[derive(Debug, Clone, Copy)]
pub(super) enum ChainFeature {
Segment(usize),
Vertex(usize),
}
pub(super) fn chain_pieces(
corners: &[Point2],
chain: &[Point2],
) -> Vec<(Vec<Point2>, ChainFeature)> {
let hull: Vec<Point2> = if corners.len() < 3 {
corners.to_vec()
} else {
convex_hull_2d(corners)
.into_iter()
.map(|i| corners[i])
.collect()
};
let dir = |k: usize| chain[k + 1] - chain[k];
let last = chain.len() - 1;
let mut out = Vec::with_capacity(2 * chain.len());
let mut cuts: Vec<(Point2, Vector2)> = Vec::with_capacity(2);
let clip = |cuts: &[(Point2, Vector2)]| -> Vec<Point2> {
cuts.iter()
.fold(hull.clone(), |poly, (c, n)| clip_half(&poly, c, n))
};
for k in 0..chain.len() {
if k < last {
cuts.clear();
cuts.push((chain[k], dir(k)));
cuts.push((chain[k + 1], -dir(k)));
let piece = clip(&cuts);
if !piece.is_empty() {
out.push((piece, ChainFeature::Segment(k)));
}
}
cuts.clear();
if k > 0 {
cuts.push((chain[k], dir(k - 1)));
}
if k < last {
cuts.push((chain[k], -dir(k)));
}
let piece = clip(&cuts);
if !piece.is_empty() {
out.push((piece, ChainFeature::Vertex(k)));
}
}
out
}
fn clip_half(poly: &[Point2], c: &Point2, n: &Vector2) -> Vec<Point2> {
let mut out = Vec::with_capacity(poly.len() + 1);
let side = |q: &Point2| (q - c).dot(n);
for i in 0..poly.len() {
let (a, b) = (poly[i], poly[(i + 1) % poly.len()]);
let (fa, fb) = (side(&a), side(&b));
if fa >= 0.0 {
out.push(a);
}
if (fa > 0.0 && fb < 0.0) || (fa < 0.0 && fb > 0.0) {
let t = fa / (fa - fb);
out.push(Point2::from(a.coords * (1.0 - t) + b.coords * t));
}
}
out
}
pub(super) struct Landing {
pub(super) at: Point3,
pub(super) coeff: f64,
pub(super) known: f64,
}
pub(super) fn chain_landing(
q: &Point2,
feature: ChainFeature,
chain2: &[Point2],
chain3: &[Point3],
radii: &[Option<f64>],
) -> Landing {
let blend = |k: usize, w: f64| -> (f64, f64) {
match radii[k] {
None => (w, 0.0),
Some(r) => (0.0, w * r),
}
};
match feature {
ChainFeature::Vertex(k) => {
let (coeff, known) = blend(k, 1.0);
Landing {
at: chain3[k],
coeff,
known,
}
}
ChainFeature::Segment(k) => {
let t = Segment2::new_unchecked(chain2[k], chain2[k + 1])
.scalar_projection(q)
.clamp(0.0, 1.0);
let (c0, c1) = blend(k, 1.0 - t);
let (d0, d1) = blend(k + 1, t);
Landing {
at: Point3::from(chain3[k].coords * (1.0 - t) + chain3[k + 1].coords * t),
coeff: c0 + d0,
known: c1 + d1,
}
}
}
}