Add polygon that can check if a point is inside

..except for one super super edgy edge case, but I wanted to get this
algorithm out into a commit before I ruin it completely (probably)

1 files changed, 112 insertions, 0 deletions

diff --git a/src/math/polygon.rs b/src/math/polygon.rs
new file mode 100644
index 0000000..e70cd2c
--- /dev/null
+++ b/src/math/polygon.rs
@@ -0,0 +1,112 @@
+use super::{LineSegment, TripletOrientation, Vec2};
+use alga::general::{ClosedMul, ClosedSub};
+use nalgebra::Scalar;
+use num_traits::Zero;
+
+pub struct Polygon<T: Scalar + Copy> {
+    pub corners: Vec<Vec2<T>>,
+}
+
+impl<T: Scalar + Copy> Polygon<T> {
+    pub fn new(corners: Vec<Vec2<T>>) -> Self {
+        Self { corners }
+    }
+
+    /// Check whether a point is inside a polygon or not. If a point lies on an edge, it also
+    /// counts as inside the polygon.
+    pub fn contains(&self, point: Vec2<T>) -> bool
+    where
+        T: Scalar + Copy + ClosedSub + ClosedMul + PartialOrd + Zero,
+    {
+        // Must be at least a triangle to contain anything
+        if self.corners.len() < 3 {
+            return false;
+        }
+
+        /* What's happening here:
+         *
+         * This algorithm creates a horizontal line for the point that should be checked. It goes
+         * to infinity (since infinite lines are not possible, it just goes to the maximum x value
+         * of all corner points). Then, the times the line crosses a polygon edge is counted. If
+         * the times it hit a polygon edge is uneven, it must have been inside, otherwise outside.
+         *
+         * There is an edge case however (pun not intended); When the line from the point is collinear
+         * to a polygon edge. it might hit this edge once and no other (it's at the top y or bottom y
+         * of the polygon), but may still not be inside the polygon. In this case, it's checked
+         * whether the point is in between the corner points of this polygon edge or not. If it is
+         * in between, it is still inside the polygon, otherwise outside.
+         */
+
+        // Get the maximum x for the horizontal lines for "Infinity".
+        let mut max_x = self.corners[0].x;
+        for corner in self.corners.iter().skip(1) {
+            max_x = super::partial_max(corner.x, max_x);
+        }
+        println!("Max x is {:?}", max_x);
+        // The horizontally "infinite" point of the test point.
+        let line_to_infinity = LineSegment::new(point, Vec2::new(max_x, point.y));
+
+        // Check for intersection for all the polygon edges.
+        let mut num_intersects = 0;
+        for i in 0..self.corners.len() {
+            // Wrap around for the edge that returns to the start.
+            let j = (i + 1) % self.corners.len();
+            let current_edge = LineSegment::new(self.corners[i], self.corners[j]);
+
+            if LineSegment::intersect(&current_edge, &line_to_infinity) {
+                /* Check for the edge case, where the point might lie right on an edge of the
+                 * polygon.
+                 */
+                if super::triplet_orientation(current_edge.start, current_edge.end, point)
+                    == TripletOrientation::Collinear
+                {
+                    // The point is right on an edge
+                    if current_edge.contains_collinear(point) {
+                        return true;
+                    }
+                } else {
+                    num_intersects += 1;
+                }
+            }
+        }
+
+        num_intersects % 2 == 1
+    }
+
+    /// Join this polygon with another, ensuring the area of the two stays the same, minus the
+    /// overlap.
+    ///
+    /// # Panics
+    /// If the two polygons do not intersect, it is impossible to unite them into a single polygon,
+    /// in which case this function is bound to fail.
+    // TODO: Create a function that only tries to join the polygons.
+    pub fn unite(&mut self, mut _other: Polygon<T>) {
+        unimplemented!()
+    }
+}
+
+#[cfg(test)]
+mod test {
+    use super::*;
+
+    #[test]
+    fn polygon_contains() {
+        let polygon = Polygon::new(vec![
+            Vec2::new(0., 0.),
+            Vec2::new(-1., 1.),
+            Vec2::new(0., 2.),
+            Vec2::new(1., 3.),
+            Vec2::new(3., 1.5),
+            Vec2::new(2., 0.),
+            Vec2::new(1., 1.),
+        ]);
+
+        assert!(!polygon.contains(Vec2::new(1., -2.)));
+        assert!(!polygon.contains(Vec2::new(-1., 0.5)));
+        assert!(polygon.contains(Vec2::new(0., 0.5)));
+        assert!(polygon.contains(Vec2::new(0.5, 1.)));
+        assert!(polygon.contains(Vec2::new(0.5, 1.5)));
+        assert!(!polygon.contains(Vec2::new(-2., 1.9)));
+        assert!(!polygon.contains(Vec2::new(0., 3.)));
+    }
+}