Fix the polygon point containment algorithm

The algorithm before was really not working for a lot of edge cases and
very difficult to adapt. This version is definitely not the be-all and
end-all, but it should work for most (well, hopefully all) cases. After
refactoring and hopefully simplifying and straightening out the logic a
little more, it should be verifiable.

2 files changed, 83 insertions, 29 deletions

diff --git a/src/math/line_segment.rs b/src/math/line_segment.rs
index d7bcdb1..338a681 100644
--- a/src/math/line_segment.rs
+++ b/src/math/line_segment.rs
@@ -3,6 +3,7 @@ use alga::general::{ClosedMul, ClosedSub};
 use nalgebra::Scalar;
 use num_traits::Zero;
 
+#[derive(Debug)]
 pub struct LineSegment<T: Scalar + Copy> {
     pub start: Vec2<T>,
     pub end: Vec2<T>,
diff --git a/src/math/polygon.rs b/src/math/polygon.rs
index e70cd2c..2af669a 100644
--- a/src/math/polygon.rs
+++ b/src/math/polygon.rs
@@ -23,54 +23,106 @@ impl<T: Scalar + Copy> Polygon<T> {
             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) {
+        for corner in self.corners.iter() {
+            /* Handle the edge case where the point is on a polygon corner, so we don't have to
+             * worry about it later.
+             */
+            if point == *corner {
+                return true;
+            }
+
             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;
+        // The number of times the point line to infinity pierced through the polygon hull.
+        let mut num_pierced = 0;
+
+        /* Find edges that should be ignored. These are all edges, where the straight line passes
+         * right through a corner of the edge. It might still be counted as piercing the polygon,
+         * if the next corners lie below and the previous corner lies above the line or vice
+         * versa, but not if both points lie above it or below. The corners are exempted from the
+         * run through the edges. The edges that should be ignored are saved by their starting
+         * corner's index.
+         */
+        let mut ignore_edge = vec![false; self.corners.len()];
         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 point.y == self.corners[i].y {
+                // The previous corner index
+                let prev_i = (i + self.corners.len() - 1) % self.corners.len();
+
+                // Make sure the edges containing this corner will be ignored.
+                ignore_edge[i] = true;
+                ignore_edge[prev_i] = true;
+
+                /* Make sure we don't count a pierce double because of consecutive collinear
+                 * points. (Although the polygon really should be sanitised, but you know)
+                 */
+                if self.corners[prev_i].y == point.y {
+                    continue;
+                }
+
+                /* Ignore coming collinear points, since we are only interested in when the
+                 * y-coordinate finally changes
+                 */
+                let mut j = (i + 1) % self.corners.len();
+                while i != j {
+                    if self.corners[j].y != point.y {
+                        if (self.corners[prev_i].y < point.y && self.corners[j].y > point.y)
+                            || (self.corners[prev_i].y > point.y && self.corners[j].y < point.y)
+                        {
+                            /* Only count as pierced when it would be right of the point, otherwise
+                             * it would be like checking to the left of the line that is drawn to
+                             * infinity, which is incorrect
+                             */
+                            if self.corners[i].x >= point.x {
+                                //println!("Pierced through corner {:?}", self.corners[i]);
+                                num_pierced += 1;
+                            }
+                        }
+
+                        break;
+                    }
+
+                    j = (j + 1) % self.corners.len();
+                }
+            }
+        }
+
+        // Find the points where the x-line may actually collide with a proper line.. ^^
+        for (i, edge_start) in self.corners.iter().enumerate() {
+            if ignore_edge[i] {
+                continue;
+            }
+
+            let next = (i + 1) % self.corners.len();
+            let current_edge = LineSegment::new(*edge_start, self.corners[next]);
 
             if LineSegment::intersect(&current_edge, &line_to_infinity) {
+                num_pierced += 1;
+                //println!("Pierced through edge: {:?}", &current_edge);
+
                 /* 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)
+                if super::triplet_orientation(*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;
+                    // The point should be right on an edge.
+                    // XXX: Should this not just be an assertion? It seems that this always has to
+                    // be the case when reaching this part.
+                    return current_edge.contains_collinear(point);
                 }
             }
         }
 
-        num_intersects % 2 == 1
+        //println!("Num pierced is: {}", num_pierced);
+
+        num_pierced % 2 == 1
     }
 
     /// Join this polygon with another, ensuring the area of the two stays the same, minus the
@@ -108,5 +160,6 @@ mod test {
         assert!(polygon.contains(Vec2::new(0.5, 1.5)));
         assert!(!polygon.contains(Vec2::new(-2., 1.9)));
         assert!(!polygon.contains(Vec2::new(0., 3.)));
+        assert!(polygon.contains(Vec2::new(1., 3.)));
     }
 }