1 files changed, 102 insertions, 1 deletions

diff --git a/src/bitmap.rs b/src/bitmap.rs
index 01a39d9..8ff311b 100644
--- a/src/bitmap.rs
+++ b/src/bitmap.rs
@@ -1,4 +1,7 @@
-use std::convert::{From, Into, TryFrom};
+use std::{
+    convert::{From, Into, TryFrom},
+    ops::Sub,
+};
 
 #[derive(Debug)]
 pub struct Pixmap<T> {
@@ -59,6 +62,7 @@ where
             data,
         }
     }
+
     pub fn new_with(width: u32, height: u32, start: T) -> Self {
         let data = vec![start; (width * height) as usize];
         Pixmap {
@@ -67,18 +71,22 @@ where
             data,
         }
     }
+
     pub fn is_inside<P: Into<MapPoint>>(&self, pt: P) -> bool {
         let MapPoint { x, y } = pt.into();
         x < self.width && y < self.height
     }
+
     pub fn idx<P: Into<MapPoint>>(&self, pt: P) -> usize {
         let MapPoint { x, y } = pt.into();
         (y * self.width + x) as usize
     }
+
     pub fn get<P: Into<MapPoint>>(&self, pt: P) -> T {
         let idx = self.idx(pt);
         self.data[idx]
     }
+
     pub fn set<P: Into<MapPoint>>(&mut self, pt: P, new_val: T) -> T {
         let pt = pt.into();
         let old_val = self.get(pt);
@@ -86,4 +94,97 @@ where
         self.data[idx] = new_val;
         old_val
     }
+
+    pub fn get_circle<P: Into<MapPoint>>(&self, center: P, radius: u32) -> Vec<MapPoint> {
+        let mut circle: Vec<(i64, i64)> = vec![];
+        let MapPoint { x, y } = center.into();
+        let x = x as i64;
+        let y = y as i64;
+        let (mut dx, mut dy, mut err) = (radius as i64, 0i64, 1 - radius as i64);
+        while dx >= dy {
+            circle.push((x + dx, y + dy));
+            circle.push((x - dx, y + dy));
+            circle.push((x + dx, y - dy));
+            circle.push((x - dx, y - dy));
+            circle.push((x + dy, y + dx));
+            circle.push((x - dy, y + dx));
+            circle.push((x + dy, y - dx));
+            circle.push((x - dy, y - dx));
+            dy = dy + 1;
+            if err < 0 {
+                err = err + 2 * dy + 1;
+            } else {
+                dx -= 1;
+                err += 2 * (dy - dx) + 1;
+            }
+        }
+        for xi in 0..radius as i64 {
+            for yi in 0..radius as i64 {
+                if xi.pow(2) + yi.pow(2) < (radius as i64).pow(2) {
+                    circle.push((x + xi, y + yi));
+                    circle.push((x - xi, y + yi));
+                    circle.push((x + xi, y - yi));
+                    circle.push((x - xi, y - yi));
+                }
+            }
+        }
+        circle
+            .into_iter()
+            .flat_map(|pt| MapPoint::try_from(pt))
+            .filter(|&pt| self.is_inside(pt))
+            .collect()
+    }
+
+    pub fn get_line<P: Into<MapPoint>>(&self, start: P, end: P) -> Vec<MapPoint> {
+        let MapPoint { x: x1, y: y1 } = start.into();
+        let MapPoint { x: x2, y: y2 } = end.into();
+        let mut coordinates = vec![];
+        let dx = abs_difference(x1, x2) as i64;
+        let dy = abs_difference(y1, y2) as i64;
+        let sx = {
+            if x1 < x2 {
+                1
+            } else {
+                -1
+            }
+        };
+        let sy = {
+            if y1 < y2 {
+                1
+            } else {
+                -1
+            }
+        };
+        let mut err: i64 = dx - dy;
+        let mut current_x = x1 as i64;
+        let mut current_y = y1 as i64;
+        loop {
+            coordinates.push((current_x, current_y));
+            if current_x == x2 as i64 && current_y == y2 as i64 {
+                break;
+            }
+            let e2 = 2 * err;
+            if e2 > -dy {
+                err -= dy;
+                current_x += sx;
+            }
+            if e2 < dx {
+                err += dx;
+                current_y += sy;
+            }
+        }
+        coordinates
+            .into_iter()
+            .flat_map(|pt| MapPoint::try_from(pt))
+            .filter(|&pt| self.is_inside(pt))
+            .collect()
+    }
+}
+
+fn abs_difference<T: Sub<Output = T> + Ord>(x: T, y: T) -> T {
+    if x < y {
+        y - x
+    } else {
+        x - y
+    }
 }