geo/algorithm/
euclidean_distance.rs

1use crate::{
2    Coord, GeoFloat, Geometry, GeometryCollection, Line, LineString, MultiLineString, MultiPoint,
3    MultiPolygon, Point, Polygon, Rect, Triangle,
4};
5use crate::{Distance, Euclidean};
6use num_traits::{Bounded, Signed, float::FloatConst};
7
8use rstar::RTree;
9use rstar::RTreeNum;
10use rstar::primitives::CachedEnvelope;
11
12#[deprecated(
13    since = "0.29.0",
14    note = "Please use the `Euclidean.distance` method from the `Distance` trait instead"
15)]
16/// Returns the distance between two geometries.
17pub trait EuclideanDistance<T, Rhs = Self> {
18    /// Returns the distance between two geometries
19    ///
20    /// If a `Point` is contained by a `Polygon`, the distance is `0.0`
21    ///
22    /// If a `Point` lies on a `Polygon`'s exterior or interior rings, the distance is `0.0`
23    ///
24    /// If a `Point` lies on a `LineString`, the distance is `0.0`
25    ///
26    /// The distance between a `Point` and an empty `LineString` is `0.0`
27    ///
28    /// # Examples
29    ///
30    /// `Point` to `Point`:
31    ///
32    /// ```
33    /// use approx::assert_relative_eq;
34    /// use geo::EuclideanDistance;
35    /// use geo::point;
36    ///
37    /// let p1 = point!(x: -72.1235, y: 42.3521);
38    /// let p2 = point!(x: -72.1260, y: 42.45);
39    ///
40    /// let distance = p1.euclidean_distance(&p2);
41    ///
42    /// assert_relative_eq!(distance, 0.09793191512474639);
43    /// ```
44    ///
45    /// `Point` to `Polygon`:
46    ///
47    /// ```
48    /// use approx::assert_relative_eq;
49    /// use geo::EuclideanDistance;
50    /// use geo::{point, polygon};
51    ///
52    /// let polygon = polygon![
53    ///     (x: 5., y: 1.),
54    ///     (x: 4., y: 2.),
55    ///     (x: 4., y: 3.),
56    ///     (x: 5., y: 4.),
57    ///     (x: 6., y: 4.),
58    ///     (x: 7., y: 3.),
59    ///     (x: 7., y: 2.),
60    ///     (x: 6., y: 1.),
61    ///     (x: 5., y: 1.),
62    /// ];
63    ///
64    /// let point = point!(x: 2.5, y: 0.5);
65    ///
66    /// let distance = point.euclidean_distance(&polygon);
67    ///
68    /// assert_relative_eq!(distance, 2.1213203435596424);
69    /// ```
70    ///
71    /// `Point` to `LineString`:
72    ///
73    /// ```
74    /// use approx::assert_relative_eq;
75    /// use geo::EuclideanDistance;
76    /// use geo::{point, line_string};
77    ///
78    /// let line_string = line_string![
79    ///     (x: 5., y: 1.),
80    ///     (x: 4., y: 2.),
81    ///     (x: 4., y: 3.),
82    ///     (x: 5., y: 4.),
83    ///     (x: 6., y: 4.),
84    ///     (x: 7., y: 3.),
85    ///     (x: 7., y: 2.),
86    ///     (x: 6., y: 1.),
87    /// ];
88    ///
89    /// let point = point!(x: 5.5, y: 2.1);
90    ///
91    /// let distance = point.euclidean_distance(&line_string);
92    ///
93    /// assert_relative_eq!(distance, 1.1313708498984762);
94    /// ```
95    fn euclidean_distance(&self, rhs: &Rhs) -> T;
96}
97
98// ┌───────────────────────────┐
99// │ Implementations for Coord │
100// └───────────────────────────┘
101#[allow(deprecated)]
102impl<T> EuclideanDistance<T, Coord<T>> for Coord<T>
103where
104    T: GeoFloat,
105{
106    /// Minimum distance between two `Coord`s
107    fn euclidean_distance(&self, c: &Coord<T>) -> T {
108        Euclidean.distance(Point(*self), Point(*c))
109    }
110}
111
112#[allow(deprecated)]
113impl<T> EuclideanDistance<T, Line<T>> for Coord<T>
114where
115    T: GeoFloat,
116{
117    /// Minimum distance from a `Coord` to a `Line`
118    fn euclidean_distance(&self, line: &Line<T>) -> T {
119        Euclidean.distance(&Point(*self), line)
120    }
121}
122
123// ┌───────────────────────────┐
124// │ Implementations for Point │
125// └───────────────────────────┘
126
127#[allow(deprecated)]
128impl<T> EuclideanDistance<T, Point<T>> for Point<T>
129where
130    T: GeoFloat,
131{
132    /// Minimum distance between two Points
133    fn euclidean_distance(&self, p: &Point<T>) -> T {
134        Euclidean.distance(*self, *p)
135    }
136}
137
138#[allow(deprecated)]
139impl<T> EuclideanDistance<T, Line<T>> for Point<T>
140where
141    T: GeoFloat,
142{
143    /// Minimum distance from a Line to a Point
144    fn euclidean_distance(&self, line: &Line<T>) -> T {
145        Euclidean.distance(self, line)
146    }
147}
148
149#[allow(deprecated)]
150impl<T> EuclideanDistance<T, LineString<T>> for Point<T>
151where
152    T: GeoFloat,
153{
154    /// Minimum distance from a Point to a LineString
155    fn euclidean_distance(&self, line_string: &LineString<T>) -> T {
156        Euclidean.distance(self, line_string)
157    }
158}
159
160#[allow(deprecated)]
161impl<T> EuclideanDistance<T, Polygon<T>> for Point<T>
162where
163    T: GeoFloat,
164{
165    /// Minimum distance from a Point to a Polygon
166    fn euclidean_distance(&self, polygon: &Polygon<T>) -> T {
167        Euclidean.distance(self, polygon)
168    }
169}
170
171// ┌──────────────────────────┐
172// │ Implementations for Line │
173// └──────────────────────────┘
174
175#[allow(deprecated)]
176impl<T> EuclideanDistance<T, Coord<T>> for Line<T>
177where
178    T: GeoFloat,
179{
180    /// Minimum distance from a `Line` to a `Coord`
181    fn euclidean_distance(&self, coord: &Coord<T>) -> T {
182        Euclidean.distance(self, *coord)
183    }
184}
185
186#[allow(deprecated)]
187impl<T> EuclideanDistance<T, Point<T>> for Line<T>
188where
189    T: GeoFloat,
190{
191    /// Minimum distance from a Line to a Point
192    fn euclidean_distance(&self, point: &Point<T>) -> T {
193        Euclidean.distance(self, point)
194    }
195}
196
197#[allow(deprecated)]
198/// Line to Line distance
199impl<T> EuclideanDistance<T, Line<T>> for Line<T>
200where
201    T: GeoFloat + FloatConst + Signed + RTreeNum,
202{
203    fn euclidean_distance(&self, other: &Line<T>) -> T {
204        Euclidean.distance(self, other)
205    }
206}
207
208#[allow(deprecated)]
209/// Line to LineString
210impl<T> EuclideanDistance<T, LineString<T>> for Line<T>
211where
212    T: GeoFloat + FloatConst + Signed + RTreeNum,
213{
214    fn euclidean_distance(&self, other: &LineString<T>) -> T {
215        Euclidean.distance(self, other)
216    }
217}
218
219#[allow(deprecated)]
220// Line to Polygon distance
221impl<T> EuclideanDistance<T, Polygon<T>> for Line<T>
222where
223    T: GeoFloat + Signed + RTreeNum + FloatConst,
224{
225    fn euclidean_distance(&self, other: &Polygon<T>) -> T {
226        Euclidean.distance(self, other)
227    }
228}
229
230// ┌────────────────────────────────┐
231// │ Implementations for LineString │
232// └────────────────────────────────┘
233
234#[allow(deprecated)]
235impl<T> EuclideanDistance<T, Point<T>> for LineString<T>
236where
237    T: GeoFloat,
238{
239    /// Minimum distance from a LineString to a Point
240    fn euclidean_distance(&self, point: &Point<T>) -> T {
241        Euclidean.distance(self, point)
242    }
243}
244
245#[allow(deprecated)]
246/// LineString to Line
247impl<T> EuclideanDistance<T, Line<T>> for LineString<T>
248where
249    T: GeoFloat + FloatConst + Signed + RTreeNum,
250{
251    fn euclidean_distance(&self, other: &Line<T>) -> T {
252        Euclidean.distance(self, other)
253    }
254}
255
256#[allow(deprecated)]
257/// LineString-LineString distance
258impl<T> EuclideanDistance<T, LineString<T>> for LineString<T>
259where
260    T: GeoFloat + Signed + RTreeNum,
261{
262    fn euclidean_distance(&self, other: &LineString<T>) -> T {
263        Euclidean.distance(self, other)
264    }
265}
266
267#[allow(deprecated)]
268/// LineString to Polygon
269impl<T> EuclideanDistance<T, Polygon<T>> for LineString<T>
270where
271    T: GeoFloat + FloatConst + Signed + RTreeNum,
272{
273    fn euclidean_distance(&self, other: &Polygon<T>) -> T {
274        Euclidean.distance(self, other)
275    }
276}
277
278// ┌─────────────────────────────┐
279// │ Implementations for Polygon │
280// └─────────────────────────────┘
281
282#[allow(deprecated)]
283impl<T> EuclideanDistance<T, Point<T>> for Polygon<T>
284where
285    T: GeoFloat,
286{
287    /// Minimum distance from a Polygon to a Point
288    fn euclidean_distance(&self, point: &Point<T>) -> T {
289        Euclidean.distance(self, point)
290    }
291}
292
293#[allow(deprecated)]
294// Polygon to Line distance
295impl<T> EuclideanDistance<T, Line<T>> for Polygon<T>
296where
297    T: GeoFloat + FloatConst + Signed + RTreeNum,
298{
299    fn euclidean_distance(&self, other: &Line<T>) -> T {
300        Euclidean.distance(self, other)
301    }
302}
303
304#[allow(deprecated)]
305/// Polygon to LineString distance
306impl<T> EuclideanDistance<T, LineString<T>> for Polygon<T>
307where
308    T: GeoFloat + FloatConst + Signed + RTreeNum,
309{
310    fn euclidean_distance(&self, other: &LineString<T>) -> T {
311        Euclidean.distance(self, other)
312    }
313}
314
315#[allow(deprecated)]
316// Polygon to Polygon distance
317impl<T> EuclideanDistance<T, Polygon<T>> for Polygon<T>
318where
319    T: GeoFloat + FloatConst + RTreeNum,
320{
321    fn euclidean_distance(&self, poly2: &Polygon<T>) -> T {
322        Euclidean.distance(self, poly2)
323    }
324}
325
326// ┌────────────────────────────────────────┐
327// │ Implementations for Rect and Triangle  │
328// └────────────────────────────────────────┘
329
330/// Implements Euclidean distance for Triangles and Rects by converting them to polygons.
331macro_rules! impl_euclidean_distance_for_polygonlike_geometry {
332  ($for:ty,  [$($target:ty),*]) => {
333      $(
334          #[allow(deprecated)]
335          impl<T> EuclideanDistance<T, $target> for $for
336          where
337              T: GeoFloat + Signed + RTreeNum + FloatConst,
338          {
339              fn euclidean_distance(&self, other: &$target) -> T {
340                  Euclidean.distance(self, other)
341              }
342          }
343      )*
344  };
345}
346
347impl_euclidean_distance_for_polygonlike_geometry!(Triangle<T>,  [Point<T>, MultiPoint<T>, Line<T>, LineString<T>, MultiLineString<T>, Polygon<T>, MultiPolygon<T>, GeometryCollection<T>, Rect<T>, Triangle<T>]);
348impl_euclidean_distance_for_polygonlike_geometry!(Rect<T>,      [Point<T>, MultiPoint<T>, Line<T>, LineString<T>, MultiLineString<T>, Polygon<T>, MultiPolygon<T>, GeometryCollection<T>, Rect<T>, Triangle<T>]);
349
350/// Implements Euclidean distance for other geometry types to Triangles and Rects by converting the Triangle or Rect to a polygon.
351macro_rules! impl_euclidean_distance_to_polygonlike_geometry {
352  ($for:ty,  [$($target:ty),*]) => {
353      $(
354          #[allow(deprecated)]
355          impl<T> EuclideanDistance<T, $target> for $for
356          where
357              T: GeoFloat + Signed + RTreeNum + FloatConst,
358          {
359              fn euclidean_distance(&self, other: &$target) -> T {
360                  Euclidean.distance(self, other)
361              }
362          }
363      )*
364  };
365}
366
367impl_euclidean_distance_to_polygonlike_geometry!(Point<T>,               [Rect<T>, Triangle<T>]);
368impl_euclidean_distance_to_polygonlike_geometry!(MultiPoint<T>,          [Rect<T>, Triangle<T>]);
369impl_euclidean_distance_to_polygonlike_geometry!(Line<T>,                [Rect<T>, Triangle<T>]);
370impl_euclidean_distance_to_polygonlike_geometry!(LineString<T>,          [Rect<T>, Triangle<T>]);
371impl_euclidean_distance_to_polygonlike_geometry!(MultiLineString<T>,     [Rect<T>, Triangle<T>]);
372impl_euclidean_distance_to_polygonlike_geometry!(Polygon<T>,             [Rect<T>, Triangle<T>]);
373impl_euclidean_distance_to_polygonlike_geometry!(MultiPolygon<T>,        [Rect<T>, Triangle<T>]);
374impl_euclidean_distance_to_polygonlike_geometry!(GeometryCollection<T>,  [Rect<T>, Triangle<T>]);
375
376// ┌───────────────────────────────────────────┐
377// │ Implementations for multi geometry types  │
378// └───────────────────────────────────────────┘
379
380/// Euclidean distance implementation for multi geometry types.
381macro_rules! impl_euclidean_distance_for_iter_geometry {
382  ($for:ty,  [$($target:ty),*]) => {
383      $(
384          #[allow(deprecated)]
385          impl<T> EuclideanDistance<T, $target> for $for
386          where
387              T: GeoFloat + FloatConst + RTreeNum,
388          {
389              fn euclidean_distance(&self, target: &$target) -> T {
390                  Euclidean.distance(self, target)
391              }
392          }
393      )*
394  };
395}
396
397impl_euclidean_distance_for_iter_geometry!(MultiPoint<T>,         [Point<T>, MultiPoint<T>, Line<T>, LineString<T>, MultiLineString<T>, Polygon<T>, MultiPolygon<T>, GeometryCollection<T>]);
398impl_euclidean_distance_for_iter_geometry!(MultiLineString<T>,    [Point<T>, MultiPoint<T>, Line<T>, LineString<T>, MultiLineString<T>, Polygon<T>, MultiPolygon<T>, GeometryCollection<T>]);
399impl_euclidean_distance_for_iter_geometry!(MultiPolygon<T>,       [Point<T>, MultiPoint<T>, Line<T>, LineString<T>, MultiLineString<T>, Polygon<T>, MultiPolygon<T>, GeometryCollection<T>]);
400impl_euclidean_distance_for_iter_geometry!(GeometryCollection<T>, [Point<T>, MultiPoint<T>, Line<T>, LineString<T>, MultiLineString<T>, Polygon<T>, MultiPolygon<T>, GeometryCollection<T>]);
401
402/// Euclidean distance implementation for other geometry types to multi geometry types,
403/// using the multi geometry type's implementation.
404macro_rules! impl_euclidean_distance_from_iter_geometry {
405  ($for:ty,  [$($target:ty),*]) => {
406      $(
407        #[allow(deprecated)]
408        impl<T> EuclideanDistance<T, $target> for $for
409        where
410            T: GeoFloat + FloatConst + RTreeNum
411        {
412          fn euclidean_distance(&self, target: &$target) -> T {
413              Euclidean.distance(self, target)
414          }
415        }
416      )*
417  };
418}
419
420// This macro is used to implement EuclideanDistance to multi geometry types for non-multi geometry types.
421// Rect and Triangle are omitted here because those implementations are included in the Rect and Triangle section above.
422impl_euclidean_distance_from_iter_geometry!(Point<T>,         [MultiPoint<T>, MultiLineString<T>, MultiPolygon<T>, GeometryCollection<T>]);
423impl_euclidean_distance_from_iter_geometry!(Line<T>,          [MultiPoint<T>, MultiLineString<T>, MultiPolygon<T>, GeometryCollection<T>]);
424impl_euclidean_distance_from_iter_geometry!(LineString<T>,    [MultiPoint<T>, MultiLineString<T>, MultiPolygon<T>, GeometryCollection<T>]);
425impl_euclidean_distance_from_iter_geometry!(Polygon<T>,       [MultiPoint<T>, MultiLineString<T>, MultiPolygon<T>, GeometryCollection<T>]);
426
427// ┌─────────────────────────────────────────────────────────┐
428// │ Implementation to Geometry<T> for every geometry type   │
429// └─────────────────────────────────────────────────────────┘
430
431/// Euclidean distance implementation for every specific Geometry type to Geometry<T>.
432macro_rules! impl_euclidean_distance_to_geometry_for_specific {
433  ([$($for:ty),*]) => {
434      $(
435          #[allow(deprecated)]
436          impl<T> EuclideanDistance<T, Geometry<T>> for $for
437          where
438              T: GeoFloat + FloatConst + RTreeNum,
439          {
440              fn euclidean_distance(&self, geom: &Geometry<T>) -> T {
441                Euclidean.distance(self, geom)
442              }
443          }
444      )*
445  };
446}
447
448impl_euclidean_distance_to_geometry_for_specific!([Point<T>, MultiPoint<T>, Line<T>, LineString<T>, MultiLineString<T>, Polygon<T>, MultiPolygon<T>, Triangle<T>, Rect<T>, GeometryCollection<T>]);
449
450// ┌──────────────────────────────┐
451// │ Implementation for Geometry  │
452// └──────────────────────────────┘
453
454/// Euclidean distance implementation for Geometry<T> to every specific Geometry type.
455macro_rules! impl_euclidean_distance_to_specific_for_geometry {
456  ([$($for:ty),*]) => {
457      $(
458          #[allow(deprecated)]
459          impl<T> EuclideanDistance<T, $for> for Geometry<T>
460          where
461              T: GeoFloat + FloatConst + RTreeNum
462          {
463              crate::geometry_delegate_impl! {
464                  fn euclidean_distance(&self, other: &$for) -> T;
465              }
466          }
467      )*
468  };
469}
470
471impl_euclidean_distance_to_specific_for_geometry!([Point<T>, MultiPoint<T>, Line<T>, LineString<T>, MultiLineString<T>, Polygon<T>, MultiPolygon<T>, Triangle<T>, Rect<T>, GeometryCollection<T>]);
472
473#[allow(deprecated)]
474impl<T> EuclideanDistance<T> for Geometry<T>
475where
476    T: GeoFloat + FloatConst,
477{
478    crate::geometry_delegate_impl! {
479        fn euclidean_distance(&self, other: &Geometry<T>) -> T;
480    }
481}
482
483// ┌───────────┐
484// │ Utilities │
485// └───────────┘
486
487#[deprecated(
488    since = "0.29.0",
489    note = "Please use the `Euclidean.distance` method from the `Distance` trait instead"
490)]
491/// Uses an R* tree and nearest-neighbour lookups to calculate minimum distances
492// This is somewhat slow and memory-inefficient, but certainly better than quadratic time
493pub fn nearest_neighbour_distance<T>(geom1: &LineString<T>, geom2: &LineString<T>) -> T
494where
495    T: GeoFloat + RTreeNum,
496{
497    let tree_a = RTree::bulk_load(geom1.lines().map(CachedEnvelope::new).collect());
498    let tree_b = RTree::bulk_load(geom2.lines().map(CachedEnvelope::new).collect());
499    // Return minimum distance between all geom a points and geom b lines, and all geom b points and geom a lines
500    geom2
501        .points()
502        .fold(<T as Bounded>::max_value(), |acc, point| {
503            let nearest = tree_a.nearest_neighbor(&point).unwrap();
504            #[allow(deprecated)]
505            acc.min(nearest.euclidean_distance(&point))
506        })
507        .min(geom1.points().fold(Bounded::max_value(), |acc, point| {
508            let nearest = tree_b.nearest_neighbor(&point).unwrap();
509            #[allow(deprecated)]
510            acc.min(nearest.euclidean_distance(&point))
511        }))
512}
513
514#[cfg(test)]
515mod test {
516    // These tests have been ported to the new line_measures::euclidean::distance module.
517    // They'll get removed eventually, so lets leave the deprecated tests here until then
518    // as assurance that they old traits are properly delegating to the new implementation.
519    #![allow(deprecated)]
520
521    use super::*;
522    use crate::Orient;
523    use crate::orient::Direction;
524    use crate::{Line, LineString, MultiLineString, MultiPoint, MultiPolygon, Point, Polygon};
525    use geo_types::{coord, polygon, private_utils::line_segment_distance};
526
527    #[test]
528    fn line_segment_distance_test() {
529        let o1 = Point::new(8.0, 0.0);
530        let o2 = Point::new(5.5, 0.0);
531        let o3 = Point::new(5.0, 0.0);
532        let o4 = Point::new(4.5, 1.5);
533
534        let p1 = Point::new(7.2, 2.0);
535        let p2 = Point::new(6.0, 1.0);
536
537        let dist = line_segment_distance(o1, p1, p2);
538        let dist2 = line_segment_distance(o2, p1, p2);
539        let dist3 = line_segment_distance(o3, p1, p2);
540        let dist4 = line_segment_distance(o4, p1, p2);
541        // Results agree with Shapely
542        assert_relative_eq!(dist, 2.0485900789263356);
543        assert_relative_eq!(dist2, 1.118033988749895);
544        assert_relative_eq!(dist3, std::f64::consts::SQRT_2); // workaround clippy::correctness error approx_constant (1.4142135623730951)
545        assert_relative_eq!(dist4, 1.5811388300841898);
546        // Point is on the line
547        let zero_dist = line_segment_distance(p1, p1, p2);
548        assert_relative_eq!(zero_dist, 0.0);
549    }
550    #[test]
551    // Point to Polygon, outside point
552    fn point_polygon_distance_outside_test() {
553        // an octagon
554        let points = vec![
555            (5., 1.),
556            (4., 2.),
557            (4., 3.),
558            (5., 4.),
559            (6., 4.),
560            (7., 3.),
561            (7., 2.),
562            (6., 1.),
563            (5., 1.),
564        ];
565        let ls = LineString::from(points);
566        let poly = Polygon::new(ls, vec![]);
567        // A Random point outside the octagon
568        let p = Point::new(2.5, 0.5);
569        let dist = p.euclidean_distance(&poly);
570        assert_relative_eq!(dist, 2.1213203435596424);
571    }
572    #[test]
573    // Point to Polygon, inside point
574    fn point_polygon_distance_inside_test() {
575        // an octagon
576        let points = vec![
577            (5., 1.),
578            (4., 2.),
579            (4., 3.),
580            (5., 4.),
581            (6., 4.),
582            (7., 3.),
583            (7., 2.),
584            (6., 1.),
585            (5., 1.),
586        ];
587        let ls = LineString::from(points);
588        let poly = Polygon::new(ls, vec![]);
589        // A Random point inside the octagon
590        let p = Point::new(5.5, 2.1);
591        let dist = p.euclidean_distance(&poly);
592        assert_relative_eq!(dist, 0.0);
593    }
594    #[test]
595    // Point to Polygon, on boundary
596    fn point_polygon_distance_boundary_test() {
597        // an octagon
598        let points = vec![
599            (5., 1.),
600            (4., 2.),
601            (4., 3.),
602            (5., 4.),
603            (6., 4.),
604            (7., 3.),
605            (7., 2.),
606            (6., 1.),
607            (5., 1.),
608        ];
609        let ls = LineString::from(points);
610        let poly = Polygon::new(ls, vec![]);
611        // A point on the octagon
612        let p = Point::new(5.0, 1.0);
613        let dist = p.euclidean_distance(&poly);
614        assert_relative_eq!(dist, 0.0);
615    }
616    #[test]
617    // Point to Polygon, on boundary
618    fn point_polygon_boundary_test2() {
619        let exterior = LineString::from(vec![
620            (0., 0.),
621            (0., 0.0004),
622            (0.0004, 0.0004),
623            (0.0004, 0.),
624            (0., 0.),
625        ]);
626
627        let poly = Polygon::new(exterior, vec![]);
628        let bugged_point = Point::new(0.0001, 0.);
629        assert_relative_eq!(poly.euclidean_distance(&bugged_point), 0.);
630    }
631    #[test]
632    // Point to Polygon, empty Polygon
633    fn point_polygon_empty_test() {
634        // an empty Polygon
635        let points = vec![];
636        let ls = LineString::new(points);
637        let poly = Polygon::new(ls, vec![]);
638        // A point on the octagon
639        let p = Point::new(2.5, 0.5);
640        let dist = p.euclidean_distance(&poly);
641        assert_relative_eq!(dist, 0.0);
642    }
643    #[test]
644    // Point to Polygon with an interior ring
645    fn point_polygon_interior_cutout_test() {
646        // an octagon
647        let ext_points = vec![
648            (4., 1.),
649            (5., 2.),
650            (5., 3.),
651            (4., 4.),
652            (3., 4.),
653            (2., 3.),
654            (2., 2.),
655            (3., 1.),
656            (4., 1.),
657        ];
658        // cut out a triangle inside octagon
659        let int_points = vec![(3.5, 3.5), (4.4, 1.5), (2.6, 1.5), (3.5, 3.5)];
660        let ls_ext = LineString::from(ext_points);
661        let ls_int = LineString::from(int_points);
662        let poly = Polygon::new(ls_ext, vec![ls_int]);
663        // A point inside the cutout triangle
664        let p = Point::new(3.5, 2.5);
665        let dist = p.euclidean_distance(&poly);
666
667        // 0.41036467732879783 <-- Shapely
668        assert_relative_eq!(dist, 0.41036467732879767);
669    }
670
671    #[test]
672    fn line_distance_multipolygon_do_not_intersect_test() {
673        // checks that the distance from the multipolygon
674        // is equal to the distance from the closest polygon
675        // taken in isolation, whatever that distance is
676        let ls1 = LineString::from(vec![
677            (0.0, 0.0),
678            (10.0, 0.0),
679            (10.0, 10.0),
680            (5.0, 15.0),
681            (0.0, 10.0),
682            (0.0, 0.0),
683        ]);
684        let ls2 = LineString::from(vec![
685            (0.0, 30.0),
686            (0.0, 25.0),
687            (10.0, 25.0),
688            (10.0, 30.0),
689            (0.0, 30.0),
690        ]);
691        let ls3 = LineString::from(vec![
692            (15.0, 30.0),
693            (15.0, 25.0),
694            (20.0, 25.0),
695            (20.0, 30.0),
696            (15.0, 30.0),
697        ]);
698        let pol1 = Polygon::new(ls1, vec![]);
699        let pol2 = Polygon::new(ls2, vec![]);
700        let pol3 = Polygon::new(ls3, vec![]);
701        let mp = MultiPolygon::new(vec![pol1.clone(), pol2, pol3]);
702        let pnt1 = Point::new(0.0, 15.0);
703        let pnt2 = Point::new(10.0, 20.0);
704        let ln = Line::new(pnt1.0, pnt2.0);
705        let dist_mp_ln = ln.euclidean_distance(&mp);
706        let dist_pol1_ln = ln.euclidean_distance(&pol1);
707        assert_relative_eq!(dist_mp_ln, dist_pol1_ln);
708    }
709
710    #[test]
711    fn point_distance_multipolygon_test() {
712        let ls1 = LineString::from(vec![(0.0, 0.0), (1.0, 10.0), (2.0, 0.0), (0.0, 0.0)]);
713        let ls2 = LineString::from(vec![(3.0, 0.0), (4.0, 10.0), (5.0, 0.0), (3.0, 0.0)]);
714        let p1 = Polygon::new(ls1, vec![]);
715        let p2 = Polygon::new(ls2, vec![]);
716        let mp = MultiPolygon::new(vec![p1, p2]);
717        let p = Point::new(50.0, 50.0);
718        assert_relative_eq!(p.euclidean_distance(&mp), 60.959002616512684);
719    }
720    #[test]
721    // Point to LineString
722    fn point_linestring_distance_test() {
723        // like an octagon, but missing the lowest horizontal segment
724        let points = vec![
725            (5., 1.),
726            (4., 2.),
727            (4., 3.),
728            (5., 4.),
729            (6., 4.),
730            (7., 3.),
731            (7., 2.),
732            (6., 1.),
733        ];
734        let ls = LineString::from(points);
735        // A Random point "inside" the LineString
736        let p = Point::new(5.5, 2.1);
737        let dist = p.euclidean_distance(&ls);
738        assert_relative_eq!(dist, 1.1313708498984762);
739    }
740    #[test]
741    // Point to LineString, point lies on the LineString
742    fn point_linestring_contains_test() {
743        // like an octagon, but missing the lowest horizontal segment
744        let points = vec![
745            (5., 1.),
746            (4., 2.),
747            (4., 3.),
748            (5., 4.),
749            (6., 4.),
750            (7., 3.),
751            (7., 2.),
752            (6., 1.),
753        ];
754        let ls = LineString::from(points);
755        // A point which lies on the LineString
756        let p = Point::new(5.0, 4.0);
757        let dist = p.euclidean_distance(&ls);
758        assert_relative_eq!(dist, 0.0);
759    }
760    #[test]
761    // Point to LineString, closed triangle
762    fn point_linestring_triangle_test() {
763        let points = vec![(3.5, 3.5), (4.4, 2.0), (2.6, 2.0), (3.5, 3.5)];
764        let ls = LineString::from(points);
765        let p = Point::new(3.5, 2.5);
766        let dist = p.euclidean_distance(&ls);
767        assert_relative_eq!(dist, 0.5);
768    }
769    #[test]
770    // Point to LineString, empty LineString
771    fn point_linestring_empty_test() {
772        let points = vec![];
773        let ls = LineString::new(points);
774        let p = Point::new(5.0, 4.0);
775        let dist = p.euclidean_distance(&ls);
776        assert_relative_eq!(dist, 0.0);
777    }
778    #[test]
779    fn distance_multilinestring_test() {
780        let v1 = LineString::from(vec![(0.0, 0.0), (1.0, 10.0)]);
781        let v2 = LineString::from(vec![(1.0, 10.0), (2.0, 0.0), (3.0, 1.0)]);
782        let mls = MultiLineString::new(vec![v1, v2]);
783        let p = Point::new(50.0, 50.0);
784        assert_relative_eq!(p.euclidean_distance(&mls), 63.25345840347388);
785    }
786    #[test]
787    fn distance1_test() {
788        assert_relative_eq!(
789            Point::new(0., 0.).euclidean_distance(&Point::new(1., 0.)),
790            1.
791        );
792    }
793    #[test]
794    fn distance2_test() {
795        let dist = Point::new(-72.1235, 42.3521).euclidean_distance(&Point::new(72.1260, 70.612));
796        assert_relative_eq!(dist, 146.99163308930207);
797    }
798    #[test]
799    fn distance_multipoint_test() {
800        let v = vec![
801            Point::new(0.0, 10.0),
802            Point::new(1.0, 1.0),
803            Point::new(10.0, 0.0),
804            Point::new(1.0, -1.0),
805            Point::new(0.0, -10.0),
806            Point::new(-1.0, -1.0),
807            Point::new(-10.0, 0.0),
808            Point::new(-1.0, 1.0),
809            Point::new(0.0, 10.0),
810        ];
811        let mp = MultiPoint::new(v);
812        let p = Point::new(50.0, 50.0);
813        assert_relative_eq!(p.euclidean_distance(&mp), 64.03124237432849)
814    }
815    #[test]
816    fn distance_line_test() {
817        let line0 = Line::from([(0., 0.), (5., 0.)]);
818        let p0 = Point::new(2., 3.);
819        let p1 = Point::new(3., 0.);
820        let p2 = Point::new(6., 0.);
821        assert_relative_eq!(line0.euclidean_distance(&p0), 3.);
822        assert_relative_eq!(p0.euclidean_distance(&line0), 3.);
823
824        assert_relative_eq!(line0.euclidean_distance(&p1), 0.);
825        assert_relative_eq!(p1.euclidean_distance(&line0), 0.);
826
827        assert_relative_eq!(line0.euclidean_distance(&p2), 1.);
828        assert_relative_eq!(p2.euclidean_distance(&line0), 1.);
829    }
830    #[test]
831    fn distance_line_line_test() {
832        let line0 = Line::from([(0., 0.), (5., 0.)]);
833        let line1 = Line::from([(2., 1.), (7., 2.)]);
834        assert_relative_eq!(line0.euclidean_distance(&line1), 1.);
835        assert_relative_eq!(line1.euclidean_distance(&line0), 1.);
836    }
837    #[test]
838    // See https://github.com/georust/geo/issues/476
839    fn distance_line_polygon_test() {
840        let line = Line::new(
841            coord! {
842                x: -0.17084137691985102,
843                y: 0.8748085493016657,
844            },
845            coord! {
846                x: -0.17084137691985102,
847                y: 0.09858870312437906,
848            },
849        );
850        let poly: Polygon<f64> = polygon![
851            coord! {
852                x: -0.10781391405721802,
853                y: -0.15433610862574643,
854            },
855            coord! {
856                x: -0.7855276236615211,
857                y: 0.23694208404779793,
858            },
859            coord! {
860                x: -0.7855276236615214,
861                y: -0.5456143012992907,
862            },
863            coord! {
864                x: -0.10781391405721802,
865                y: -0.15433610862574643,
866            },
867        ];
868        assert_eq!(line.euclidean_distance(&poly), 0.18752558079168907);
869    }
870    #[test]
871    // test edge-vertex minimum distance
872    fn test_minimum_polygon_distance() {
873        let points_raw = [
874            (126., 232.),
875            (126., 212.),
876            (112., 202.),
877            (97., 204.),
878            (87., 215.),
879            (87., 232.),
880            (100., 246.),
881            (118., 247.),
882        ];
883        let points = points_raw
884            .iter()
885            .map(|e| Point::new(e.0, e.1))
886            .collect::<Vec<_>>();
887        let poly1 = Polygon::new(LineString::from(points), vec![]);
888
889        let points_raw_2 = [
890            (188., 231.),
891            (189., 207.),
892            (174., 196.),
893            (164., 196.),
894            (147., 220.),
895            (158., 242.),
896            (177., 242.),
897        ];
898        let points2 = points_raw_2
899            .iter()
900            .map(|e| Point::new(e.0, e.1))
901            .collect::<Vec<_>>();
902        let poly2 = Polygon::new(LineString::from(points2), vec![]);
903        let dist = nearest_neighbour_distance(poly1.exterior(), poly2.exterior());
904        assert_relative_eq!(dist, 21.0);
905    }
906    #[test]
907    // test vertex-vertex minimum distance
908    fn test_minimum_polygon_distance_2() {
909        let points_raw = [
910            (118., 200.),
911            (153., 179.),
912            (106., 155.),
913            (88., 190.),
914            (118., 200.),
915        ];
916        let points = points_raw
917            .iter()
918            .map(|e| Point::new(e.0, e.1))
919            .collect::<Vec<_>>();
920        let poly1 = Polygon::new(LineString::from(points), vec![]);
921
922        let points_raw_2 = [
923            (242., 186.),
924            (260., 146.),
925            (182., 175.),
926            (216., 193.),
927            (242., 186.),
928        ];
929        let points2 = points_raw_2
930            .iter()
931            .map(|e| Point::new(e.0, e.1))
932            .collect::<Vec<_>>();
933        let poly2 = Polygon::new(LineString::from(points2), vec![]);
934        let dist = nearest_neighbour_distance(poly1.exterior(), poly2.exterior());
935        assert_relative_eq!(dist, 29.274562336608895);
936    }
937    #[test]
938    // test edge-edge minimum distance
939    fn test_minimum_polygon_distance_3() {
940        let points_raw = [
941            (182., 182.),
942            (182., 168.),
943            (138., 160.),
944            (136., 193.),
945            (182., 182.),
946        ];
947        let points = points_raw
948            .iter()
949            .map(|e| Point::new(e.0, e.1))
950            .collect::<Vec<_>>();
951        let poly1 = Polygon::new(LineString::from(points), vec![]);
952
953        let points_raw_2 = [
954            (232., 196.),
955            (234., 150.),
956            (194., 165.),
957            (194., 191.),
958            (232., 196.),
959        ];
960        let points2 = points_raw_2
961            .iter()
962            .map(|e| Point::new(e.0, e.1))
963            .collect::<Vec<_>>();
964        let poly2 = Polygon::new(LineString::from(points2), vec![]);
965        let dist = nearest_neighbour_distance(poly1.exterior(), poly2.exterior());
966        assert_relative_eq!(dist, 12.0);
967    }
968    #[test]
969    fn test_large_polygon_distance() {
970        let ls = geo_test_fixtures::norway_main::<f64>();
971        let poly1 = Polygon::new(ls, vec![]);
972        let vec2 = vec![
973            (4.921875, 66.33750501996518),
974            (3.69140625, 65.21989393613207),
975            (6.15234375, 65.07213008560697),
976            (4.921875, 66.33750501996518),
977        ];
978        let poly2 = Polygon::new(vec2.into(), vec![]);
979        let distance = poly1.euclidean_distance(&poly2);
980        // GEOS says 2.2864896295566055
981        assert_relative_eq!(distance, 2.2864896295566055);
982    }
983    #[test]
984    // A polygon inside another polygon's ring; they're disjoint in the DE-9IM sense:
985    // FF2FF1212
986    fn test_poly_in_ring() {
987        let shell = geo_test_fixtures::shell::<f64>();
988        let ring = geo_test_fixtures::ring::<f64>();
989        let poly_in_ring = geo_test_fixtures::poly_in_ring::<f64>();
990        // inside is "inside" outside's ring, but they are disjoint
991        let outside = Polygon::new(shell, vec![ring]);
992        let inside = Polygon::new(poly_in_ring, vec![]);
993        assert_relative_eq!(outside.euclidean_distance(&inside), 5.992772737231033);
994    }
995    #[test]
996    // two ring LineStrings; one encloses the other but they neither touch nor intersect
997    fn test_linestring_distance() {
998        let ring = geo_test_fixtures::ring::<f64>();
999        let poly_in_ring = geo_test_fixtures::poly_in_ring::<f64>();
1000        assert_relative_eq!(ring.euclidean_distance(&poly_in_ring), 5.992772737231033);
1001    }
1002    #[test]
1003    // Line-Polygon test: closest point on Polygon is NOT nearest to a Line end-point
1004    fn test_line_polygon_simple() {
1005        let line = Line::from([(0.0, 0.0), (0.0, 3.0)]);
1006        let v = vec![(5.0, 1.0), (5.0, 2.0), (0.25, 1.5), (5.0, 1.0)];
1007        let poly = Polygon::new(v.into(), vec![]);
1008        assert_relative_eq!(line.euclidean_distance(&poly), 0.25);
1009    }
1010    #[test]
1011    // Line-Polygon test: Line intersects Polygon
1012    fn test_line_polygon_intersects() {
1013        let line = Line::from([(0.5, 0.0), (0.0, 3.0)]);
1014        let v = vec![(5.0, 1.0), (5.0, 2.0), (0.25, 1.5), (5.0, 1.0)];
1015        let poly = Polygon::new(v.into(), vec![]);
1016        assert_relative_eq!(line.euclidean_distance(&poly), 0.0);
1017    }
1018    #[test]
1019    // Line-Polygon test: Line contained by interior ring
1020    fn test_line_polygon_inside_ring() {
1021        let line = Line::from([(4.4, 1.5), (4.45, 1.5)]);
1022        let v = vec![(5.0, 1.0), (5.0, 2.0), (0.25, 1.0), (5.0, 1.0)];
1023        let v2 = vec![(4.5, 1.2), (4.5, 1.8), (3.5, 1.2), (4.5, 1.2)];
1024        let poly = Polygon::new(v.into(), vec![v2.into()]);
1025        assert_relative_eq!(line.euclidean_distance(&poly), 0.04999999999999982);
1026    }
1027    #[test]
1028    // LineString-Line test
1029    fn test_linestring_line_distance() {
1030        let line = Line::from([(0.0, 0.0), (0.0, 2.0)]);
1031        let ls: LineString<_> = vec![(3.0, 0.0), (1.0, 1.0), (3.0, 2.0)].into();
1032        assert_relative_eq!(ls.euclidean_distance(&line), 1.0);
1033    }
1034
1035    #[test]
1036    // Triangle-Point test: point on vertex
1037    fn test_triangle_point_on_vertex_distance() {
1038        let triangle = Triangle::from([(0.0, 0.0), (2.0, 0.0), (2.0, 2.0)]);
1039        let point = Point::new(0.0, 0.0);
1040        assert_relative_eq!(triangle.euclidean_distance(&point), 0.0);
1041    }
1042
1043    #[test]
1044    // Triangle-Point test: point on edge
1045    fn test_triangle_point_on_edge_distance() {
1046        let triangle = Triangle::from([(0.0, 0.0), (2.0, 0.0), (2.0, 2.0)]);
1047        let point = Point::new(1.5, 0.0);
1048        assert_relative_eq!(triangle.euclidean_distance(&point), 0.0);
1049    }
1050
1051    #[test]
1052    // Triangle-Point test
1053    fn test_triangle_point_distance() {
1054        let triangle = Triangle::from([(0.0, 0.0), (2.0, 0.0), (2.0, 2.0)]);
1055        let point = Point::new(2.0, 3.0);
1056        assert_relative_eq!(triangle.euclidean_distance(&point), 1.0);
1057    }
1058
1059    #[test]
1060    // Triangle-Point test: point within triangle
1061    fn test_triangle_point_inside_distance() {
1062        let triangle = Triangle::from([(0.0, 0.0), (2.0, 0.0), (2.0, 2.0)]);
1063        let point = Point::new(1.0, 0.5);
1064        assert_relative_eq!(triangle.euclidean_distance(&point), 0.0);
1065    }
1066
1067    #[test]
1068    fn convex_and_nearest_neighbour_comparison() {
1069        let ls1: LineString<f64> = vec![
1070            Coord::from((57.39453770777941, 307.60533608924663)),
1071            Coord::from((67.1800355576469, 309.6654408997451)),
1072            Coord::from((84.89693692793338, 225.5101593908847)),
1073            Coord::from((75.1114390780659, 223.45005458038628)),
1074            Coord::from((57.39453770777941, 307.60533608924663)),
1075        ]
1076        .into();
1077        let first_polygon: Polygon<f64> = Polygon::new(ls1, vec![]);
1078        let ls2: LineString<f64> = vec![
1079            Coord::from((138.11769866645008, -45.75134112915392)),
1080            Coord::from((130.50230476949187, -39.270154833870336)),
1081            Coord::from((184.94426964987397, 24.699153900578573)),
1082            Coord::from((192.55966354683218, 18.217967605294987)),
1083            Coord::from((138.11769866645008, -45.75134112915392)),
1084        ]
1085        .into();
1086        let second_polygon = Polygon::new(ls2, vec![]);
1087
1088        assert_relative_eq!(
1089            first_polygon.euclidean_distance(&second_polygon),
1090            224.35357967013238
1091        );
1092    }
1093    #[test]
1094    fn fast_path_regression() {
1095        // this test will fail if the fast path algorithm is reintroduced without being fixed
1096        let p1 = polygon!(
1097            (x: 0_f64, y: 0_f64),
1098            (x: 300_f64, y: 0_f64),
1099            (x: 300_f64, y: 100_f64),
1100            (x: 0_f64, y: 100_f64),
1101        )
1102        .orient(Direction::Default);
1103        let p2 = polygon!(
1104            (x: 100_f64, y: 150_f64),
1105            (x: 150_f64, y: 200_f64),
1106            (x: 50_f64, y: 200_f64),
1107        )
1108        .orient(Direction::Default);
1109        let p3 = polygon!(
1110            (x: 0_f64, y: 0_f64),
1111            (x: 300_f64, y: 0_f64),
1112            (x: 300_f64, y: 100_f64),
1113            (x: 0_f64, y: 100_f64),
1114        )
1115        .orient(Direction::Reversed);
1116        let p4 = polygon!(
1117            (x: 100_f64, y: 150_f64),
1118            (x: 150_f64, y: 200_f64),
1119            (x: 50_f64, y: 200_f64),
1120        )
1121        .orient(Direction::Reversed);
1122        assert_eq!(p1.euclidean_distance(&p2), 50.0f64);
1123        assert_eq!(p3.euclidean_distance(&p4), 50.0f64);
1124        assert_eq!(p1.euclidean_distance(&p4), 50.0f64);
1125        assert_eq!(p2.euclidean_distance(&p3), 50.0f64);
1126    }
1127    #[test]
1128    fn all_types_geometry_collection_test() {
1129        let p = Point::new(0.0, 0.0);
1130        let line = Line::from([(-1.0, -1.0), (-2.0, -2.0)]);
1131        let ls = LineString::from(vec![(0.0, 0.0), (1.0, 10.0), (2.0, 0.0)]);
1132        let poly = Polygon::new(
1133            LineString::from(vec![(0.0, 0.0), (1.0, 10.0), (2.0, 0.0), (0.0, 0.0)]),
1134            vec![],
1135        );
1136        let tri = Triangle::from([(0.0, 0.0), (1.0, 10.0), (2.0, 0.0)]);
1137        let rect = Rect::new((0.0, 0.0), (-1.0, -1.0));
1138
1139        let ls1 = LineString::from(vec![(0.0, 0.0), (1.0, 10.0), (2.0, 0.0), (0.0, 0.0)]);
1140        let ls2 = LineString::from(vec![(3.0, 0.0), (4.0, 10.0), (5.0, 0.0), (3.0, 0.0)]);
1141        let p1 = Polygon::new(ls1, vec![]);
1142        let p2 = Polygon::new(ls2, vec![]);
1143        let mpoly = MultiPolygon::new(vec![p1, p2]);
1144
1145        let v = vec![
1146            Point::new(0.0, 10.0),
1147            Point::new(1.0, 1.0),
1148            Point::new(10.0, 0.0),
1149            Point::new(1.0, -1.0),
1150            Point::new(0.0, -10.0),
1151            Point::new(-1.0, -1.0),
1152            Point::new(-10.0, 0.0),
1153            Point::new(-1.0, 1.0),
1154            Point::new(0.0, 10.0),
1155        ];
1156        let mpoint = MultiPoint::new(v);
1157
1158        let v1 = LineString::from(vec![(0.0, 0.0), (1.0, 10.0)]);
1159        let v2 = LineString::from(vec![(1.0, 10.0), (2.0, 0.0), (3.0, 1.0)]);
1160        let mls = MultiLineString::new(vec![v1, v2]);
1161
1162        let gc = GeometryCollection(vec![
1163            Geometry::Point(p),
1164            Geometry::Line(line),
1165            Geometry::LineString(ls),
1166            Geometry::Polygon(poly),
1167            Geometry::MultiPoint(mpoint),
1168            Geometry::MultiLineString(mls),
1169            Geometry::MultiPolygon(mpoly),
1170            Geometry::Triangle(tri),
1171            Geometry::Rect(rect),
1172        ]);
1173
1174        let test_p = Point::new(50., 50.);
1175        assert_relative_eq!(test_p.euclidean_distance(&gc), 60.959002616512684);
1176
1177        let test_multipoint = MultiPoint::new(vec![test_p]);
1178        assert_relative_eq!(test_multipoint.euclidean_distance(&gc), 60.959002616512684);
1179
1180        let test_line = Line::from([(50., 50.), (60., 60.)]);
1181        assert_relative_eq!(test_line.euclidean_distance(&gc), 60.959002616512684);
1182
1183        let test_ls = LineString::from(vec![(50., 50.), (60., 60.), (70., 70.)]);
1184        assert_relative_eq!(test_ls.euclidean_distance(&gc), 60.959002616512684);
1185
1186        let test_mls = MultiLineString::new(vec![test_ls]);
1187        assert_relative_eq!(test_mls.euclidean_distance(&gc), 60.959002616512684);
1188
1189        let test_poly = Polygon::new(
1190            LineString::from(vec![
1191                (50., 50.),
1192                (60., 50.),
1193                (60., 60.),
1194                (55., 55.),
1195                (50., 50.),
1196            ]),
1197            vec![],
1198        );
1199        assert_relative_eq!(test_poly.euclidean_distance(&gc), 60.959002616512684);
1200
1201        let test_multipoly = MultiPolygon::new(vec![test_poly]);
1202        assert_relative_eq!(test_multipoly.euclidean_distance(&gc), 60.959002616512684);
1203
1204        let test_tri = Triangle::from([(50., 50.), (60., 50.), (55., 55.)]);
1205        assert_relative_eq!(test_tri.euclidean_distance(&gc), 60.959002616512684);
1206
1207        let test_rect = Rect::new(coord! { x: 50., y: 50. }, coord! { x: 60., y: 60. });
1208        assert_relative_eq!(test_rect.euclidean_distance(&gc), 60.959002616512684);
1209
1210        let test_gc = GeometryCollection(vec![Geometry::Rect(test_rect)]);
1211        assert_relative_eq!(test_gc.euclidean_distance(&gc), 60.959002616512684);
1212    }
1213}
geo/algorithm/euclidean_distance.rs

geo/algorithm/
euclidean_distance.rs
