#[macro_use]
extern crate serde_derive;
extern crate wasm_bindgen;
use std::collections::BTreeMap;
use std::ops::Range;
use wasm_bindgen::prelude::*;
pub trait Bounded<T> {
fn add(self, value: T) -> Range<T>;
}
impl<T: PartialOrd> Bounded<T> for Range<T> {
fn add(self, value: T) -> Range<T> {
if value < self.start {
Range {
start: value,
end: self.end,
}
} else if self.end < value {
Range {
start: self.start,
end: value,
}
} else {
self
}
}
}
#[derive(Serialize, Debug)]
pub struct Boundary {
pub x: i32,
pub y: Range<i32>,
}
impl PartialEq for Boundary {
fn eq(&self, other: &Boundary) -> bool {
(self.x == other.x) && (self.y == other.y)
}
}
fn bresenham_algorithm(x0: i32, y0: i32, radius: i32) -> BTreeMap<i32, Range<i32>> {
let mut points = BTreeMap::new();
let mut error = -radius;
let mut x = radius;
let mut y = 0;
while x >= y {
points = add_points(points, x0, y0, x, y);
error += y;
y += 1;
error += y;
if error >= 0 {
x -= 1;
error -= x;
error -= x;
}
}
points
}
fn add_points(
mut points: BTreeMap<i32, Range<i32>>,
x0: i32,
y0: i32,
x: i32,
y: i32,
) -> BTreeMap<i32, Range<i32>> {
let new_points = [
(x0 + x, y0 + y),
(x0 - x, y0 + y),
(x0 + x, y0 - y),
(x0 - x, y0 - y),
(x0 + y, y0 + x),
(x0 - y, y0 + x),
(x0 + y, y0 - x),
(x0 - y, y0 - x),
];
for (current_x, current_y) in &new_points {
let new_y = match points.get(current_x) {
Some(found_y) => found_y.clone().add(*current_y),
None => Range {
start: *current_y,
end: *current_y,
},
};
points.insert(*current_x, new_y);
}
points
}
pub fn calculate(x: i32, y: i32, radius: i32) -> Vec<Boundary> {
let boundaries = bresenham_algorithm(x, y, radius);
let mut circle_points = Vec::new();
for (x, range) in &boundaries {
circle_points.push(Boundary {
x: *x,
y: range.clone(),
});
}
circle_points
}
#[wasm_bindgen]
pub fn web_calculate(x: i32, y: i32, radius: i32) -> JsValue {
let boundary = calculate(x, y, radius);
JsValue::from_serde(&boundary).unwrap()
}
#[cfg(test)]
mod tests {
use super::{calculate, Boundary};
#[test]
fn zero_radius() {
let points = calculate(0, 0, 0);
let expected_points = vec![Boundary { x: 0, y: 0..0 }];
assert_eq!(points, expected_points);
}
#[test]
fn one_radius() {
let points = calculate(0, 0, 1);
let expected_points = vec![
Boundary { x: -1, y: 0..0 },
Boundary { x: 0, y: -1..1 },
Boundary { x: 1, y: 0..0 },
];
assert_eq!(points, expected_points);
}
#[test]
fn small_radius() {
let points = calculate(0, 0, 3);
let expected_points = vec![
Boundary { x: -3, y: -1..1 },
Boundary { x: -2, y: -2..2 },
Boundary { x: -1, y: -3..3 },
Boundary { x: 0, y: -3..3 },
Boundary { x: 1, y: -3..3 },
Boundary { x: 2, y: -2..2 },
Boundary { x: 3, y: -1..1 },
];
assert_eq!(points, expected_points);
}
mod circle_at_origin {
use super::super::{calculate, Boundary};
#[test]
fn it_has_all_the_expected_coordinates() {
let points = calculate(0, 0, 7);
let expected_points = vec![
Boundary { x: -7, y: -2..2 },
Boundary { x: -6, y: -4..4 },
Boundary { x: -5, y: -5..5 },
Boundary { x: -4, y: -6..6 },
Boundary { x: -3, y: -6..6 },
Boundary { x: -2, y: -7..7 },
Boundary { x: -1, y: -7..7 },
Boundary { x: 0, y: -7..7 },
Boundary { x: 1, y: -7..7 },
Boundary { x: 2, y: -7..7 },
Boundary { x: 3, y: -6..6 },
Boundary { x: 4, y: -6..6 },
Boundary { x: 5, y: -5..5 },
Boundary { x: 6, y: -4..4 },
Boundary { x: 7, y: -2..2 },
];
assert_eq!(points, expected_points);
}
#[test]
fn it_has_consecutive_x_values() {
let mut xes = Vec::new();
for Boundary { x, y: _ } in calculate(0, 0, 16) {
xes.push(x);
}
let expected_xes = vec![
-16, -15, -14, -13, -12, -11, -10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3,
4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
];
assert_eq!(xes, expected_xes);
}
}
mod circle_offset_from_origin {
use super::super::{calculate, Boundary};
#[test]
fn it_has_all_the_expected_coordinates() {
let points = calculate(9, 3, 7);
let expected_points = vec![
Boundary { x: 2, y: 1..5 },
Boundary { x: 3, y: -1..7 },
Boundary { x: 4, y: -2..8 },
Boundary { x: 5, y: -3..9 },
Boundary { x: 6, y: -3..9 },
Boundary { x: 7, y: -4..10 },
Boundary { x: 8, y: -4..10 },
Boundary { x: 9, y: -4..10 },
Boundary { x: 10, y: -4..10 },
Boundary { x: 11, y: -4..10 },
Boundary { x: 12, y: -3..9 },
Boundary { x: 13, y: -3..9 },
Boundary { x: 14, y: -2..8 },
Boundary { x: 15, y: -1..7 },
Boundary { x: 16, y: 1..5 },
];
assert_eq!(points, expected_points);
}
#[test]
fn it_has_consecutive_x_values() {
let mut xes = Vec::new();
for Boundary { x, y: _ } in calculate(9, 3, 16) {
xes.push(x);
}
let expected_xes = vec![
-7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
16, 17, 18, 19, 20, 21, 22, 23, 24, 25,
];
assert_eq!(xes, expected_xes);
}
}
}