geo_validator/
lib.rs

1#![allow(clippy::float_cmp)]
2
3use byteorder::{ByteOrder, NativeEndian};
4use geo::algorithm::contains::Contains;
5use geo::algorithm::intersects::Intersects;
6use geo_types::{Coordinate, Line, LineString, MultiPolygon, Point, Polygon};
7use linked_hash_map::LinkedHashMap;
8use num_traits;
9use std::hash::{Hash, Hasher};
10
11/// Violations of the OGC rules for polygon validity
12/// This also includes usage of NaN or Infinite floating point values
13///
14pub struct ValidationErrors<T>
15where
16    T: num_traits::Float,
17{
18    /// Whether the polygon is valid or not
19    pub valid: bool,
20    /// Whether the polygon has less than three points
21    pub has_less_than_three_points: bool,
22    /// Whether the polygon is actually a multipolygon
23    pub is_multi_polygon: bool,
24    /// NaN/Infinite floating point values
25    pub unsupported_floating_point_values: Vec<T>,
26    /// Rings of the polygon that have not been closed
27    pub open_rings: Vec<LineString<T>>,
28    /// Holes in the polygon that intersect the outer ring of another inner ring
29    /// (they may, however, share points)
30    pub ring_intersects_other_ring: Vec<Coordinate<T>>,
31    /// Coordinates where self intersection occurs
32    pub self_intersections: Vec<Coordinate<T>>,
33    /// Points that touch a line
34    pub point_touching_line: Vec<Coordinate<T>>,
35    /// Points repeated in a single ring
36    pub repeated_points: Vec<Coordinate<T>>,
37}
38
39pub trait Validate<T>
40where
41    T: num_traits::Float,
42{
43    /// Validate a Multipolygon/Polygon Geometry according to the OGC rules
44    ///
45    /// This function is non-trivial from a computational perspective.
46    /// It returns `false` at the first point it hits a violation of
47    /// the OCG rules for a polygon.
48    ///
49    /// * A polygon may not have less than three points
50    /// * A polygon may not have any unclosed rings
51    /// * A polygon may not be a multi-polygon (all inner rings must be contained by the outer ring)
52    /// * No ring in the polygon may intersect another ring
53    /// * No ring in the polygon may intersect itself
54    /// * No point on a ring may be touching a line in it or any other ring
55    /// * No points may be repeated in a ring
56    /// * All points must have valid floating point values
57    ///
58    /// # Examples
59    ///
60    /// ```
61    /// use geo_types::polygon;
62    /// use geo_validator::Validate;
63    ///
64    /// let poly = polygon!(
65    ///             exterior: [
66    ///                 (x: 0., y: 0.),
67    ///                 (x: 0., y: 200.),
68    ///                 (x: 200., y: 0.),
69    ///                 (x: 200., y: 200.),
70    ///             ],
71    ///             interiors: [
72    ///                 [
73    ///                     (x: 10., y: 20.),
74    ///                     (x: 50., y: 20.),
75    ///                     (x: 20., y: 50.),
76    ///                     (x: 50., y: 50.),
77    ///                 ],
78    ///             ],
79    ///         );
80    ///
81    ///         let valid = poly.validate();
82    ///         assert_eq!(valid, false);
83    /// ```
84    ///
85    fn validate(&self) -> bool;
86
87    /// Validate a Multipolygon/Polygon Geometry according to the OGC rules
88    /// with a detailed report of errors
89    ///
90    /// This function is non-trivial from a computational perspective.
91    /// It returns a large struct detailing all errors found in the submitted Geometry.
92    ///
93    /// * A polygon may not have less than three points
94    /// * A polygon may not have any unclosed rings
95    /// * No ring in the polygon may intersect another ring
96    /// * No ring in the polygon may intersect itself
97    /// * No point on a ring may be touching a line in it or any other ring
98    /// * No points may be repeated in a ring
99    /// * All points must have valid floating point values
100    ///
101    /// # Examples
102    ///
103    /// ```
104    /// use geo_types::polygon;
105    /// use geo_validator::Validate;
106    ///
107    /// let poly = polygon!(
108    ///             exterior: [
109    ///                 (x: 0., y: 0.),
110    ///                 (x: 0., y: 200.),
111    ///                 (x: 200., y: 0.),
112    ///                 (x: 200., y: 200.),
113    ///             ],
114    ///             interiors: [
115    ///                 [
116    ///                     (x: 10., y: 20.),
117    ///                     (x: 50., y: 20.),
118    ///                     (x: 20., y: 50.),
119    ///                     (x: 50., y: 50.),
120    ///                 ],
121    ///             ],
122    ///         );
123    ///
124    ///         let valid = poly.validate_detailed();
125    ///         assert_eq!(valid.valid, false);
126    ///         assert_eq!(valid.ring_intersects_other_ring.len(), 3);
127    ///         assert_eq!(valid.self_intersections.len(), 2);
128    ///         assert_eq!(valid.point_touching_line.len(), 1);
129    ///
130    ///         assert_eq!(valid.ring_intersects_other_ring[0].x, 20_f64);
131    ///         assert_eq!(valid.ring_intersects_other_ring[0].y, 20_f64);
132    ///         assert_eq!(valid.ring_intersects_other_ring[1].x, 35_f64);
133    ///         assert_eq!(valid.ring_intersects_other_ring[1].y, 35_f64);
134    ///         assert_eq!(valid.ring_intersects_other_ring[2].x, 50_f64);
135    ///         assert_eq!(valid.ring_intersects_other_ring[2].y, 50_f64);
136    ///
137    ///         assert_eq!(valid.self_intersections[0].x, 100_f64);
138    ///         assert_eq!(valid.self_intersections[0].y, 100_f64);
139    ///         assert_eq!(valid.self_intersections[1].x, 32.857142857142854_f64);
140    ///         assert_eq!(valid.self_intersections[1].y, 37.142857142857146_f64);
141    ///
142    ///         assert_eq!(valid.point_touching_line[0].x, 50_f64);
143    ///         assert_eq!(valid.point_touching_line[0].y, 50_f64);
144    /// ```
145    ///
146    fn validate_detailed(&self) -> ValidationErrors<T>;
147}
148
149/** Polygons */
150
151impl<T> Validate<T> for MultiPolygon<T>
152where
153    T: num_traits::Float,
154{
155    fn validate(&self) -> bool {
156        validate_multi_polygon(self, true).valid
157    }
158
159    fn validate_detailed(&self) -> ValidationErrors<T> {
160        validate_multi_polygon(self, false)
161    }
162}
163
164fn validate_multi_polygon<T: num_traits::Float>(
165    mp: &MultiPolygon<T>,
166    quick: bool,
167) -> ValidationErrors<T> {
168    let mut validation_errors = ValidationErrors::<T> {
169        valid: true,
170        has_less_than_three_points: false,
171        is_multi_polygon: false,
172        unsupported_floating_point_values: vec![] as Vec<T>,
173        open_rings: vec![] as Vec<LineString<T>>,
174        ring_intersects_other_ring: vec![] as Vec<Coordinate<T>>,
175        self_intersections: vec![] as Vec<Coordinate<T>>,
176        point_touching_line: vec![] as Vec<Coordinate<T>>,
177        repeated_points: vec![] as Vec<Coordinate<T>>,
178    };
179    for poly in mp.0.iter() {
180        if quick {
181            let valid = poly.validate();
182            if !valid {
183                validation_errors.valid = false;
184                return validation_errors; // Early return on first error
185            }
186        } else {
187            let err = poly.validate_detailed();
188            if !err.valid && validation_errors.valid {
189                validation_errors.valid = err.valid
190            }
191            if err.has_less_than_three_points && !validation_errors.has_less_than_three_points {
192                validation_errors.has_less_than_three_points = err.has_less_than_three_points
193            }
194            validation_errors
195                .unsupported_floating_point_values
196                .extend(err.unsupported_floating_point_values);
197            validation_errors.open_rings.extend(err.open_rings);
198            validation_errors
199                .ring_intersects_other_ring
200                .extend(err.ring_intersects_other_ring);
201            validation_errors
202                .self_intersections
203                .extend(err.self_intersections);
204            validation_errors
205                .point_touching_line
206                .extend(err.point_touching_line);
207            validation_errors
208                .repeated_points
209                .extend(err.repeated_points);
210        }
211    }
212    validation_errors
213}
214
215impl<T> Validate<T> for Polygon<T>
216where
217    T: num_traits::Float,
218{
219    fn validate(&self) -> bool {
220        validate_polygon(self, true).valid
221    }
222
223    fn validate_detailed(&self) -> ValidationErrors<T> {
224        validate_polygon(self, false)
225    }
226}
227
228/// Check a polygon for validity.
229/// This function is rather long, because it tries to be as quick as possible
230/// and to waste as few resources as possible. Setting the second parameter `quick`
231/// to true will cause the function to bail out at the very first error (without)
232/// providing any detailed information about the error.
233fn validate_polygon<T>(poly: &Polygon<T>, quick: bool) -> ValidationErrors<T>
234where
235    T: num_traits::Float,
236{
237    let mut validation_errors = ValidationErrors::<T> {
238        valid: true,
239        has_less_than_three_points: false,
240        is_multi_polygon: false,
241        unsupported_floating_point_values: vec![] as Vec<T>,
242        open_rings: vec![] as Vec<LineString<T>>,
243        ring_intersects_other_ring: vec![] as Vec<Coordinate<T>>,
244        self_intersections: vec![] as Vec<Coordinate<T>>,
245        point_touching_line: vec![] as Vec<Coordinate<T>>,
246        repeated_points: vec![] as Vec<Coordinate<T>>,
247    };
248
249    // First check if polygon is actually a MultiPolygon
250    let exterior_ring = Polygon::new(poly.exterior().clone(), vec![]);
251    for inner_ring in poly.interiors() {
252        if !exterior_ring.contains(inner_ring) {
253            validation_errors.valid = false;
254            if quick {
255                return validation_errors;
256            }
257            validation_errors.is_multi_polygon = true;
258        }
259    }
260
261    let mut poly_lines = vec![] as Vec<Line<T>>;
262    let mut rings = vec![poly.exterior()];
263    rings.extend(poly.interiors());
264    let mut ring_start_idx = 0; // This is used together with poly_lines to determine if intersection is with self
265    for ring in rings.into_iter() {
266        // Check for poly with less than 3 points
267        let ring_points_count = ring.0.len();
268        // The geo libs always close the poly so first and last point are the same and we need 4 point
269        // to describe a triangle.
270        if ring_points_count < 4 {
271            validation_errors.valid = false;
272            if quick {
273                return validation_errors;
274            }
275            validation_errors.has_less_than_three_points = true;
276        }
277
278        // Check for open ring
279        // Note: this check is pointless with the current geo crate, since it automatically closes
280        // any open rings. It is computationally cheap though, so keep it in case of future design
281        // changes.
282        if !ring.0[0].x.eq(&ring.0[ring_points_count - 1].x)
283            && !ring.0[0].y.eq(&ring.0[ring_points_count - 1].y)
284        {
285            validation_errors.valid = false;
286            if quick {
287                return validation_errors;
288            }
289            validation_errors.open_rings.push(ring.clone());
290        }
291
292        // Check for unsupported floating point value
293        let mut prev_point = ring.0[0];
294        if !prev_point.x.is_finite() {
295            validation_errors.valid = false;
296            if quick {
297                return validation_errors;
298            }
299            validation_errors
300                .unsupported_floating_point_values
301                .push(prev_point.x);
302        }
303        if !prev_point.y.is_finite() {
304            validation_errors.valid = false;
305            if quick {
306                return validation_errors;
307            }
308            validation_errors
309                .unsupported_floating_point_values
310                .push(prev_point.y);
311        }
312
313        let mut ring_points_map = LinkedHashMap::<CompCoord<T>, Coordinate<T>>::new();
314        for i in 1..(ring_points_count) {
315            let point = ring.0[i];
316
317            // Check for unsupported floating point value
318            if !point.x.is_finite() {
319                validation_errors.valid = false;
320                if quick {
321                    return validation_errors;
322                }
323                validation_errors
324                    .unsupported_floating_point_values
325                    .push(point.x);
326            }
327            if !point.y.is_finite() {
328                validation_errors.valid = false;
329                if quick {
330                    return validation_errors;
331                }
332                validation_errors
333                    .unsupported_floating_point_values
334                    .push(point.y);
335            }
336
337            // Check for repeated points (don't check the last point, since that should == first point)
338            let pp_comp = CompCoord {
339                0: Coordinate {
340                    x: prev_point.x,
341                    y: prev_point.y,
342                },
343            };
344            if ring_points_map.contains_key(&pp_comp) {
345                validation_errors.valid = false;
346                if quick {
347                    return validation_errors;
348                }
349                validation_errors.repeated_points.push(prev_point);
350            }
351            // Check for intersections
352            let current_line = Line::<T>::new(prev_point, point);
353            for (line_idx, line) in poly_lines.iter().enumerate() {
354                if !line.end.eq(&current_line.start) && !line.start.eq(&current_line.end) {
355                    // Check if any points intersect any lines
356                    let start_point: Point<T> = current_line.start.into();
357                    if line.intersects(&start_point) {
358                        validation_errors.valid = false;
359                        if quick {
360                            return validation_errors;
361                        }
362                        validation_errors
363                            .point_touching_line
364                            .push(current_line.start);
365                    } else if line.intersects(&current_line) {
366                        validation_errors.valid = false;
367                        if quick {
368                            return validation_errors;
369                        }
370                        if line_idx > ring_start_idx {
371                            validation_errors
372                                .self_intersections
373                                .push(line.intersection_point(&current_line));
374                        } else {
375                            validation_errors
376                                .ring_intersects_other_ring
377                                .push(line.intersection_point(&current_line));
378                        }
379                    }
380                }
381            }
382            poly_lines.push(current_line);
383            prev_point = point;
384            ring_points_map.insert(pp_comp, point);
385        }
386        ring_start_idx = poly_lines.len();
387    }
388
389    validation_errors
390}
391
392struct CompCoord<T: num_traits::Float>(Coordinate<T>);
393
394impl<T: num_traits::Float> PartialEq for CompCoord<T> {
395    fn eq(&self, other: &CompCoord<T>) -> bool {
396        // Note this function has no idea about the history of the float coordinates
397        // only the current state.  This is a strict byte-equality check and does not
398        // try to account in any way for the deviation of a float from its expected
399        // value due to imprecision caused by floating point operations.
400        transform_coord_to_array_of_u8(self) == transform_coord_to_array_of_u8(other)
401    }
402}
403
404impl<T: num_traits::Float> Eq for CompCoord<T> {}
405
406impl<T: num_traits::Float> Hash for CompCoord<T> {
407    fn hash<H: Hasher>(&self, state: &mut H) {
408        transform_coord_to_array_of_u8(self).hash(state);
409    }
410}
411/// Transform a coordinate into a 128byte array by concatenating the
412/// byte representation of its position on the 2 axes (as f64)
413///
414fn transform_coord_to_array_of_u8<T>(coord: &CompCoord<T>) -> [u8; 16]
415where
416    T: num_traits::Float,
417{
418    let mut buf1 = [0; 8];
419    NativeEndian::write_f64(&mut buf1, T::to_f64(&coord.0.x).unwrap());
420    let mut buf2 = [0; 8];
421    NativeEndian::write_f64(&mut buf2, T::to_f64(&coord.0.y).unwrap());
422
423    [
424        buf1[0], buf1[1], buf1[2], buf1[3], buf1[4], buf1[5], buf1[6], buf1[7], buf2[0], buf2[1],
425        buf2[2], buf2[3], buf2[4], buf2[5], buf2[6], buf2[7],
426    ]
427}
428
429/// Returns the coordinate at which two geometries intersect
430pub trait IntersectionPoint<T>
431where
432    T: num_traits::Float,
433{
434    fn intersection_point(&self, line: &Line<T>) -> Coordinate<T>;
435}
436
437impl<T> IntersectionPoint<T> for Line<T>
438where
439    T: num_traits::Float,
440{
441    // See https://www.geeksforgeeks.org/program-for-point-of-intersection-of-two-lines/
442    fn intersection_point(&self, line: &Line<T>) -> Coordinate<T> {
443        // Line AB represented as a1x + b1y = c1
444        let a1 = self.end.y - self.start.y;
445        let b1 = self.start.x - self.end.x;
446        let c1 = a1 * (self.start.x) + b1 * (self.start.y);
447
448        // Line CD represented as a2x + b2y = c2
449        let a2 = line.end.y - line.start.y;
450        let b2 = line.start.x - line.end.x;
451        let c2 = a2 * (line.start.x) + b2 * (line.start.y);
452
453        let determinant = a1 * b2 - a2 * b1;
454        if determinant.is_normal()
455        // == T::from(0).unwrap() // Will this be problematic in cases where determinant is subnormal?
456        {
457            let x = (b2 * c1 - b1 * c2) / determinant;
458            let y = (a1 * c2 - a2 * c1) / determinant;
459            Coordinate { x, y }
460        } else {
461            // Parallel lines never intersect (hence infinity)
462            Coordinate {
463                x: T::infinity(),
464                y: T::infinity(),
465            }
466        }
467    }
468}
469
470/** Tests */
471
472#[cfg(test)]
473mod tests {
474    use super::*;
475    use geo_types::{line_string, point, polygon};
476
477    #[test]
478    fn can_validate_polygon() {
479        let poly = polygon![
480            (x: 1.0, y: 1.0),
481            (x: 4.000000007, y: 1.0),
482            (x: 4.0, y: 4.0),
483            (x: 1.0, y: 4.0),
484            (x: 1.0, y: 1.0),
485        ];
486
487        let valid = validate_polygon(&poly, false);
488        assert_eq!(valid.valid, true);
489    }
490
491    #[test]
492    fn can_validate_complex_polygon() {
493        let poly = polygon!(
494            exterior: [
495                (x: 0., y: 0.),
496                (x: 0., y: 20.),
497                (x: 20., y: 20.),
498                (x: 20., y: 0.),
499            ],
500            interiors: [
501                [
502                    (x: 10., y: 10.),
503                    (x: 15., y: 10.),
504                    (x: 15., y: 15.),
505                    (x: 10., y: 15.),
506                ],
507            ],
508        );
509
510        let valid = validate_polygon(&poly, true);
511        assert_eq!(valid.valid, true);
512    }
513
514    #[test]
515    fn can_find_multiple_errors_in_complex_polygon() {
516        let poly = polygon!(
517            exterior: [
518                (x: 0., y: 0.),
519                (x: 0., y: 200.),
520                (x: 200., y: 0.),
521                (x: 200., y: 200.),
522            ],
523            interiors: [
524                [
525                    (x: 10., y: 20.),
526                    (x: 50., y: 20.),
527                    (x: 20., y: 50.),
528                    (x: 50., y: 50.),
529                ],
530            ],
531        );
532
533        let valid = validate_polygon(&poly, false);
534        assert_eq!(valid.valid, false);
535        assert_eq!(valid.ring_intersects_other_ring.len(), 3);
536        assert_eq!(valid.self_intersections.len(), 2);
537        assert_eq!(valid.point_touching_line.len(), 1);
538
539        assert_eq!(valid.ring_intersects_other_ring[0].x, 20_f64);
540        assert_eq!(valid.ring_intersects_other_ring[0].y, 20_f64);
541        assert_eq!(valid.ring_intersects_other_ring[1].x, 35_f64);
542        assert_eq!(valid.ring_intersects_other_ring[1].y, 35_f64);
543        assert_eq!(valid.ring_intersects_other_ring[2].x, 50_f64);
544        assert_eq!(valid.ring_intersects_other_ring[2].y, 50_f64);
545
546        assert_eq!(valid.self_intersections[0].x, 100_f64);
547        assert_eq!(valid.self_intersections[0].y, 100_f64);
548        assert_eq!(valid.self_intersections[1].x, 32.857142857142854_f64);
549        assert_eq!(valid.self_intersections[1].y, 37.142857142857146_f64);
550
551        assert_eq!(valid.point_touching_line[0].x, 50_f64);
552        assert_eq!(valid.point_touching_line[0].y, 50_f64);
553    }
554
555    #[test]
556    fn can_recognize_self_intersecting_polygon() {
557        let poly = polygon![
558            (x: 1.0_f64, y: 1.0),
559            (x: 4.0, y: 1.0),
560            (x: 1.0, y: 4.0),
561            (x: 4.0, y: 4.0),
562            (x: 1.0, y: 1.0),
563        ];
564
565        let valid = validate_polygon(&poly, false);
566        assert_eq!(valid.valid, false);
567        assert_eq!(valid.self_intersections.len(), 1);
568        assert_eq!(valid.self_intersections[0].x, 2.5);
569        assert_eq!(valid.self_intersections[0].y, 2.5);
570    }
571
572    #[test]
573    fn can_recognize_multi_polygon() {
574        let poly = polygon!(
575            exterior: [
576                (x: 0., y: 0.),
577                (x: 0., y: 20.),
578                (x: 20., y: 20.),
579                (x: 0., y: 20.),
580                (x: 0., y: 0.),
581            ],
582            interiors: [
583                [
584                    (x: 25., y: 25.),
585                    (x: 25., y: 30.),
586                    (x: 30., y: 30.),
587                    (x: 30., y: 25.),
588                    (x: 25., y: 25.),
589                ],
590            ],
591        );
592
593        let valid = validate_polygon(&poly, false);
594        assert!(!valid.valid);
595        assert!(valid.is_multi_polygon);
596    }
597
598    #[test]
599    fn rejects_polygon_with_too_few_points() {
600        let poly = polygon![
601            (x: 1.0_f64, y: 1.0),
602            (x: 4.0, y: 1.0),
603            (x: 1.0, y: 1.0),
604        ];
605
606        let valid = validate_polygon(&poly, false);
607        assert!(!valid.valid);
608        assert!(valid.has_less_than_three_points);
609    }
610
611    #[test]
612    fn rejects_polygon_with_nan_and_infinity() {
613        let poly = polygon![
614            (x: 1.0_f64, y: 1.0),
615            (x: 1.0, y: 4.0),
616            (x: 4.0, y: 4.0),
617            (x: 4.0, y: 1.0),
618            (x: std::f64::INFINITY, y: std::f64::NAN),
619        ];
620
621        let valid = validate_polygon(&poly, false);
622        assert!(!valid.valid);
623        assert_eq!(valid.unsupported_floating_point_values.len(), 2);
624        assert!(valid.unsupported_floating_point_values[0].is_infinite());
625        assert!(valid.unsupported_floating_point_values[1].is_nan());
626    }
627
628    #[test]
629    fn rejects_polygon_with_repeated_points() {
630        let poly = polygon![
631            (x: 1.0_f64, y: 1.0),
632            (x: 1.0, y: 4.0),
633            (x: 4.0, y: 4.0),
634            (x: 4.0, y: 1.0),
635            (x: 1.0, y: 1.0),
636            (x: 1.0, y: 1.0),
637            (x: 1.0, y: 1.0),
638        ];
639
640        let valid = validate_polygon(&poly, false);
641        assert!(!valid.valid);
642        assert_eq!(valid.repeated_points.len(), 2);
643        assert!(valid.repeated_points[0].eq(&Coordinate { x: 1.0_f64, y: 1.0 }));
644        assert!(valid.repeated_points[1].eq(&Coordinate { x: 1.0_f64, y: 1.0 }));
645
646        let poly2 = polygon![
647            (x: 1.0_f64, y: 1.0),
648            (x: 1.0, y: 4.0),
649            (x: 4.0, y: 4.0),
650            (x: 4.0, y: 1.0),
651            (x: 4.0, y: 1.0),
652            (x: 4.0, y: 1.0),
653            (x: 1.0, y: 1.0),
654        ];
655
656        let valid2 = validate_polygon(&poly2, false);
657        assert!(!valid2.valid);
658        assert_eq!(valid2.repeated_points.len(), 2);
659        assert!(valid2.repeated_points[0].eq(&Coordinate { x: 4.0_f64, y: 1.0 }));
660        assert!(valid2.repeated_points[1].eq(&Coordinate { x: 4.0_f64, y: 1.0 }));
661    }
662}
geo_validator/lib.rs

geo_validator/
lib.rs
