use crate::common::kd_tree::{KdTreeSearch, PartialKdTree};
use crate::common::{IndexMask, PCoords, compute_first_per_voxel_mask};
pub fn sample_poisson_disk_all<const D: usize>(
points: &[impl PCoords<D>],
radius: f64,
) -> IndexMask {
let pre_mask = compute_first_per_voxel_mask(points, radius * 0.25);
let partial_tree = PartialKdTree::try_new(points, &pre_mask)
.expect("KD tree construction failed. Are there enough points?");
let mut skip_mask = pre_mask.clone();
let mut final_mask = IndexMask::new(points.len(), false);
for i in pre_mask.iter_true() {
if !skip_mask.get(i) {
continue;
}
final_mask.set(i, true);
let within = partial_tree.within(&points[i], radius);
for w in within {
skip_mask.set(w.0, false);
}
}
final_mask
}
#[cfg(test)]
mod tests {
use super::*;
use crate::Point2;
use crate::common::kd_tree::KdTree;
use crate::na::Point;
use rand;
use rand::RngExt;
#[test]
fn stress_test_poisson_disk() {
let n = 3000;
let mx = 10.0;
let r = 0.2;
for _ in 0..50 {
let points = random_points(n, mx);
let keep = sample_poisson_disk_all(&points, r);
let at_least = (mx * mx) / (r * r) * 0.25;
assert!(keep.len() > at_least as usize);
let kept = keep.clone_indices_of(&points).unwrap();
let tree = KdTree::try_new(&kept).expect("Tree construction failed");
for (i, &p) in kept.iter().enumerate() {
let within = tree.within(&p, r);
assert_eq!(within.len(), 1);
assert_eq!(within[0].0, i);
}
}
}
fn random_points(n: usize, mx: f64) -> Vec<Point<f64, 2>> {
let mut rng = rand::rng();
(0..n)
.map(|_| Point2::new(rng.random_range(0.0..mx), rng.random_range(0.0..mx)))
.collect()
}
}