use euclid::TypedPoint2D;
use num_traits::Num;
use partial_min_max::{max as partial_max, min as partial_min};
use std::fmt;
#[derive(Clone, PartialEq)]
pub struct Aabb<T, U = euclid::UnknownUnit> {
min: TypedPoint2D<T, U>,
max: TypedPoint2D<T, U>,
}
impl<T, U> fmt::Debug for Aabb<T, U>
where
T: fmt::Debug,
{
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
f.debug_struct("Aabb")
.field("min", &self.min)
.field("max", &self.max)
.finish()
}
}
impl<T, U> Aabb<T, U>
where
T: Copy + Num + PartialOrd,
{
#[inline]
pub fn new(min: TypedPoint2D<T, U>, max: TypedPoint2D<T, U>) -> Aabb<T, U> {
assert!(min.x <= max.x);
assert!(min.y <= max.y);
Aabb { min, max }
}
pub fn for_vertices<I>(vertices: I) -> Aabb<T, U>
where
I: IntoIterator<Item = TypedPoint2D<T, U>>,
{
let mut vertices = vertices.into_iter();
let first = vertices
.next()
.expect("Must have at least one vertex to create a bounding box");
let mut min = first;
let mut max = first;
for v in vertices {
min.x = partial_min(min.x, v.x);
min.y = partial_min(min.y, v.y);
max.x = partial_max(max.x, v.x);
max.y = partial_max(max.y, v.y);
}
Aabb::new(min, max)
}
#[inline]
pub fn min(&self) -> TypedPoint2D<T, U> {
self.min
}
#[inline]
pub fn max(&self) -> TypedPoint2D<T, U> {
self.max
}
#[inline]
pub fn width(&self)-> T {
self.max.x - self.min.x
}
#[inline]
pub fn height(&self)-> T {
self.max.y - self.min.y
}
#[inline]
pub fn area(&self) -> T {
(self.max.x - self.min.x) * (self.max.y - self.min.y)
}
#[inline]
pub fn join(&self, other: &Aabb<T, U>) -> Aabb<T, U> {
let min = TypedPoint2D::new(
partial_min(self.min.x, other.min.x),
partial_min(self.min.y, other.min.y),
);
let max = TypedPoint2D::new(
partial_max(self.max.x, other.max.x),
partial_max(self.max.y, other.max.y),
);
Aabb::new(min, max)
}
pub fn contains(&self, other: &Aabb<T, U>) -> bool {
other.min.x >= self.min.x
&& other.max.x <= self.max.x
&& other.min.y >= self.min.y
&& other.max.y <= self.max.y
}
pub fn intersects(&self, other: &Aabb<T, U>) -> bool {
self.max.x > other.min.x
&& self.min.x < other.max.x
&& self.max.y > other.min.y
&& self.min.y < other.max.y
}
}
#[derive(Debug)]
pub struct AabbTree<T, U, V> {
root: Option<AabbTreeNode<T, U, V>>,
}
#[derive(Debug)]
enum AabbTreeNode<T, U, V> {
Branch(AabbTreeBranch<T, U, V>),
Leaf(AabbTreeLeaf<T, U, V>),
}
#[derive(Debug)]
struct AabbTreeBranch<T, U, V> {
aabb: Aabb<T, U>,
children: Box<(AabbTreeNode<T, U, V>, AabbTreeNode<T, U, V>)>,
}
#[derive(Debug)]
struct AabbTreeLeaf<T, U, V> {
aabb: Aabb<T, U>,
value: V,
}
impl<T, U, V> AabbTree<T, U, V>
where
T: Copy + Num + PartialOrd,
{
#[inline]
pub fn new() -> AabbTree<T, U, V> {
AabbTree { root: None }
}
pub fn insert(&mut self, aabb: Aabb<T, U>, value: V) {
let leaf = AabbTreeLeaf { aabb, value };
self.root = Some(if let Some(r) = self.root.take() {
r.insert(leaf)
} else {
AabbTreeNode::Leaf(leaf)
});
}
pub fn iter_overlapping(&self, aabb: Aabb<T, U>) -> IterOverlapping<T, U, V> {
let stack = self
.root
.iter()
.filter(|n| n.aabb().intersects(&aabb))
.collect();
IterOverlapping { aabb, stack }
}
#[inline]
pub fn any_overlap(&self, aabb: Aabb<T, U>) -> bool {
self.iter_overlapping(aabb).next().is_some()
}
}
impl<T, U, V> AabbTreeNode<T, U, V>
where
T: Copy + Num + PartialOrd,
{
fn aabb(&self) -> &Aabb<T, U> {
match self {
AabbTreeNode::Leaf(l) => &l.aabb,
AabbTreeNode::Branch(b) => &b.aabb,
}
}
fn insert(self, leaf: AabbTreeLeaf<T, U, V>) -> AabbTreeNode<T, U, V> {
match self {
AabbTreeNode::Leaf(l) => AabbTreeNode::Branch(AabbTreeBranch {
aabb: l.aabb.join(&leaf.aabb),
children: Box::new((AabbTreeNode::Leaf(l), AabbTreeNode::Leaf(leaf))),
}),
AabbTreeNode::Branch(branch) => {
let combined_aabb = branch.aabb.join(&leaf.aabb);
let two = T::one() + T::one();
let new_parent_cost = two * combined_aabb.area();
let min_push_down_cost = two * (combined_aabb.area() - branch.aabb.area());
let left_cost = match branch.children.0 {
AabbTreeNode::Leaf(ref l) => {
l.aabb.join(&leaf.aabb).area() + min_push_down_cost
}
AabbTreeNode::Branch(ref b) => {
b.aabb.join(&leaf.aabb).area() - b.aabb.area() + min_push_down_cost
}
};
let right_cost = match branch.children.1 {
AabbTreeNode::Leaf(ref l) => {
l.aabb.join(&leaf.aabb).area() + min_push_down_cost
}
AabbTreeNode::Branch(ref b) => {
b.aabb.join(&leaf.aabb).area() - b.aabb.area() + min_push_down_cost
}
};
AabbTreeNode::Branch(AabbTreeBranch {
aabb: combined_aabb,
children: Box::new(
if new_parent_cost < left_cost && new_parent_cost < right_cost {
(AabbTreeNode::Leaf(leaf), AabbTreeNode::Branch(branch))
} else if left_cost < right_cost {
(branch.children.0.insert(leaf), branch.children.1)
} else {
(branch.children.0, branch.children.1.insert(leaf))
},
),
})
}
}
}
}
#[derive(Debug, Clone)]
pub struct IterOverlapping<'a, T, U, V> {
aabb: Aabb<T, U>,
stack: Vec<&'a AabbTreeNode<T, U, V>>,
}
impl<'a, T, U, V> Iterator for IterOverlapping<'a, T, U, V>
where
T: Copy + Num + PartialOrd,
{
type Item = (&'a Aabb<T, U>, &'a V);
fn next(&mut self) -> Option<Self::Item> {
loop {
match self.stack.pop() {
None => return None,
Some(AabbTreeNode::Leaf(l)) => {
debug_assert!(l.aabb.intersects(&self.aabb));
return Some((&l.aabb, &l.value));
}
Some(AabbTreeNode::Branch(b)) => {
if self.aabb.intersects(b.children.0.aabb()) {
self.stack.push(&b.children.0);
}
if self.aabb.intersects(b.children.1.aabb()) {
self.stack.push(&b.children.1);
}
}
}
}
}
}