Table of Contents

Snapping to a target

Data that is meant to meet often misses by a little: a cutting line drawn on a map ends a few millimetres short of the edge, two parcels surveyed apart leave a gap or a sliver between them, a point "on" a line lies 4e-16 beside it. The exact operations of the library answer these cases correctly and unhelpfully: a loose end does not cut (ADR 0007), a gap is not a touch (ADR 0013). The case that started this was the playground: Geoman snaps the end of a cutting line onto the edge as it is straight in Web Mercator, the server computes in UTM, where the edge between the same two vertices is a different straight line, and the end lies beside it by about 0.15 mm on a 100 m edge, 4 mm on 500 m and 6 cm on 2 km. That is a thousand to ten thousand times the grid of the overlays (1e-6 m at UTM coordinates), and whether the end lies inside (no cut) or outside (a cut) depends on the direction of the edge: the cut worked only sometimes. SnapTo moves the vertices of a geometry that lie within a tolerance of a target onto it, as a separate step before the exact operation: cutter.SnapTo(polygon, 0.01).Cut(polygon).

German version: 0046-fangen-an-ein-ziel.de.md

Consequences

  • Placement: SnapTo and the enums SnapMode and SnapEnds in a new static class Snapping (Snapping.cs) in SpatialNET.Extensions. For the package validation and the API tracking this is an addition only (ADR 0028). Cut, the overlays and the predicates are unchanged, and so is ADR 0007: the cutting line is not extended by Cut.

  • API (typed overloads, ADR 0012):

    IPoint2D      SnapTo(this IPoint2D point, IGeometry2D target, double tolerance, IGeometryFactory? factory = null)
    IMultiPoint2D SnapTo(this IMultiPoint2D multiPoint, IGeometry2D target, double tolerance, IGeometryFactory? factory = null)
    IPolyline2D   SnapTo(this IPolyline2D line, IGeometry2D target, double tolerance, SnapMode mode = SnapMode.Ends, SnapEnds ends = SnapEnds.Nearest, IGeometryFactory? factory = null)
    IPolygon2D    SnapTo(this IPolygon2D polygon, IGeometry2D target, double tolerance, SnapMode mode = SnapMode.Vertices, IGeometryFactory? factory = null)
    IGeometry2D   SnapTo(this IGeometry2D geometry, IGeometry2D target, double tolerance, SnapMode? mode = null, SnapEnds ends = SnapEnds.Nearest, IGeometryFactory? factory = null)
    enum SnapMode { Ends, Vertices }
    enum SnapEnds { Nearest, Extend, ExtendOrNearest }
    
  • The target can be any geometry: the vertices and the segments of a line, the rings of a polygon, the points of a multipoint. The tolerance is required, finite and greater than 0, in the units of the coordinates (as maxSnapDistance of CalibrateM, ADR 0030): a sensible value depends on the data (millimetres for a survey, metres for digitising), and a silent default would change data.

  • A vertex of the target wins over an edge. A point within the tolerance of a vertex of the target goes to the nearest such vertex, otherwise to the nearest point of an edge within the tolerance, otherwise it stays. An end that lands a millimetre beside a corner would leave a sliver in the cut. Among equally near candidates the first one in the order of the target wins (ADR 0019).

  • SnapMode.Ends (the default for a polyline) moves only the loose ends: the start and the end of every open path. A closed path has no loose end and stays, a polygon has none at all (Ends on a polygon gives a copy). The inner vertices stay where they are. For each end, in this order:

    1. An overshoot is cut back. If the path meets the target less than the tolerance before its end (measured along the path), it is cut at that contact, and the stub behind it goes. A line that crosses an edge and stops 3 mm beyond it ends on the edge.
    2. A vertex of the target within the tolerance of the end wins (of the cut-back end).
    3. An end that lies on the target stays.
    4. Otherwise SnapEnds decides: Nearest (the default) moves the end to the nearest point of an edge; Extend moves it along the direction of the last segment up to the first edge within the tolerance, so that the direction stays, and leaves it if the extension misses (an end that runs along an edge, a target at a glancing angle beyond the tolerance); ExtendOrNearest extends, and moves to the nearest point if that misses. For the projection error both give practically the same, since the end is off by a fraction of a millimetre almost across the edge; Extend is for lines that were digitised short of a boundary.
  • SnapMode.Vertices (the default for a polygon) snaps every vertex as a point, and then inserts every vertex of the target that lies within the tolerance of a segment, strictly between its ends, into it (in the order along the segment). Only then do two neighbours share their common boundary: moving the vertices of one alone would leave wedges where the other has a corner in the middle of an edge. SnapEnds is not used in this mode.

  • Points snap as points; the modes do not apply. A point with nothing within the tolerance stays, without an error (for CalibrateM an anchor beyond the distance is an error, since it would be a wrong measurement; here it is only a point that was not meant).

  • Z and M: a moved point keeps its own Z and M; the target decides only where it lies, as the cut keeps the values of the line (ADR 0015). A vertex of the target that is inserted gets Z and M interpolated on the segment, a cut-back end too.

  • What collapses: vertices that fall together are merged, a path with fewer than two and a ring with fewer than three distinct vertices are dropped, a part whose shell collapses goes with its holes, and the rings are normalized (as SnapToGrid, ADR 0027). There is no MakeValid inside: moving vertices can make edges cross, a check on every call would cost for a case that needs features closer together than the tolerance, and MakeValid is one call away (as for Smooth, ADR 0043).

  • Exact enough for the exact operations. A point moved onto an edge is computed in floating point and lies on it within about 1e-16 relative, far below the grid of the overlays (1e-12 relative, ADR 0005): snap rounding sees it as touching, and Cut cuts. A point moved onto a vertex has the very same numbers. The predicates are exact on the coordinates; for them a vertex of the target inserted into a segment is what makes "on the line" true (an inserted vertex is exact, a projected point is not).

  • Index: the vertices and the segments of the target are held in a SpatialIndex (ADR 0014), so a large target is not searched linearly. A PreparedGeometry as the target is not used for its own index; an overload follows if a measurement asks for it.

  • Difference to NTS: the GeometrySnapper of NetTopologySuite (and JTS) moves the vertices of the source only onto vertices of the target and inserts vertices of the target into the segments of the source. SnapTo with Vertices does that too, and in addition moves a vertex onto an edge of the target when no vertex is near: a vertex 2 cm from the middle of an edge stays in NTS and goes onto the edge here. The test compares with NTS where both do the same (every vertex either near a vertex of the target or far from its edges) and shows the difference in a test of its own. NTS has nothing like Ends.

  • Tests (ADR 0008): points (vertex before edge, edge, nothing, targets of every kind, Z and M), the ends (short of the edge, overshoot over one and several segments, the three SnapEnds, a vertex wins, closed paths and polygons, the cut that did not cut and cuts after snapping in UTM coordinates), Vertices (moved and inserted vertices, neighbouring areas that touch afterwards and unite to one part, Z and M of inserted vertices), collapse, the overload for any geometry, errors, NTS as above, and two properties: no point moves further than the tolerance and every point within it ends on the target; a chord of a convex polygon with both ends moved by up to 9 mm inwards or outwards always cuts into two pieces after SnapTo(polygon, 0.01). The methods are covered by tests ([Covers]), not by fixtures: the playground examples live in samples/snapping/.

  • Playground: the entry snapTo (tolerance, mode with Auto for the default of the kind, ends). The entries with two inputs and an exact topological result, cut, relate, all predicates and the overlays (intersection, union, difference, symDifference), get the parameters "Snap B to A, tolerance" (empty = off) and the mode, Ends for cut and Vertices for the others. The direction is always B onto A, which for cut is the cutting line onto the polygon. The result names how many vertices of B moved and by how much (the Hausdorff distance), a cut that did not cut names an end of the cutting line that lies within a thousandth of the size of A, and the text of a predicate that is almost true points to the snap tolerance. The alternatives of the predicates name SnapTo first for Intersects, Disjoint, Touches, Crosses and EqualsTopo. clip has no second geometry and no snapping; equalsExact compares the exact coordinates on purpose.

  • Documentation: this ADR, a section on the concept page of Cut, a cookbook recipe and glossary entries that keep apart the three meanings of "snap": snapping to a target (SnapTo), snap rounding of the overlays (ADR 0005) and snapping to the grid (SnapToGrid, ADR 0027).

  • Not now: snapping a geometry to itself (closing gaps between its own parts), snapping many geometries to each other at once (a coverage), a snap tolerance as a parameter of Cut or of the predicates, and the use of a PreparedGeometry as the target.

Considered Options

  • A parameter snapTolerance of Cut (rejected: it would change the rule of ADR 0007 for one operation, and the same need exists for the overlays and the predicates; one function before all of them says the same and stays composable)
  • Only the ends of lines (rejected as the only mode: neighbouring areas need all vertices and the inserted corners; kept as the default for lines)
  • Only extending the last segment, as editing tools do (rejected as the only way: at a glancing angle the extension hits far away or never; kept as SnapEnds.Extend)
  • Onto vertices of the target only, as NTS (rejected: an end in the middle of an edge, the case of the playground, would not move at all)
  • Making the result valid inside (rejected: as for Smooth, MakeValid is one call away)
  • A default tolerance (rejected: no value fits survey data and digitised data at once)
  • Fixing the projection in the playground instead (densifying the edges before projecting) (rejected as the answer: it would hide the effect in the playground only, while every client with drawn or projected data has it; the playground keeps projecting vertices only, ADR 0010)