use crate::error::{Error, Result};
use crate::filters::{estimate_normals, planarity_linearity, voxel_downsample_indices};
use crate::numeric::{arange, median, nanmedian, quantile};
use crate::trees::{fit_circle_ransac, RansacCircleParams};
use crate::Point;
#[derive(Debug, Clone)]
pub struct ButtressParams {
pub max_radius: f64,
pub slice_height: f64,
pub max_height: f64,
pub low: f64,
pub bins: usize,
pub max_circle_fit: f64,
pub min_ridges: usize,
pub bark_only: bool,
pub voxel: f64,
}
impl Default for ButtressParams {
fn default() -> Self {
ButtressParams { max_radius: 4.0, slice_height: 0.1, max_height: 6.0, low: 1.0, bins: 36, max_circle_fit: 0.55, min_ridges: 2, bark_only: true, voxel: 0.02 }
}
}
#[derive(Debug, Clone, PartialEq)]
pub struct Buttress {
pub buttressed: bool,
pub base_circle_fit: f64,
pub stem_circle_fit: f64,
pub stem_radius: f64,
pub ridges: usize,
pub ridge_share: f64,
pub spread: f64,
pub top: f64,
pub centre: [f64; 2],
}
pub fn count_ridges(persistence: &[f64], level: f64, dip: f64) -> usize {
let ridge: Vec<bool> = persistence.iter().map(|&v| v >= level).collect();
if !ridge.iter().any(|&r| r) {
return 0;
}
let Some(start) = ridge.iter().position(|&r| !r) else { return 1 };
let p: Vec<f64> = persistence[start..].iter().chain(&persistence[..start]).copied().collect();
let n = p.len();
let (mut count, mut i) = (0, 0);
while i < n {
if p[i] < level {
i += 1;
continue;
}
let mut j = i;
while j < n && p[j] >= level {
j += 1;
}
count += 1;
let (mut peak, mut low) = (p[i], p[i]);
for &v in &p[i + 1..j] {
if v > peak {
peak = v;
}
if v < low {
low = v;
}
if peak - low >= dip && v - low >= dip {
count += 1;
peak = v;
low = v;
}
}
i = j;
}
count
}
fn median_nan(v: &[f64]) -> f64 {
if v.iter().any(|x| x.is_nan()) {
f64::NAN
} else {
median(v)
}
}
pub fn detect_buttress(points: &[Point], heights: &[f64], base_xy: Option<[f64; 2]>, p: &ButtressParams) -> Result<Buttress> {
if heights.len() != points.len() {
return Err(Error::invalid("heights must have one value per point"));
}
if p.bins == 0 {
return Err(Error::invalid("bins must be positive"));
}
let (xyz, h_all): (Vec<Point>, Vec<f64>) = if p.voxel != 0.0 {
voxel_downsample_indices(points, p.voxel).into_iter().map(|i| (points[i], heights[i])).unzip()
} else {
(points.to_vec(), heights.to_vec())
};
let centre = match base_xy {
Some(c) => c,
None => {
let band = |lo: f64, hi: f64| -> Vec<usize> { (0..xyz.len()).filter(|&i| h_all[i] > lo && h_all[i] < hi).collect() };
let mut sel = band(2.5, 3.5);
if sel.len() < 50 {
sel = band(1.2, 1.8);
}
if sel.is_empty() {
sel = (0..xyz.len()).collect();
}
let col = |k: usize| median_nan(&sel.iter().map(|&i| xyz[i][k]).collect::<Vec<_>>());
[col(0), col(1)]
}
};
let (mut pts, mut h): (Vec<Point>, Vec<f64>) = xyz
.iter()
.zip(&h_all)
.filter(|(q, &hh)| (q[0] - centre[0]).hypot(q[1] - centre[1]) < p.max_radius && hh >= 0.0 && hh < p.max_height + p.slice_height)
.map(|(q, &hh)| (*q, hh))
.unzip();
if p.bark_only && pts.len() > 20 {
let (planarity, _) = planarity_linearity(&pts, 20);
let normals = estimate_normals(&pts, 20);
let bark: Vec<bool> = planarity.iter().zip(&normals).map(|(&pl, n)| pl >= 0.4 && n[2].abs() <= 0.5).collect();
let mut k = 0;
pts.retain(|_| {
k += 1;
bark[k - 1]
});
let mut k = 0;
h.retain(|_| {
k += 1;
bark[k - 1]
});
}
let z0s = arange(0.2, p.max_height, p.slice_height);
let mut radius = vec![f64::NAN; z0s.len()];
let mut fit = vec![f64::NAN; z0s.len()];
let mut slices: Vec<Vec<[f64; 2]>> = Vec::with_capacity(z0s.len());
for (k, &z0) in z0s.iter().enumerate() {
let s: Vec<[f64; 2]> = pts.iter().zip(&h).filter(|(_, &hh)| hh >= z0 && hh < z0 + p.slice_height).map(|(q, _)| [q[0], q[1]]).collect();
if s.len() >= 30 {
let rp = RansacCircleParams { threshold: 0.02, iterations: 200, max_radius: p.max_radius, seed: k as u64, ..Default::default() };
match fit_circle_ransac(&s, &rp) {
Ok((_, _, r, inl)) => {
radius[k] = r;
fit[k] = inl.iter().filter(|&&b| b).count() as f64 / inl.len() as f64;
}
Err(_) => fit[k] = 0.0,
}
}
slices.push(s);
}
let up: Vec<bool> = (0..z0s.len()).map(|k| z0s[k] >= 2.0 && fit[k].is_finite()).collect();
let round_up: Vec<bool> = (0..z0s.len()).map(|k| up[k] && fit[k] >= 0.5).collect();
let reference = if round_up.iter().filter(|&&b| b).count() >= 3 { &round_up } else { &up };
let pick = |v: &[f64], mask: &[bool]| -> f64 {
if mask.iter().any(|&b| b) {
nanmedian(v.iter().zip(mask).filter(|(_, &m)| m).map(|(x, _)| *x))
} else {
f64::NAN
}
};
let stem_r = pick(&radius, reference);
let stem_fit = pick(&fit, reference);
let base: Vec<bool> = (0..z0s.len()).map(|k| z0s[k] < p.low && fit[k].is_finite()).collect();
let base_fit = pick(&fit, &base);
let mut marks = 0usize;
let mut hits = vec![0usize; p.bins];
let mut spread = Vec::new();
for (&z0, s) in z0s.iter().zip(&slices) {
if z0 >= p.low || s.len() < 30 || !stem_r.is_finite() {
continue;
}
let d: Vec<[f64; 2]> = s.iter().map(|q| [q[0] - centre[0], q[1] - centre[1]]).collect();
let dist: Vec<f64> = d.iter().map(|v| v[0].hypot(v[1])).collect();
spread.push(quantile(&dist, 0.95));
let mut mk = vec![false; p.bins];
let reach = 1.4 * stem_r + 0.1;
for (v, &r) in d.iter().zip(&dist) {
if r > reach {
let b = ((v[1].atan2(v[0]) + std::f64::consts::PI) / (2.0 * std::f64::consts::PI) * p.bins as f64) as usize % p.bins;
mk[b] = true;
}
}
for (c, m) in hits.iter_mut().zip(mk) {
*c += m as usize;
}
marks += 1;
}
let persistence: Vec<f64> = if marks > 0 { hits.iter().map(|&c| c as f64 / marks as f64).collect() } else { vec![0.0; p.bins] };
let ridges = count_ridges(&persistence, 0.6, 0.2);
let buttressed = base_fit.is_finite() && base_fit < p.max_circle_fit && ridges >= p.min_ridges;
let mut top = f64::NAN;
if buttressed && stem_fit.is_finite() {
let need = (0.8 * stem_fit).min(stem_fit - 0.1);
let good: Vec<bool> = fit.iter().map(|&f| f.is_finite() && f >= need).collect();
top = p.max_height;
for k in 0..z0s.len().saturating_sub(2) {
if z0s[k] >= p.low && good[k..k + 3].iter().all(|&g| g) {
top = z0s[k];
break;
}
}
}
let ridge_share = persistence.iter().filter(|&&v| v >= 0.6).count() as f64 / p.bins as f64;
let spread = if !spread.is_empty() && stem_r > 0.0 { median(&spread) / stem_r } else { f64::NAN };
Ok(Buttress { buttressed, base_circle_fit: base_fit, stem_circle_fit: stem_fit, stem_radius: stem_r, ridges, ridge_share, spread, top, centre })
}
#[cfg(test)]
mod tests {
use super::*;
use crate::filters::Rng;
#[test]
fn ridges_split_at_dips_and_wrap_around() {
assert_eq!(count_ridges(&[0.0; 36], 0.6, 0.2), 0);
assert_eq!(count_ridges(&[1.0; 36], 0.6, 0.2), 1);
assert_eq!(count_ridges(&[0.9, 0.9, 0.2, 0.9, 0.3, 0.8, 0.95, 0.7, 0.9], 0.6, 0.2), 3);
assert_eq!(count_ridges(&[0.1, 0.9, 0.65, 0.9, 0.1], 0.6, 0.2), 2);
}
fn base(flanges: bool) -> (Vec<Point>, Vec<f64>) {
let mut rng = Rng::new(3);
let mut uniform = || (rng.next_u64() >> 11) as f64 / (1u64 << 53) as f64;
let pts: Vec<Point> = (0..60_000)
.map(|_| {
let t = uniform() * std::f64::consts::TAU;
let h = uniform() * 6.0;
let f = if flanges { 3.0 * (1.0 - h / 2.0).max(0.0) * (2.5 * t).cos().powi(8) } else { 0.0 };
let r = 0.25 * (1.0 + f);
[r * t.cos(), r * t.sin(), h]
})
.collect();
let h = pts.iter().map(|q| q[2]).collect();
(pts, h)
}
#[test]
fn flanged_bases_are_buttressed_and_round_ones_are_not() {
let p = ButtressParams { bark_only: false, ..Default::default() };
let (pts, h) = base(true);
let b = detect_buttress(&pts, &h, Some([0.0, 0.0]), &p).unwrap();
assert!(b.buttressed && b.ridges >= 2, "{b:?}");
assert!((1.0..=2.6).contains(&b.top), "{b:?}");
let (pts, h) = base(false);
let b = detect_buttress(&pts, &h, None, &p).unwrap();
assert!(!b.buttressed && (b.stem_radius - 0.25).abs() < 0.03, "{b:?}");
assert!(b.top.is_nan());
}
}