Merge #181

181: Implement SpatialObject for Line type r=frewsxcv a=urschrei This doesn't get us any speedup, but it _does_ let us use the `Line` type directly in an `RTree`, which reduces complexity quite a bit.
georust · Mar 15, 2018 · 3842c03 · 3842c03
2 parents 71bf680 + 4df2c05
commit 3842c03
Show file tree

Hide file tree

Showing 2 changed files with 59 additions and 29 deletions.
diff --git a/src/algorithm/simplifyvw.rs b/src/algorithm/simplifyvw.rs
@@ -1,15 +1,14 @@
 use std::cmp::Ordering;
 use std::collections::BinaryHeap;
 use num_traits::Float;
-use types::{LineString, MultiLineString, MultiPolygon, Point, Polygon};
+use types::{Line, LineString, MultiLineString, MultiPolygon, Point, Polygon};
 use algorithm::boundingbox::BoundingBox;
 
 use spade::SpadeFloat;
-use spade::primitives::SimpleEdge;
 use spade::BoundingRect;
 use spade::rtree::RTree;
 
-// Store triangle information
+/// Store triangle information
 // current is the candidate point for removal
 #[derive(Debug)]
 struct VScore<T>
@@ -60,12 +59,14 @@ where
     }
 }
 
-// Geometries that can be simplified using the topology-preserving variant
+/// Geometries that can be simplified using the topology-preserving variant
 #[derive(Debug, Clone, Copy)]
 enum GeomType {
     Line,
     Ring,
 }
+
+/// Settings for Ring and Line geometries
 // initial min: if we ever have fewer than these, stop immediately
 // min_points: if we detect a self-intersection before point removal, and we only
 // have min_points left, stop: since a self-intersection causes removal of the spatially previous
@@ -201,16 +202,12 @@ where
 {
     let mut rings = vec![];
     // Populate R* tree with exterior line segments
-    let ls = exterior
-        .lines()
-        .map(|line| SimpleEdge::new(line.start, line.end))
-        .collect();
-    let mut tree: RTree<SimpleEdge<_>> = RTree::bulk_load(ls);
+    let mut tree: RTree<Line<_>> = RTree::bulk_load(exterior.lines().collect());
     // and with interior segments, if any
     if let Some(interior_rings) = interiors {
         for ring in interior_rings {
             for line in ring.lines() {
-                tree.insert(SimpleEdge::new(line.start, line.end));
+                tree.insert(line);
             }
         }
     }
@@ -231,12 +228,12 @@ where
 }
 
 /// Visvalingam-Whyatt with self-intersection detection to preserve topologies
-// this is a port of the technique at https://www.jasondavies.com/simplify/
+/// this is a port of the technique at https://www.jasondavies.com/simplify/
 fn visvalingam_preserve<T>(
     geomtype: &GeomSettings,
     orig: &[Point<T>],
     epsilon: &T,
-    tree: &mut RTree<SimpleEdge<Point<T>>>,
+    tree: &mut RTree<Line<T>>,
 ) -> Vec<Point<T>>
 where
     T: Float + SpadeFloat,
@@ -347,14 +344,8 @@ where
                 intersector: false,
             };
             // add re-computed line segments to the tree
-            tree.insert(SimpleEdge::new(
-                orig[ai as usize],
-                orig[current_point as usize],
-            ));
-            tree.insert(SimpleEdge::new(
-                orig[current_point as usize],
-                orig[bi as usize],
-            ));
+            tree.insert(Line::new(orig[ai as usize], orig[current_point as usize]));
+            tree.insert(Line::new(orig[current_point as usize], orig[bi as usize]));
             // push re-computed triangle onto heap
             pq.push(new_triangle);
         }
@@ -366,24 +357,24 @@ where
         .collect::<Vec<Point<T>>>()
 }
 
-// is p1 -> p2 -> p3 wound counterclockwise?
+/// is p1 -> p2 -> p3 wound counterclockwise?
 fn ccw<T>(p1: &Point<T>, p2: &Point<T>, p3: &Point<T>) -> bool
 where
     T: Float,
 {
     (p3.y() - p1.y()) * (p2.x() - p1.x()) > (p2.y() - p1.y()) * (p3.x() - p1.x())
 }
 
-// checks whether line segments with p1-p4 as their start and endpoints touch or cross
+/// checks whether line segments with p1-p4 as their start and endpoints touch or cross
 fn cartesian_intersect<T>(p1: &Point<T>, p2: &Point<T>, p3: &Point<T>, p4: &Point<T>) -> bool
 where
     T: Float,
 {
     (ccw(p1, p3, p4) ^ ccw(p2, p3, p4)) & (ccw(p1, p2, p3) ^ ccw(p1, p2, p4))
 }
 
-// check whether a triangle's edges intersect with any other edges of the LineString
-fn tree_intersect<T>(tree: &RTree<SimpleEdge<Point<T>>>, triangle: &VScore<T>, orig: &[Point<T>]) -> bool
+/// check whether a triangle's edges intersect with any other edges of the LineString
+fn tree_intersect<T>(tree: &RTree<Line<T>>, triangle: &VScore<T>, orig: &[Point<T>]) -> bool
 where
     T: Float + SpadeFloat,
 {
@@ -401,8 +392,8 @@ where
     let candidates = tree.lookup_in_rectangle(&BoundingRect::from_corners(&br, &tl));
     candidates.iter().any(|c| {
         // triangle start point, end point
-        let ca = c.from;
-        let cb = c.to;
+        let ca = c.start;
+        let cb = c.end;
         if ca != point_a && ca != point_c && cb != point_a && cb != point_c
             && cartesian_intersect(&ca, &cb, &point_a, &point_c)
         {
@@ -414,7 +405,7 @@ where
     })
 }
 
-// Area of a triangle given three vertices
+/// Area of a triangle given three vertices
 fn area<T>(p1: &Point<T>, p2: &Point<T>, p3: &Point<T>) -> T
 where
     T: Float,

diff --git a/src/types.rs b/src/types.rs
@@ -6,10 +6,11 @@ use std::ops::Sub;
 use std::fmt::Debug;
 
 use std::iter::{self, FromIterator, Iterator};
-
+use algorithm::boundingbox::BoundingBox;
+use algorithm::distance::Distance;
 use spade::SpadeNum;
-use spade::{PointN, TwoDimensional};
 use num_traits::{Float, Num, NumCast, ToPrimitive};
+use spade::{BoundingRect, PointN, SpatialObject, TwoDimensional};
 
 /// The type of an x or y value of a point/coordinate.
 ///
@@ -552,6 +553,30 @@ where
     }
 }
 
+impl<T> SpatialObject for Line<T>
+where
+    T: Float + SpadeNum + Debug,
+{
+    type Point = Point<T>;
+
+    fn mbr(&self) -> BoundingRect<Self::Point> {
+        let bbox = self.bbox();
+        BoundingRect::from_corners(
+            &Point::new(bbox.xmin, bbox.ymin),
+            &Point::new(bbox.xmax, bbox.ymax),
+        )
+    }
+
+    fn distance2(&self, point: &Self::Point) -> <Self::Point as PointN>::Scalar {
+        let d = self.distance(point);
+        if d == T::zero() {
+            d
+        } else {
+            d.powi(2)
+        }
+    }
+}
+
 /// An ordered collection of two or more [`Point`s](struct.Point.html), representing a path between locations
 ///
 /// Create a `LineString` by calling it directly:
@@ -940,6 +965,7 @@ impl<T: CoordinateType> Geometry<T> {
 
 #[cfg(test)]
 mod test {
+    use spade::primitives::SimpleEdge;
     use types::*;
 
     #[test]
@@ -1009,4 +1035,17 @@ mod test {
         let p: Point<i64> = Point::new(1_000_000, 0);
         assert_eq!(p.x(), 1_000_000i64);
     }
+
+    #[test]
+    /// ensure Line's SpatialObject impl is correct
+    fn line_test() {
+        let se = SimpleEdge::new(Point::new(0.0, 0.0), Point::new(5.0, 5.0));
+        let l = Line::new(Point::new(0.0, 0.0), Point::new(5.0, 5.0));
+        assert_eq!(se.mbr(), l.mbr());
+        // difference in 15th decimal place
+        assert_relative_eq!(
+            se.distance2(&Point::new(4.0, 10.0)),
+            l.distance2(&Point::new(4.0, 10.0))
+        );
+    }
 }