Table of Contents

Transformations, checks and Hausdorff distance

Three small groups of helpers that hosts keep writing themselves. Transformations move, scale and rotate a geometry (Translate, Scale, Rotate, and the general Transform). Checks answer a yes/no question about the form of a geometry (IsSimple, IsClosed, IsRing, EqualsExact). HausdorffDistance measures how far two shapes are from each other as a whole, not at their closest point. None of them runs the overlay core, and none needs a grid.

German version: 0025-transformationen-pruefungen-und-hausdorff.de.md

Consequences

  • Placement: Translate, Scale, Rotate and Transform in the new static class Transformations; IsSimple, IsClosed, IsRing and EqualsExact in the new static class Characteristics; HausdorffDistance in Measures. All in SpatialNET.Extensions, namespace SpatialNET. For the package validation this is an addition only.
  • Transformations (results through the factory, restricted to SupportsZ and SupportsM, ADR 0019):
    • Transform(Func<Coordinate, Coordinate>) maps every vertex. Translate(dx, dy), Scale(sx, sy, origin?) and Rotate(angle, origin?) are special cases; they change X and Y and keep Z and M. Angles are radians, counter-clockwise; the default origin of Scale and Rotate is (0, 0). Multiples of a quarter turn are exact (no sine and cosine error).
    • There are overloads for IPoint2D, IMultiPoint2D, IPolyline2D, IPolygon2D and IGeometry2D, as for Densify: the typed ones return the same kind.
    • A polygon is normalised first (ADR 0003) and its orientation is restored afterwards: a mirroring transformation (a negative scale factor) turns shells clockwise, so the rings are reversed back, and the result is again valid. Transform with an arbitrary function can produce an invalid polygon (it is a coordinate map and not a topology-preserving one); Translate, Rotate and Scale with a factor other than 0 keep validity. A factor of 0 collapses the geometry onto a line or a point.
    • Exceptions (ADR 0012): ArgumentNullException for null, ArgumentOutOfRangeException for a NaN or infinite parameter (shift, factor, angle, origin), InvalidOperationException without a factory, and also if the mapping, or an overflow of the arithmetic, produces a coordinate whose X or Y is NaN or infinite. Empty geometries are copied.
  • IsSimple: a point and a polygon are simple (validity of an area is IsValid, as in JTS). A multipoint is simple if no point occurs twice. A polyline is simple if its segments meet only where the OGC allows: consecutive segments of one path, the two ends of a closed path, and the end points of two different open paths (any number of open paths may end in one point). Everything else is a violation: a crossing, a path that touches or revisits itself, an overlap, a path end on the inside of another segment, and any touch of the closing point of a closed path by another path. The decision uses the exact orientation test and a SpatialIndex over the segments, so it is not quadratic. NTS is the oracle.
  • IsClosed(IPolyline2D): every non-empty path is closed (first and last point equal in X and Y); a polyline without a non-empty path is not closed. IsRing(IPolyline2D): exactly one non-empty path, closed, at least four points, and simple.
  • EqualsExact(a, b, tolerance = 0): the same kind and structure with the same coordinates as given, vertex by vertex: the order of points, paths and rings, the start and the direction of a ring all count (the closing point of a ring need not be stored). Two vertices are equal if their distance is at most the tolerance (default 0 = exact). Z and M are ignored, as in the topological predicates. For equality of the point sets use EqualsTopo.
  • HausdorffDistance(a, b, densifyFraction = 1): the discrete Hausdorff distance as JTS defines it: the larger of the two directed distances, each the greatest distance from a sample point of one geometry to the line work of the other. A polygon counts by its rings, not by its area. The sample points are the vertices; a fraction below 1 divides every segment into round(1 / fraction) pieces and adds those points. The result is exact for the samples and a lower bound of the true Hausdorff distance, which approaches it with a smaller fraction. An exact Hausdorff distance is not offered. NaN for an empty geometry; a fraction outside (0, 1], or one so small that the number of samples is unreasonable, throws ArgumentOutOfRangeException. The search uses a SpatialIndex over the segments of the other geometry.
  • Tests (ADR 0008): these methods have no topological edge cases the tag catalog is made for, so [Covers] tests take the place of fixtures: hand-written tables, and property tests against NTS: AffineTransformation for the combination of rotation, scale and translation; IsSimple, IsClosed and IsRing on lines on a small integer grid (many touches), 20,000 cases; DiscreteHausdorffDistance for random polygons, lines and multipoints with several densify fractions. Rigid motions keep area and validity, mirroring keeps the orientation.
  • Playground and documentation: descriptors for Translate, Scale, Rotate, IsSimple, IsClosed, IsRing, EqualsExact and HausdorffDistance (ADR 0011; Transform takes a function and has none), a section in the concept page for the measures and constructions, glossary entries.

Considered Options

  • Transformations as an IAffineTransformation object (rejected: a matrix type is more API than Translate, Scale and Rotate; Transform takes any function)
  • Rotation about the centre of the envelope by default (rejected: the origin (0, 0) is what JTS does and what a reader expects; an explicit origin is one argument)
  • Moving the mod-2 boundary rule into IsSimple (rejected: it would call a point where four open paths end non-simple, which JTS does not; the closed-ring rule is the one that matters)
  • An exact Hausdorff distance (rejected: it needs the Voronoi diagram of the line work; the discrete one with a fraction is what JTS offers and what users need)
  • Comparing Z and M in EqualsExact (rejected: Z and M never influence a computation, ADR 0015; a caller who wants them compares the coordinates)