use std::ops::Range;
use crate::coord::Coord;
#[derive(Debug, Clone, Copy)]
pub struct Rect {
pub top: i32,
pub bottom: i32,
pub left: i32,
pub right: i32,
}
impl Rect {
pub fn new<C: Into<Coord>>(dimensions: C) -> Self {
Self::with_corners((0, 0), dimensions)
}
pub fn with_corners<C1, C2>(corner1: C1, corner2: C2) -> Self
where
C1: Into<Coord>,
C2: Into<Coord>,
{
let corner1 = corner1.into();
let corner2 = corner2.into();
Self {
top: corner1.y.min(corner2.y),
bottom: corner1.y.max(corner2.y),
left: corner1.x.min(corner2.x),
right: corner1.x.max(corner2.x),
}
}
pub fn dimensions(&self) -> Coord {
Coord::new(self.width(), self.height())
}
pub fn offset(&self) -> Coord {
Coord::new(self.left, self.top)
}
pub fn area(&self) -> i32 {
self.width() * self.height()
}
pub fn width(&self) -> i32 {
self.right - self.left
}
pub fn height(&self) -> i32 {
self.bottom - self.top
}
pub fn partition_vertical(&self, partition: i32) -> (Self, Self) {
let absolute_partition = self.top + partition;
(
Self {
top: absolute_partition,
..*self
},
Self {
bottom: absolute_partition,
..*self
},
)
}
pub fn partition_horizontal(&self, partition: i32) -> (Self, Self) {
let absolute_partition = self.left + partition;
(
Self {
right: absolute_partition,
..*self
},
Self {
left: absolute_partition,
..*self
},
)
}
pub fn bsp(
&self,
orientation: Orientation,
splitter: &dyn Fn(Rect, Orientation) -> Option<(i32, Orientation)>,
) -> BspTree {
match splitter(*self, orientation) {
Some((partition, next_orientation)) => {
let (left_or_bottom, right_or_top) = match orientation {
Orientation::Horizontal => self.partition_horizontal(partition),
Orientation::Vertical => self.partition_vertical(partition),
};
BspTree::Node(
*self,
Box::new(left_or_bottom.bsp(next_orientation, splitter)),
Box::new(right_or_top.bsp(next_orientation, splitter)),
)
}
None => BspTree::Leaf(*self),
}
}
pub fn translate<C: Into<Coord>>(&self, coord: C) -> Self {
let coord = coord.into();
Self {
bottom: self.bottom + coord.y,
left: self.left + coord.x,
top: self.top + coord.y,
right: self.right + coord.x,
}
}
pub fn contains<C: Into<Coord>>(&self, coord: C) -> bool {
let coord = coord.into();
coord.x >= self.left && coord.x < self.right && coord.y >= self.top && coord.y < self.bottom
}
pub fn x_range(&self) -> Range<i32> {
self.left..self.right
}
pub fn y_range(&self) -> Range<i32> {
self.top..self.bottom
}
pub fn iter(&self) -> impl Iterator<Item = Coord> {
let next_coord = Coord::new(self.left, self.top);
RectIter {
rect: *self,
next_coord,
is_finished: false,
}
}
}
#[derive(Clone, Copy)]
pub enum Orientation {
Horizontal,
Vertical,
}
impl Orientation {
pub fn orthogonal(&self) -> Self {
match self {
Orientation::Horizontal => Orientation::Vertical,
Orientation::Vertical => Orientation::Horizontal,
}
}
}
#[derive(Debug)]
pub enum BspTree {
Node(Rect, Box<BspTree>, Box<BspTree>),
Leaf(Rect),
}
impl BspTree {
pub fn leaves(&self) -> Vec<Rect> {
match self {
BspTree::Node(_, left, right) => {
let mut leaves = left.leaves();
leaves.append(&mut right.leaves());
leaves
}
BspTree::Leaf(rect) => vec![*rect],
}
}
}
struct RectIter {
rect: Rect,
next_coord: Coord,
is_finished: bool,
}
impl Iterator for RectIter {
type Item = Coord;
fn next(&mut self) -> Option<Self::Item> {
if self.is_finished {
return None;
}
let next_coord = self.next_coord;
if self.next_coord.x < self.rect.right - 1 {
self.next_coord.x += 1;
} else if self.next_coord.y < self.rect.bottom - 1 {
self.next_coord.x = self.rect.left;
self.next_coord.y += 1;
} else {
self.is_finished = true;
}
Some(next_coord)
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn dimensions() {
let rect = Rect::new((3, 4));
assert_eq!(rect.width(), 3);
assert_eq!(rect.height(), 4);
}
#[test]
fn single_coord_rect_iter() {
let rect = Rect::new((0, 0));
assert_eq!(rect.iter().count(), 1);
}
#[test]
fn multi_coord_rect_iter() {
let rect = Rect::new((4, 4));
assert_eq!(rect.iter().count(), 16);
}
#[test]
fn reversed_coord_rect_iter() {
let rect = Rect::with_corners((3, 3), (-2, -2));
let coords = rect.iter().collect::<Vec<_>>();
assert_eq!(coords.first(), Some(&Coord::new(-2, -2)));
assert_eq!(coords.last(), Some(&Coord::new(2, 2)));
}
#[test]
fn vertical_partitioning() {
let rect = Rect::new((8, 8));
let (top, bottom) = rect.partition_vertical(4);
assert_eq!(top.area(), 32);
assert_eq!(bottom.area(), 32);
}
#[test]
fn vertical_zero_partitioning() {
let rect = Rect::new((8, 8));
let (bottom, top) = rect.partition_vertical(0);
assert_eq!(top.area(), 0);
assert_eq!(bottom.area(), 64);
}
#[test]
fn horizontal_partitioning() {
let rect = Rect::new((8, 8));
let (left, right) = rect.partition_horizontal(4);
assert_eq!(left.area(), 32);
assert_eq!(right.area(), 32);
}
#[test]
fn horizontal_zero_partitioning() {
let rect = Rect::new((8, 8));
let (left, right) = rect.partition_horizontal(0);
assert_eq!(left.area(), 0);
assert_eq!(right.area(), 64);
}
#[test]
fn equally_subdivided_bsp() {
let rect = Rect::new((16, 16));
let min_size = 4;
let bsp_leaves = rect
.bsp(Orientation::Horizontal, &|rect, orientation| {
let partition = match orientation {
Orientation::Horizontal => rect.width() / 2,
Orientation::Vertical => rect.height() / 2,
};
if partition < min_size {
return None;
}
Some((partition, orientation.orthogonal()))
})
.leaves();
assert_eq!(bsp_leaves.len(), 16);
assert!(bsp_leaves.iter().all(|rect| rect.area() == 16));
}
}