use crate::{util, Point};
use ncollide2d::{
bounding_volume::AABB,
math::Isometry,
query::{proximity, Proximity},
shape::{Polyline, Segment},
};
use std::{cmp, cmp::Ordering, fmt};
mod cell_grid;
pub use cell_grid::CellGrid;
#[derive(Debug, PartialEq, Hash, PartialOrd, Clone, Copy)]
pub struct Cell {
pub x: i32,
pub y: i32,
}
impl fmt::Display for Cell {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "({},{})", self.x, self.y)
}
}
impl Eq for Cell {}
impl Ord for Cell {
fn cmp(&self, other: &Self) -> Ordering {
self.y.cmp(&other.y).then(self.x.cmp(&other.x))
}
}
macro_rules! cell_grid {
($($a:ident),*) => {
$(pub fn $a(&self) -> Point {
self.top_left_most() + CellGrid::$a()
})*
}
}
impl Cell {
cell_grid!(
a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y
);
pub fn new(x: i32, y: i32) -> Self {
Cell { x, y }
}
pub fn is_adjacent(&self, other: &Self) -> bool {
(other.x - self.x).abs() <= 1 && (other.y - self.y).abs() <= 1
}
pub fn snap_point(point: Point) -> (Self, Point) {
let x = (point.x / Self::width()).floor();
let y = (point.y / Self::height()).floor();
let cell = Self::new(x as i32, y as i32);
let snap = Self::snap(cell.localize_point(point));
(cell, snap)
}
pub fn snap_group(points: &[Point]) -> Self {
let snaps: Vec<(Self, Point)> = points
.iter()
.map(|point| Self::snap_point(*point))
.collect();
let (cells, _snap_points): (Vec<Self>, Vec<Point>) = snaps.into_iter().unzip();
let min_cell: Self = cells.into_iter().min().expect("should have a min cell");
min_cell
}
pub(in crate) fn absolute_position(&self, point: Point) -> Point {
self.top_left_most() + point
}
pub fn top_left_most(&self) -> Point {
let px = self.x as f32 * CellGrid::width();
let py = self.y as f32 * CellGrid::height();
Point::new(px, py)
}
pub fn bottom_right_most(&self) -> Point {
let px = (self.x + 1) as f32 * CellGrid::width();
let py = (self.y + 1) as f32 * CellGrid::height();
Point::new(px, py)
}
pub fn localize_point(&self, point: Point) -> Point {
point - self.top_left_most()
}
pub fn localize_cell(&self, cell: Cell) -> Cell {
Cell::new(cell.x - self.x, cell.y - self.y)
}
#[inline]
fn bounding_box(&self) -> AABB<f32> {
let start = Point::new(
self.x as f32 * Self::width(),
self.y as f32 * Self::height(),
);
let end = Point::new(
(self.x + 1) as f32 * Self::width(),
(self.y + 1) as f32 * Self::height(),
);
AABB::new(*start, *end)
}
fn polyline(&self) -> Polyline<f32> {
let aabb = self.bounding_box();
let min = aabb.mins();
let max = aabb.maxs();
let x1 = min.x;
let y1 = min.y;
let x2 = max.x;
let y2 = max.y;
let c1 = Point::new(x1, y1);
let c2 = Point::new(x2, y1);
let c3 = Point::new(x2, y2);
let c4 = Point::new(x1, y2);
Polyline::new(vec![*c1, *c2, *c3, *c4, *c1], None)
}
pub fn width() -> f32 {
CellGrid::width()
}
pub fn height() -> f32 {
CellGrid::height()
}
pub fn unit(l: i32) -> f32 {
CellGrid::unit_x() * l as f32
}
pub fn is_intersected(&self, start: Point, end: Point) -> bool {
let pl = self.polyline();
let segment = Segment::new(*start, *end);
let prox = proximity(
&Isometry::identity(),
&pl,
&Isometry::identity(),
&segment,
0.0,
);
prox == Proximity::Intersecting
}
pub fn is_bounded(&self, bound1: Cell, bound2: Cell) -> bool {
let (lower_bound, upper_bound) = rearrange_bound(bound1, bound2);
self.x >= lower_bound.x
&& self.y >= lower_bound.y
&& self.x <= upper_bound.x
&& self.y <= upper_bound.y
}
#[inline]
fn snap_xy(x: f32, y: f32) -> Point {
let tx = (x * 4.0).round() / 4.0;
let ty = (y * 8.0).round() / 8.0;
Point::new(tx, ty)
}
#[inline]
pub fn snap(p: Point) -> Point {
Self::snap_xy(p.x, p.y)
}
fn clip_line(&self, start: Point, end: Point) -> Option<(Point, Point)> {
let aabb = self.bounding_box();
util::clip_line(&aabb, start, end)
}
pub fn clip_line_snap(&self, start: Point, end: Point) -> Option<(Point, Point)> {
self.clip_line(start, end)
.map(|(s, e)| (Self::snap(s), Self::snap(e)))
}
pub fn clip_line_localize(&self, start: Point, end: Point) -> Option<(Point, Point)> {
self.clip_line_snap(start, end)
.map(|(s, e)| (self.localize_point(s), self.localize_point(e)))
}
#[inline]
pub fn top_left(&self) -> Self {
Cell {
x: self.x - 1,
y: self.y - 1,
}
}
#[inline]
pub fn top(&self) -> Self {
Cell {
x: self.x,
y: self.y - 1,
}
}
#[inline]
pub fn top_right(&self) -> Self {
Cell {
x: self.x + 1,
y: self.y - 1,
}
}
#[inline]
pub fn left(&self) -> Self {
Cell {
x: self.x - 1,
y: self.y,
}
}
#[inline]
pub fn right(&self) -> Self {
Cell {
x: self.x + 1,
y: self.y,
}
}
#[inline]
pub fn bottom_left(&self) -> Self {
Cell {
x: self.x - 1,
y: self.y + 1,
}
}
#[inline]
pub fn bottom(&self) -> Self {
Cell {
x: self.x,
y: self.y + 1,
}
}
#[inline]
pub fn bottom_right(&self) -> Self {
Cell {
x: self.x + 1,
y: self.y + 1,
}
}
}
pub fn rearrange_bound(bound1: Cell, bound2: Cell) -> (Cell, Cell) {
let min_x = cmp::min(bound1.x, bound2.x);
let min_y = cmp::min(bound1.y, bound2.y);
let max_x = cmp::max(bound1.x, bound2.x);
let max_y = cmp::max(bound1.y, bound2.y);
(Cell::new(min_x, min_y), Cell::new(max_x, max_y))
}
#[cfg(test)]
mod tests {
use super::*;
extern crate test;
use test::{black_box, Bencher};
#[bench]
fn bench_adjacent(bencher: &mut Bencher) {
bencher.iter(|| {
for i in 0..1000 {
for j in 0..1000 {
let cell1 = Cell::new(i, j);
let cell2 = Cell::new(i + 1, j + 1);
black_box(cell1.is_adjacent(&cell2));
}
}
})
}
#[test]
fn test_bottom_right() {
let cell = Cell::new(2, 0);
assert_eq!(cell.bottom_right(), Cell::new(3, 1));
}
#[test]
fn test_adjacent() {
let cell = Cell::new(4, 4);
let top = Cell::new(4, 3);
let top2 = Cell::new(4, 2);
assert!(cell.is_adjacent(&top));
assert!(top.is_adjacent(&cell));
assert!(cell.is_adjacent(&cell.top_left()));
assert!(cell.is_adjacent(&cell.top()));
assert!(cell.is_adjacent(&cell.top_right()));
assert!(cell.is_adjacent(&cell.left()));
assert!(cell.is_adjacent(&cell.right()));
assert!(cell.is_adjacent(&cell.bottom_left()));
assert!(cell.is_adjacent(&cell.bottom()));
assert!(cell.is_adjacent(&cell.bottom_right()));
assert!(!cell.is_adjacent(&top2));
assert!(!cell.is_adjacent(&cell.top_left().top()));
assert!(cell.is_adjacent(&cell.top().left()));
assert!(!cell.is_adjacent(&cell.top_right().right()));
assert!(!cell.is_adjacent(&cell.left().left()));
assert!(!cell.is_adjacent(&cell.right().right()));
assert!(!cell.is_adjacent(&cell.bottom_left().bottom_left()));
assert!(!cell.is_adjacent(&cell.bottom().bottom_right()));
assert!(!cell.is_adjacent(&cell.bottom_right().right()));
}
#[test]
fn test_location() {
let cell = Cell::new(5, 5);
assert_eq!(cell.left(), Cell::new(4, 5));
assert_eq!(cell.right(), Cell::new(6, 5));
assert_eq!(cell.top(), Cell::new(5, 4));
assert_eq!(cell.bottom(), Cell::new(5, 6));
assert_eq!(cell.top_left(), Cell::new(4, 4));
assert_eq!(cell.top_right(), Cell::new(6, 4));
assert_eq!(cell.bottom_left(), Cell::new(4, 6));
assert_eq!(cell.bottom_right(), Cell::new(6, 6));
}
#[test]
fn cell_from_snap_group_point() {
let p1 = Point::new(11.0, 11.0);
let p2 = Point::new(10.0, 11.0);
let (cell1, snap1) = Cell::snap_point(p1);
assert_eq!(Cell::new(11, 5), cell1);
assert_eq!(snap1, Point::new(0.0, 1.0));
let (cell2, _snap2) = Cell::snap_point(p2);
assert_eq!(Cell::new(10, 5), cell2);
let cell_group = Cell::snap_group(&[p1, p2]);
assert_eq!(Cell::new(10, 5), cell_group);
let local1 = cell_group.localize_point(p1);
let local2 = cell_group.localize_point(p2);
println!("local1: {:#?}", local1);
println!("local2: {:#?}", local2);
assert_eq!(local1, Point::new(1.0, 1.0));
assert_eq!(local2, Point::new(0.0, 1.0));
}
#[test]
fn cell_from_point() {
let (cell, snap) = Cell::snap_point(Point::new(10.0, 11.0));
assert_eq!(Cell::new(10, 5), cell);
assert_eq!(snap, Point::new(0.0, 1.0));
}
#[test]
fn test_localize() {
let cell = Cell::new(3, 2);
let m = cell.m();
assert_eq!(m, Point::new(3.5, 5.0));
let local_m = cell.localize_point(m);
assert_eq!(local_m, Point::new(0.5, 1.0));
}
#[test]
fn test_locations() {
assert_eq!(Cell::new(0, 0).top_left_most(), Point::new(0.0, 0.0));
assert_eq!(Cell::new(0, 0).a(), Point::new(0.0, 0.0));
assert_eq!(Cell::new(0, 0).y(), Point::new(1.0, 2.0));
assert_eq!(Cell::new(1, 0).y(), Point::new(2.0, 2.0));
assert_eq!(Cell::new(1, 1).m(), Point::new(1.5, 3.0));
assert_eq!(Cell::new(9, 9).o(), Point::new(10.0, 19.0));
}
#[test]
fn text_proximity() {
assert_eq!(Cell::snap_xy(0.1, 0.05), CellGrid::a());
assert_eq!(Cell::snap_xy(1.1, 2.05), CellGrid::y());
}
#[test]
fn test_aabb() {
assert_eq!(
AABB::new(*Point::new(0.0, 0.0), *Point::new(1.0, 2.0)),
Cell::new(0, 0).bounding_box()
);
}
#[test]
fn test_clip_line() {
assert_eq!(
Cell::new(0, 0).clip_line_snap(Point::new(-0.01, -0.01), Point::new(1.01, 2.01)),
Some((CellGrid::a(), CellGrid::y()))
);
assert_eq!(
Cell::new(0, 0).clip_line_snap(Point::new(0.0, 0.0), Point::new(1.00, 0.0)),
Some((CellGrid::a(), CellGrid::e()))
);
let clipped = Cell::new(0, 0).clip_line_snap(Point::new(0.0, 1.0), Point::new(1.0, 1.0));
assert_eq!(clipped, Some((CellGrid::k(), CellGrid::o())));
let clipped =
Cell::new(0, 0).clip_line_snap(Point::new(-0.01, 1.01), Point::new(1.01, 0.95));
assert_eq!(clipped, Some((CellGrid::k(), CellGrid::o())));
assert_eq!(
Cell::new(0, 0).clip_line_snap(Point::new(0.0, 2.0), Point::new(1.0, 2.0)),
Some((CellGrid::u(), CellGrid::y()))
);
assert_eq!(
Cell::new(0, 0).clip_line_snap(Point::new(0.0, 0.0), Point::new(0.0, 2.0)),
Some((CellGrid::a(), CellGrid::u()))
);
assert_eq!(
Cell::new(0, 0).clip_line_snap(Point::new(1.0, 0.0), Point::new(1.0, 2.0)),
Some((CellGrid::e(), CellGrid::y()))
);
assert_eq!(
Cell::new(0, 0).clip_line_snap(Point::new(1.0, 0.0), Point::new(0.0, 0.0)),
Some((CellGrid::e(), CellGrid::a()))
);
assert_eq!(
Cell::new(0, 0).clip_line_snap(Point::new(0.5, 1.0), Point::new(1.0, 1.0)),
Some((CellGrid::m(), CellGrid::o()))
);
assert_eq!(
Cell::new(0, 0).clip_line_snap(Point::new(0.25, 1.0), Point::new(1.0, 1.0)),
Some((CellGrid::l(), CellGrid::o()))
);
}
}