geo/algorithm/
interior_point.rs

1use std::cmp::{Ordering, Reverse};
2
3use crate::algorithm::{
4    bounding_rect::BoundingRect, centroid::Centroid, coords_iter::CoordsIter,
5    dimensions::HasDimensions, euclidean_distance::EuclideanDistance,
6    line_intersection::LineIntersection, lines_iter::LinesIter, relate::Relate,
7};
8use crate::geometry::*;
9use crate::sweep::{Intersections, SweepPoint};
10use crate::GeoFloat;
11
12/// Calculation of interior points.
13
14/// An interior point is a point that's guaranteed to intersect a given geometry, and will be
15/// strictly on the interior of the geometry if possible, or on the edge if the geometry has zero
16/// area. A best effort will additionally be made to locate the point reasonably centrally.
17///
18/// For polygons, this point is located by drawing a line that approximately subdivides the
19/// bounding box around the polygon in half, intersecting it with the polygon, then calculating
20/// the midpoint of the longest line produced by the intersection. For lines, the non-endpoint
21/// vertex closest to the line's centroid is returned if the line has interior points, or an
22/// endpoint is returned otherwise.
23///
24/// For multi-geometries or collections, the interior points of the constituent components are
25/// calculated, and one of those is returned (for MultiPolygons, it's the point that's the midpoint
26/// of the longest intersection of the intersection lines of any of the constituent polygons, as
27/// described above; for all others, the interior point closest to the collection's centroid is
28/// used).
29///
30/// # Examples
31///
32/// ```
33/// use geo::InteriorPoint;
34/// use geo::{point, polygon};
35///
36/// // rhombus shaped polygon
37/// let polygon = polygon![
38///     (x: -2., y: 1.),
39///     (x: 1., y: 3.),
40///     (x: 4., y: 1.),
41///     (x: 1., y: -1.),
42///     (x: -2., y: 1.),
43/// ];
44///
45/// assert_eq!(
46///     Some(point!(x: 1., y: 2.)),
47///     polygon.interior_point(),
48/// );
49/// ```
50pub trait InteriorPoint {
51    type Output;
52
53    /// Calculates a representative point inside the `Geometry`
54    ///
55    /// # Examples
56    ///
57    /// ```
58    /// use geo::InteriorPoint;
59    /// use geo::{line_string, point};
60    ///
61    /// let line_string = line_string![
62    ///     (x: 40.02f64, y: 116.34),
63    ///     (x: 40.02f64, y: 118.23),
64    ///     (x: 40.02f64, y: 120.15),
65    /// ];
66    ///
67    /// assert_eq!(
68    ///     Some(point!(x: 40.02, y: 118.23)),
69    ///     line_string.interior_point(),
70    /// );
71    /// ```
72    fn interior_point(&self) -> Self::Output;
73}
74
75impl<T> InteriorPoint for Line<T>
76where
77    T: GeoFloat,
78{
79    type Output = Point<T>;
80
81    fn interior_point(&self) -> Self::Output {
82        // the midpoint of the line isn't guaranteed to actually have an `intersects()`
83        // relationship with the line due to floating point rounding, so just use the start point
84        self.start_point()
85    }
86}
87
88impl<T> InteriorPoint for LineString<T>
89where
90    T: GeoFloat,
91{
92    type Output = Option<Point<T>>;
93
94    // The interior point of a LineString the non-endpoint vertex closest to the centroid if any,
95    // or the start point if there are no non-endpoint vertices
96    fn interior_point(&self) -> Self::Output {
97        match self.0.len() {
98            0 => None,
99            // for linestrings of length 2, as with lines, the calculated midpoint might not lie
100            // on the line, so just use the start point
101            1 | 2 => Some(self.0[0].into()),
102            _ => {
103                let centroid = self
104                    .centroid()
105                    .expect("expected centroid for non-empty linestring");
106                self.0[1..(self.0.len() - 1)]
107                    .iter()
108                    .map(|coord| {
109                        let pt = Point::from(*coord);
110                        (pt, pt.euclidean_distance(&centroid))
111                    })
112                    .min_by(|a, b| a.1.partial_cmp(&b.1).unwrap_or(Ordering::Less))
113                    .map(|(pt, _distance)| pt)
114            }
115        }
116    }
117}
118
119impl<T> InteriorPoint for MultiLineString<T>
120where
121    T: GeoFloat,
122{
123    type Output = Option<Point<T>>;
124
125    /// The interior point of a MultiLineString is, of the interior points of all the constituent
126    /// LineStrings, the one closest to the centroid of the MultiLineString
127    fn interior_point(&self) -> Self::Output {
128        if let Some(centroid) = self.centroid() {
129            self.iter()
130                .filter_map(|linestring| {
131                    linestring
132                        .interior_point()
133                        .map(|pt| (pt, pt.euclidean_distance(&centroid)))
134                })
135                .min_by(|a, b| a.1.partial_cmp(&b.1).unwrap_or(Ordering::Less))
136                .map(|(pt, _distance)| pt)
137        } else {
138            None
139        }
140    }
141}
142
143fn polygon_interior_point_with_segment_length<T: GeoFloat>(
144    polygon: &Polygon<T>,
145) -> Option<(Point<T>, T)> {
146    // special-case a one-point polygon since this algorithm won't otherwise support it
147    if polygon.exterior().0.len() == 1 {
148        return Some((polygon.exterior().0[0].into(), T::zero()));
149    }
150
151    let two = T::one() + T::one();
152
153    let bounds = polygon.bounding_rect()?;
154
155    // use the midpoint of the bounds to scan, unless that happens to match any vertices from
156    // polygon; if it does, perturb the line a bit by averaging with the Y coordinate of the
157    // next-closest-to-center vertex if possible, to reduce the likelihood of collinear
158    // intersections
159    let mut y_mid = (bounds.min().y + bounds.max().y) / two;
160    if polygon.coords_iter().any(|coord| coord.y == y_mid) {
161        let next_closest = polygon
162            .coords_iter()
163            .filter_map(|coord| {
164                if coord.y == y_mid {
165                    None
166                } else {
167                    Some((coord.y, (coord.y - y_mid).abs()))
168                }
169            })
170            .min_by(|a, b| a.1.partial_cmp(&b.1).unwrap_or(Ordering::Less));
171        if let Some((closest, _)) = next_closest {
172            y_mid = (y_mid + closest) / two
173        }
174    };
175
176    let scan_line = Line::new(
177        Coord {
178            x: bounds.min().x,
179            y: y_mid,
180        },
181        Coord {
182            x: bounds.max().x,
183            y: y_mid,
184        },
185    );
186
187    let lines = polygon.lines_iter().chain(std::iter::once(scan_line));
188
189    let mut intersections: Vec<SweepPoint<T>> = Vec::new();
190    for (l1, l2, inter) in Intersections::from_iter(lines) {
191        if !(l1 == scan_line || l2 == scan_line) {
192            continue;
193        }
194        match inter {
195            LineIntersection::Collinear { intersection } => {
196                intersections.push(SweepPoint::from(intersection.start));
197                intersections.push(SweepPoint::from(intersection.end));
198            }
199            LineIntersection::SinglePoint { intersection, .. } => {
200                intersections.push(SweepPoint::from(intersection));
201            }
202        }
203    }
204    intersections.sort();
205
206    let mut segments = Vec::new();
207    let mut intersections_iter = intersections.iter().peekable();
208    while let (Some(start), Some(end)) = (intersections_iter.next(), intersections_iter.peek()) {
209        let length = end.x - start.x;
210        let midpoint = Point::new((start.x + end.x) / two, y_mid);
211        segments.push((midpoint, length));
212    }
213    segments.sort_by(|a, b| b.1.partial_cmp(&a.1).unwrap_or(Ordering::Less));
214
215    for (midpoint, segment_length) in segments {
216        // some pairs of consecutive points traveling east-west will bound segments inside the
217        // polygon, and some outside; confirm that this is the former
218        let relation = polygon.relate(&midpoint);
219        if relation.is_intersects() {
220            return Some((
221                midpoint,
222                if relation.is_contains() {
223                    segment_length
224                } else {
225                    // if our point is on the boundary, it must be because this is a zero-area
226                    // polygon, so if we're being called from a multipolygon context, we want this
227                    // option to be down-ranked as compared to other polygons that might have
228                    // non-zero area
229                    T::zero()
230                },
231            ));
232        }
233    }
234    // if we've gotten this far with no luck, return any vertex point, if there are any
235    polygon
236        .coords_iter()
237        .next()
238        .map(|coord| (coord.into(), T::zero()))
239}
240
241impl<T> InteriorPoint for Polygon<T>
242where
243    T: GeoFloat,
244{
245    type Output = Option<Point<T>>;
246
247    fn interior_point(&self) -> Self::Output {
248        polygon_interior_point_with_segment_length(self).map(|(point, _length)| point)
249    }
250}
251
252impl<T> InteriorPoint for MultiPolygon<T>
253where
254    T: GeoFloat,
255{
256    type Output = Option<Point<T>>;
257
258    fn interior_point(&self) -> Self::Output {
259        let segments = self
260            .iter()
261            .filter_map(polygon_interior_point_with_segment_length);
262        segments
263            .min_by(|a, b| b.1.partial_cmp(&a.1).unwrap_or(Ordering::Less))
264            .map(|(point, _length)| point)
265    }
266}
267
268impl<T> InteriorPoint for Rect<T>
269where
270    T: GeoFloat,
271{
272    type Output = Point<T>;
273
274    fn interior_point(&self) -> Self::Output {
275        self.center().into()
276    }
277}
278
279impl<T> InteriorPoint for Point<T>
280where
281    T: GeoFloat,
282{
283    type Output = Point<T>;
284
285    fn interior_point(&self) -> Self::Output {
286        *self
287    }
288}
289
290///
291/// ```
292/// use geo::InteriorPoint;
293/// use geo::{MultiPoint, Point};
294///
295/// let empty: Vec<Point> = Vec::new();
296/// let empty_multi_points: MultiPoint<_> = empty.into();
297/// assert_eq!(empty_multi_points.interior_point(), None);
298///
299/// let points: MultiPoint<_> = vec![(5., 1.), (1., 3.), (3., 2.)].into();
300/// assert_eq!(points.interior_point(), Some(Point::new(3., 2.)));
301/// ```
302impl<T> InteriorPoint for MultiPoint<T>
303where
304    T: GeoFloat,
305{
306    type Output = Option<Point<T>>;
307
308    fn interior_point(&self) -> Self::Output {
309        if let Some(centroid) = self.centroid() {
310            self.iter()
311                .map(|pt| (pt, pt.euclidean_distance(&centroid)))
312                .min_by(|a, b| a.1.partial_cmp(&b.1).unwrap_or(Ordering::Less))
313                .map(|(pt, _distance)| *pt)
314        } else {
315            None
316        }
317    }
318}
319
320impl<T> InteriorPoint for Geometry<T>
321where
322    T: GeoFloat,
323{
324    type Output = Option<Point<T>>;
325
326    crate::geometry_delegate_impl! {
327        fn interior_point(&self) -> Self::Output;
328    }
329}
330
331impl<T> InteriorPoint for GeometryCollection<T>
332where
333    T: GeoFloat,
334{
335    type Output = Option<Point<T>>;
336
337    fn interior_point(&self) -> Self::Output {
338        if let Some(centroid) = self.centroid() {
339            self.iter()
340                .filter_map(|geom| {
341                    geom.interior_point().map(|pt| {
342                        (
343                            pt,
344                            // maximize dimensions, minimize distance
345                            (Reverse(geom.dimensions()), pt.euclidean_distance(&centroid)),
346                        )
347                    })
348                })
349                .min_by(|a, b| a.1.partial_cmp(&b.1).unwrap_or(Ordering::Less))
350                .map(|(pt, _distance)| pt)
351        } else {
352            None
353        }
354    }
355}
356
357impl<T> InteriorPoint for Triangle<T>
358where
359    T: GeoFloat,
360{
361    type Output = Point<T>;
362
363    fn interior_point(&self) -> Self::Output {
364        self.centroid()
365    }
366}
367
368#[cfg(test)]
369mod test {
370    use super::*;
371    use crate::{
372        algorithm::{contains::Contains, intersects::Intersects},
373        coord, line_string, point, polygon,
374    };
375
376    /// small helper to create a coordinate
377    fn c<T: GeoFloat>(x: T, y: T) -> Coord<T> {
378        coord! { x: x, y: y }
379    }
380
381    /// small helper to create a point
382    fn p<T: GeoFloat>(x: T, y: T) -> Point<T> {
383        point! { x: x, y: y }
384    }
385
386    // Tests: InteriorPoint of LineString
387    #[test]
388    fn empty_linestring_test() {
389        let linestring: LineString<f32> = line_string![];
390        let interior_point = linestring.interior_point();
391        assert!(interior_point.is_none());
392    }
393    #[test]
394    fn linestring_one_point_test() {
395        let coord = coord! {
396            x: 40.02f64,
397            y: 116.34,
398        };
399        let linestring = line_string![coord];
400        let interior_point = linestring.interior_point();
401        assert_eq!(interior_point, Some(Point::from(coord)));
402    }
403    #[test]
404    fn linestring_test() {
405        let linestring = line_string![
406            (x: 1., y: 1.),
407            (x: 7., y: 1.),
408            (x: 8., y: 1.),
409            (x: 9., y: 1.),
410            (x: 10., y: 1.),
411            (x: 11., y: 1.)
412        ];
413        assert_eq!(linestring.interior_point(), Some(point!(x: 7., y: 1. )));
414    }
415    #[test]
416    fn linestring_with_repeated_point_test() {
417        let l1 = LineString::from(vec![p(1., 1.), p(1., 1.), p(1., 1.)]);
418        assert_eq!(l1.interior_point(), Some(p(1., 1.)));
419
420        let l2 = LineString::from(vec![p(2., 2.), p(2., 2.), p(2., 2.)]);
421        let mls = MultiLineString::new(vec![l1, l2]);
422        assert_eq!(mls.interior_point(), Some(p(1., 1.)));
423    }
424    // Tests: InteriorPoint of MultiLineString
425    #[test]
426    fn empty_multilinestring_test() {
427        let mls: MultiLineString = MultiLineString::new(vec![]);
428        let interior_point = mls.interior_point();
429        assert!(interior_point.is_none());
430    }
431    #[test]
432    fn multilinestring_with_empty_line_test() {
433        let mls: MultiLineString = MultiLineString::new(vec![line_string![]]);
434        let interior_point = mls.interior_point();
435        assert!(interior_point.is_none());
436    }
437    #[test]
438    fn multilinestring_length_0_test() {
439        let coord = coord! {
440            x: 40.02f64,
441            y: 116.34,
442        };
443        let mls: MultiLineString = MultiLineString::new(vec![
444            line_string![coord],
445            line_string![coord],
446            line_string![coord],
447        ]);
448        assert_relative_eq!(mls.interior_point().unwrap(), Point::from(coord));
449    }
450    #[test]
451    fn multilinestring_one_line_test() {
452        let linestring = line_string![
453            (x: 1., y: 1.),
454            (x: 7., y: 1.),
455            (x: 8., y: 1.),
456            (x: 9., y: 1.),
457            (x: 10., y: 1.),
458            (x: 11., y: 1.)
459        ];
460        let mls: MultiLineString = MultiLineString::new(vec![linestring]);
461        assert_relative_eq!(mls.interior_point().unwrap(), point! { x: 7., y: 1. });
462    }
463    #[test]
464    fn multilinestring_test() {
465        let v1 = line_string![(x: 0.0, y: 0.0), (x: 1.0, y: 10.0)];
466        let v2 = line_string![(x: 1.0, y: 10.0), (x: 2.0, y: 0.0), (x: 3.0, y: 1.0)];
467        let v3 = line_string![(x: -12.0, y: -100.0), (x: 7.0, y: 8.0)];
468        let mls = MultiLineString::new(vec![v1, v2, v3]);
469        assert_eq!(mls.interior_point().unwrap(), point![x: 0., y: 0.]);
470    }
471    // Tests: InteriorPoint of Polygon
472    #[test]
473    fn empty_polygon_test() {
474        let poly: Polygon<f32> = polygon![];
475        assert!(poly.interior_point().is_none());
476    }
477    #[test]
478    fn polygon_one_point_test() {
479        let p = point![ x: 2., y: 1. ];
480        let v = Vec::new();
481        let linestring = line_string![p.0];
482        let poly = Polygon::new(linestring, v);
483        assert_relative_eq!(poly.interior_point().unwrap(), p);
484    }
485
486    #[test]
487    fn polygon_test() {
488        let poly = polygon![
489            (x: 0., y: 0.),
490            (x: 2., y: 0.),
491            (x: 2., y: 2.),
492            (x: 0., y: 2.),
493            (x: 0., y: 0.)
494        ];
495        assert_relative_eq!(poly.interior_point().unwrap(), point![x:1., y:1.]);
496    }
497    #[test]
498    fn polygon_hole_test() {
499        // hexagon
500        let ls1 = LineString::from(vec![
501            (5.0, 1.0),
502            (4.0, 2.0),
503            (4.0, 3.0),
504            (5.0, 4.0),
505            (6.0, 4.0),
506            (7.0, 3.0),
507            (7.0, 2.0),
508            (6.0, 1.0),
509            (5.0, 1.0),
510        ]);
511
512        let ls2 = LineString::from(vec![(5.0, 1.3), (5.5, 2.0), (6.0, 1.3), (5.0, 1.3)]);
513
514        let ls3 = LineString::from(vec![(5., 2.3), (5.5, 3.0), (6., 2.3), (5., 2.3)]);
515
516        let p1 = Polygon::new(ls1, vec![ls2, ls3]);
517        let interior_point = p1.interior_point().unwrap();
518        assert!(p1.contains(&interior_point));
519        assert_relative_eq!(interior_point, point!(x: 4.571428571428571, y: 2.5));
520    }
521    #[test]
522    fn flat_polygon_test() {
523        let poly = Polygon::new(
524            LineString::from(vec![p(0., 1.), p(1., 1.), p(0., 1.)]),
525            vec![],
526        );
527        assert_eq!(poly.interior_point(), Some(p(0.5, 1.)));
528    }
529    #[test]
530    fn diagonal_flat_polygon_test() {
531        // the regular intersection approach happens to not produce a point that intersects the
532        // polygon given these particular start values, so this tests falling back to a vertex
533        let start: Coord<f64> = Coord {
534            x: 0.632690318327692,
535            y: 0.08104532928154995,
536        };
537        let end: Coord<f64> = Coord {
538            x: 0.4685039949468325,
539            y: 0.31750332644855794,
540        };
541        let poly = Polygon::new(LineString::new(vec![start, end, start]), vec![]);
542
543        assert_eq!(poly.interior_point(), Some(start.into()));
544    }
545    #[test]
546    fn polygon_vertex_on_median() {
547        let poly = Polygon::new(
548            LineString::from(vec![
549                (0.5, 1.0),
550                (0.5, 0.5),
551                (0.0, 0.5),
552                (0.0, 0.0),
553                (1.0, 0.0),
554                (1.0, 1.0),
555                (0.5, 1.0),
556            ]),
557            vec![],
558        );
559        let interior_point = poly.interior_point().unwrap();
560        assert_eq!(&interior_point, &p(0.75, 0.75));
561    }
562    #[test]
563    fn multi_poly_with_flat_polygon_test() {
564        let poly = Polygon::new(
565            LineString::from(vec![p(0., 0.), p(1., 0.), p(0., 0.)]),
566            vec![],
567        );
568        let multipoly = MultiPolygon::new(vec![poly]);
569        assert_eq!(multipoly.interior_point(), Some(p(0.5, 0.)));
570    }
571    #[test]
572    fn multi_poly_with_multiple_flat_polygon_test() {
573        let p1 = Polygon::new(
574            LineString::from(vec![p(1., 1.), p(1., 3.), p(1., 1.)]),
575            vec![],
576        );
577        let p2 = Polygon::new(
578            LineString::from(vec![p(2., 2.), p(6., 2.), p(2., 2.)]),
579            vec![],
580        );
581        let multipoly = MultiPolygon::new(vec![p1, p2]);
582        let interior = multipoly.interior_point().unwrap();
583        assert_eq!(&interior, &p(1., 2.));
584        assert!(multipoly.intersects(&interior));
585    }
586    #[test]
587    fn multi_poly_with_only_points_test() {
588        let p1 = Polygon::new(
589            LineString::from(vec![p(1., 1.), p(1., 1.), p(1., 1.)]),
590            vec![],
591        );
592        assert_eq!(p1.interior_point(), Some(p(1., 1.)));
593        let p2 = Polygon::new(
594            LineString::from(vec![p(2., 2.), p(2., 2.), p(2., 2.)]),
595            vec![],
596        );
597        let multipoly = MultiPolygon::new(vec![p1, p2]);
598        let interior_point = multipoly.interior_point().unwrap();
599        assert_eq!(multipoly.interior_point(), Some(p(1.0, 1.0)));
600        assert!(multipoly.intersects(&interior_point));
601    }
602    #[test]
603    fn multi_poly_with_one_ring_and_one_real_poly() {
604        // if the multipolygon is composed of a 'normal' polygon (with an area not null)
605        // and a ring (a polygon with a null area)
606        // the interior_point of the multipolygon is the interior_point of the 'normal' polygon
607        let normal = Polygon::new(
608            LineString::from(vec![p(1., 1.), p(1., 3.), p(3., 1.), p(1., 1.)]),
609            vec![],
610        );
611        let flat = Polygon::new(
612            LineString::from(vec![p(2., 2.), p(6., 2.), p(2., 2.)]),
613            vec![],
614        );
615        let multipoly = MultiPolygon::new(vec![normal.clone(), flat]);
616        assert_eq!(multipoly.interior_point(), normal.interior_point());
617    }
618    #[test]
619    fn polygon_flat_interior_test() {
620        let poly = Polygon::new(
621            LineString::from(vec![p(0., 0.), p(0., 1.), p(1., 1.), p(1., 0.), p(0., 0.)]),
622            vec![LineString::from(vec![
623                p(0.1, 0.1),
624                p(0.1, 0.9),
625                p(0.1, 0.1),
626            ])],
627        );
628        assert_eq!(poly.interior_point(), Some(p(0.55, 0.5)));
629    }
630    #[test]
631    fn empty_interior_polygon_test() {
632        let poly = Polygon::new(
633            LineString::from(vec![p(0., 0.), p(0., 1.), p(1., 1.), p(1., 0.), p(0., 0.)]),
634            vec![LineString::new(vec![])],
635        );
636        assert_eq!(poly.interior_point(), Some(p(0.5, 0.5)));
637    }
638    #[test]
639    fn polygon_ring_test() {
640        let square = LineString::from(vec![p(0., 0.), p(0., 1.), p(1., 1.), p(1., 0.), p(0., 0.)]);
641        let poly = Polygon::new(square.clone(), vec![square]);
642        let interior_point = poly.interior_point().unwrap();
643        assert_eq!(&interior_point, &p(0.0, 0.5));
644        assert!(poly.intersects(&interior_point));
645        assert!(!poly.contains(&interior_point)); // there's no interior so won't be "contains"
646    }
647    #[test]
648    fn polygon_cell_test() {
649        // test the interior_point of polygon with a null area
650        // this one a polygon with 2 interior polygon that makes a partition of the exterior
651        let square = LineString::from(vec![p(0., 0.), p(0., 2.), p(2., 2.), p(2., 0.), p(0., 0.)]);
652        let bottom = LineString::from(vec![p(0., 0.), p(2., 0.), p(2., 1.), p(0., 1.), p(0., 0.)]);
653        let top = LineString::from(vec![p(0., 1.), p(2., 1.), p(2., 2.), p(0., 2.), p(0., 1.)]);
654        let poly = Polygon::new(square, vec![top, bottom]);
655        let interior_point = poly.interior_point().unwrap();
656        assert!(poly.intersects(&interior_point));
657        assert!(!poly.contains(&interior_point));
658    }
659    // Tests: InteriorPoint of MultiPolygon
660    #[test]
661    fn empty_multipolygon_polygon_test() {
662        assert!(MultiPolygon::<f64>::new(Vec::new())
663            .interior_point()
664            .is_none());
665    }
666
667    #[test]
668    fn multipolygon_one_polygon_test() {
669        let linestring =
670            LineString::from(vec![p(0., 0.), p(2., 0.), p(2., 2.), p(0., 2.), p(0., 0.)]);
671        let poly = Polygon::new(linestring, Vec::new());
672        assert_eq!(
673            MultiPolygon::new(vec![poly]).interior_point(),
674            Some(p(1., 1.))
675        );
676    }
677    #[test]
678    fn multipolygon_two_polygons_test() {
679        let linestring =
680            LineString::from(vec![p(2., 1.), p(5., 1.), p(5., 3.), p(2., 3.), p(2., 1.)]);
681        let poly1 = Polygon::new(linestring, Vec::new());
682        let linestring =
683            LineString::from(vec![p(7., 1.), p(8., 1.), p(8., 2.), p(7., 2.), p(7., 1.)]);
684        let poly2 = Polygon::new(linestring, Vec::new());
685        let multipoly = MultiPolygon::new(vec![poly1, poly2]);
686        let interior_point = multipoly.interior_point().unwrap();
687        assert_relative_eq!(interior_point, point![x: 3.5, y: 2.]);
688        assert!(multipoly.contains(&interior_point));
689    }
690    #[test]
691    fn multipolygon_two_polygons_of_opposite_clockwise_test() {
692        let linestring = LineString::from(vec![(0., 0.), (2., 0.), (2., 2.), (0., 2.), (0., 0.)]);
693        let poly1 = Polygon::new(linestring, Vec::new());
694        let linestring = LineString::from(vec![(0., 0.), (-2., 0.), (-2., 2.), (0., 2.), (0., 0.)]);
695        let poly2 = Polygon::new(linestring, Vec::new());
696        let multipoly = MultiPolygon::new(vec![poly1, poly2]);
697        let interior_point = multipoly.interior_point().unwrap();
698        assert_relative_eq!(interior_point, point![x: 1.0, y: 1.0]);
699        assert!(multipoly.contains(&interior_point));
700    }
701    #[test]
702    fn bounding_rect_test() {
703        let bounding_rect = Rect::new(coord! { x: 0., y: 50. }, coord! { x: 4., y: 100. });
704        let point = point![x: 2., y: 75.];
705        assert_eq!(point, bounding_rect.interior_point());
706    }
707    #[test]
708    fn line_test() {
709        let line1 = Line::new(c(0., 1.), c(1., 3.));
710        assert_eq!(line1.interior_point(), point![x: 0., y: 1.]);
711    }
712    #[test]
713    fn collection_test() {
714        let p0 = point!(x: 0.0, y: 0.0);
715        let p1 = point!(x: 2.0, y: 0.0);
716        let p2 = point!(x: 2.0, y: 2.0);
717        let p3 = point!(x: 0.0, y: 2.0);
718
719        let multi_point = MultiPoint::new(vec![p0, p1, p2, p3]);
720        assert_eq!(
721            multi_point.interior_point().unwrap(),
722            point!(x: 0.0, y: 0.0)
723        );
724    }
725    #[test]
726    fn mixed_collection_test() {
727        let linestring =
728            LineString::from(vec![p(0., 1.), p(0., 0.), p(1., 0.), p(1., 1.), p(0., 1.)]);
729        let poly1 = Polygon::new(linestring, Vec::new());
730        let linestring = LineString::from(vec![
731            p(10., 1.),
732            p(10., 0.),
733            p(11., 0.),
734            p(11., 1.),
735            p(10., 1.),
736        ]);
737        let poly2 = Polygon::new(linestring, Vec::new());
738
739        let high_dimension_shapes = GeometryCollection::new_from(vec![poly1.into(), poly2.into()]);
740
741        let mut mixed_shapes = high_dimension_shapes.clone();
742        mixed_shapes.0.push(Point::new(5_f64, 0_f64).into());
743        mixed_shapes.0.push(Point::new(5_f64, 1_f64).into());
744
745        // lower-dimensional shapes shouldn't affect interior point if higher-dimensional shapes
746        // are present, even if the low-d ones are closer to the centroid
747        assert_eq!(
748            high_dimension_shapes.interior_point().unwrap(),
749            mixed_shapes.interior_point().unwrap()
750        )
751    }
752    #[test]
753    fn triangles() {
754        // boring triangle
755        assert_eq!(
756            Triangle::new(c(0., 0.), c(3., 0.), c(1.5, 3.)).interior_point(),
757            point!(x: 1.5, y: 1.0)
758        );
759
760        // flat triangle
761        assert_eq!(
762            Triangle::new(c(0., 0.), c(3., 0.), c(1., 0.)).interior_point(),
763            point!(x: 1.5, y: 0.0)
764        );
765
766        // flat triangle that's not axis-aligned
767        assert_eq!(
768            Triangle::new(c(0., 0.), c(3., 3.), c(1., 1.)).interior_point(),
769            point!(x: 1.5, y: 1.5)
770        );
771
772        // triangle with some repeated points
773        assert_eq!(
774            Triangle::new(c(0., 0.), c(0., 0.), c(1., 0.)).interior_point(),
775            point!(x: 0.5, y: 0.0)
776        );
777
778        // triangle with all repeated points
779        assert_eq!(
780            Triangle::new(c(0., 0.5), c(0., 0.5), c(0., 0.5)).interior_point(),
781            point!(x: 0., y: 0.5)
782        )
783    }
784
785    #[test]
786    fn degenerate_triangle_like_ring() {
787        let triangle = Triangle::new(c(0., 0.), c(1., 1.), c(2., 2.));
788        let poly: Polygon<_> = triangle.into();
789
790        let line = Line::new(c(0., 1.), c(1., 3.));
791
792        let g1 = GeometryCollection::new_from(vec![triangle.into(), line.into()]);
793        let g2 = GeometryCollection::new_from(vec![poly.into(), line.into()]);
794
795        let pt1 = g1.interior_point().unwrap();
796        let pt2 = g2.interior_point().unwrap();
797        // triangle and polygon have differing interior-point implementations, so we won't get the
798        // same point with both approaches, but both should produce points that are interior to
799        // either representation
800        assert!(g1.intersects(&pt1));
801        assert!(g1.intersects(&pt2));
802        assert!(g2.intersects(&pt1));
803        assert!(g2.intersects(&pt2));
804    }
805
806    #[test]
807    fn degenerate_rect_like_ring() {
808        let rect = Rect::new(c(0., 0.), c(0., 4.));
809        let poly: Polygon<_> = rect.into();
810
811        let line = Line::new(c(0., 1.), c(1., 3.));
812
813        let g1 = GeometryCollection::new_from(vec![rect.into(), line.into()]);
814        let g2 = GeometryCollection::new_from(vec![poly.into(), line.into()]);
815        assert_eq!(g1.interior_point(), g2.interior_point());
816    }
817
818    #[test]
819    fn rectangles() {
820        // boring rect
821        assert_eq!(
822            Rect::new(c(0., 0.), c(4., 4.)).interior_point(),
823            point!(x: 2.0, y: 2.0)
824        );
825
826        // flat rect
827        assert_eq!(
828            Rect::new(c(0., 0.), c(4., 0.)).interior_point(),
829            point!(x: 2.0, y: 0.0)
830        );
831
832        // rect with all repeated points
833        assert_eq!(
834            Rect::new(c(4., 4.), c(4., 4.)).interior_point(),
835            point!(x: 4., y: 4.)
836        );
837
838        // collection with rect
839        let collection = GeometryCollection::new_from(vec![
840            p(0., 0.).into(),
841            p(6., 0.).into(),
842            p(6., 6.).into(),
843        ]);
844        // check collection
845        assert_eq!(collection.interior_point().unwrap(), point!(x: 6., y: 0.));
846    }
847}
geo/algorithm/interior_point.rs

geo/algorithm/
interior_point.rs
