Table of Contents

Fangen an ein Ziel

Daten, die sich treffen sollen, verfehlen sich oft knapp: Eine auf der Karte gezeichnete Schnittlinie endet ein paar Millimeter vor dem Rand, zwei getrennt vermessene Flurstücke lassen eine Lücke oder einen Splitter zwischen sich, ein Punkt „auf" einer Linie liegt 4e-16 daneben. Die exakten Operationen der Bibliothek beantworten diese Fälle richtig und wenig hilfreich: Ein loses Ende schneidet nicht (ADR 0007), eine Lücke ist keine Berührung (ADR 0013). Auslöser war der Playground: Geoman fängt das Ende einer Schnittlinie auf der Kante, wie sie in Web Mercator gerade ist, der Server rechnet in UTM, wo die Kante zwischen denselben zwei Stützpunkten eine andere Gerade ist, und das Ende liegt daneben, etwa 0,15 mm bei einer Kante von 100 m, 4 mm bei 500 m und 6 cm bei 2 km. Das ist das Tausend- bis Zehntausendfache des Rasters der Overlays (1e-6 m bei UTM-Koordinaten), und ob das Ende innen (kein Schnitt) oder außen (ein Schnitt) liegt, hängt von der Richtung der Kante ab: Der Schnitt klappte nur manchmal. SnapTo verschiebt die Stützpunkte einer Geometrie, die näher als eine Toleranz an einem Ziel liegen, auf das Ziel, als eigener Schritt vor der exakten Operation: cutter.SnapTo(polygon, 0.01).Cut(polygon).

English version: 0046-fangen-an-ein-ziel.md

Consequences

  • Ort: SnapTo und die Aufzählungen SnapMode und SnapEnds in einer neuen statischen Klasse Snapping (Snapping.cs) in SpatialNET.Extensions. Für die Paketvalidierung und die API-Verfolgung ist das nur eine Ergänzung (ADR 0028). Cut, die Overlays und die Prädikate bleiben unverändert, ebenso ADR 0007: Cut verlängert die Schnittlinie nicht.

  • API (typisierte Überladungen, 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 }
    
  • Das Ziel kann jede Geometrie sein: die Stützpunkte und Segmente einer Linie, die Ringe eines Polygons, die Punkte eines Multipunkts. Die Toleranz ist Pflicht, endlich und größer als 0, in den Einheiten der Koordinaten (wie maxSnapDistance von CalibrateM, ADR 0030): Ein sinnvoller Wert hängt von den Daten ab (Millimeter bei Vermessung, Meter beim Digitalisieren), und ein stiller Standardwert würde Daten verändern.

  • Eine Ecke des Ziels geht vor einer Kante. Ein Punkt in der Toleranz einer Ecke des Ziels geht auf die nächste solche Ecke, sonst auf den nächsten Punkt einer Kante in der Toleranz, sonst bleibt er. Ein Ende, das einen Millimeter neben einer Ecke landet, hinterließe beim Schnitt einen Splitter. Unter gleich nahen Kandidaten gewinnt der erste in der Reihenfolge des Ziels (ADR 0019).

  • SnapMode.Ends (Standard für eine Polylinie) verschiebt nur die losen Enden: Anfang und Ende jedes offenen Pfads. Ein geschlossener Pfad hat kein loses Ende und bleibt, ein Polygon hat gar keines (Ends auf einem Polygon gibt eine Kopie). Die inneren Stützpunkte bleiben, wo sie sind. Für jedes Ende, in dieser Reihenfolge:

    1. Ein Überstand wird abgeschnitten. Trifft der Pfad das Ziel weniger als die Toleranz vor seinem Ende (entlang des Pfads gemessen), wird er an diesem Kontakt abgeschnitten, und der Stummel dahinter fällt weg. Eine Linie, die eine Kante kreuzt und 3 mm dahinter aufhört, endet auf der Kante.
    2. Eine Ecke des Ziels in der Toleranz des Endes gewinnt (des abgeschnittenen Endes).
    3. Ein Ende, das auf dem Ziel liegt, bleibt.
    4. Sonst entscheidet SnapEnds: Nearest (Standard) verschiebt das Ende auf den nächsten Punkt einer Kante; Extend verschiebt es in Richtung des letzten Segments bis zur ersten Kante in der Toleranz, sodass die Richtung bleibt, und lässt es stehen, wenn die Verlängerung nichts trifft (ein Ende, das an einer Kante entlang läuft, ein Ziel unter schleifendem Winkel jenseits der Toleranz); ExtendOrNearest verlängert und verschiebt auf den nächsten Punkt, wenn das nichts trifft. Beim Projektionsfehler liefern beide praktisch dasselbe, weil das Ende um Bruchteile eines Millimeters fast quer zur Kante daneben liegt; Extend ist für Linien, die vor einer Grenze aufhörend digitalisiert wurden.
  • SnapMode.Vertices (Standard für ein Polygon) fängt jeden Stützpunkt als Punkt und fügt danach jede Ecke des Ziels, die in der Toleranz eines Segments liegt, echt zwischen seinen Enden in dieses ein (in der Reihenfolge entlang des Segments). Erst dann teilen sich zwei Nachbarn ihre gemeinsame Grenze: Nur die Stützpunkte des einen zu verschieben ließe Keile, wo der andere eine Ecke mitten in einer Kante hat. SnapEnds wird in diesem Modus nicht verwendet.

  • Punkte werden als Punkte gefangen; die Modi gelten nicht. Ein Punkt, der in der Toleranz nichts findet, bleibt, ohne Fehler (bei CalibrateM ist ein Ankerpunkt jenseits des Abstands ein Fehler, weil er eine falsche Messung wäre; hier ist es nur ein Punkt, der nicht gemeint war).

  • Z und M: Ein verschobener Punkt behält sein eigenes Z und M; das Ziel bestimmt nur, wo er liegt, so wie der Schnitt die Werte der Linie behält (ADR 0015). Eine eingefügte Ecke des Ziels bekommt Z und M auf dem Segment interpoliert, ein abgeschnittenes Ende ebenso.

  • Was zusammenfällt: Zusammenfallende Stützpunkte werden vereinigt, ein Pfad mit weniger als zwei und ein Ring mit weniger als drei verschiedenen Stützpunkten fällt weg, ein Teil, dessen Hülle zusammenfällt, geht mit seinen Löchern, und die Ringe werden normalisiert (wie SnapToGrid, ADR 0027). Es gibt kein MakeValid im Inneren: Verschobene Stützpunkte können Kanten kreuzen lassen, eine Prüfung bei jedem Aufruf kostete für einen Fall, der Objekte näher als die Toleranz braucht, und MakeValid ist einen Aufruf entfernt (wie bei Smooth, ADR 0043).

  • Genau genug für die exakten Operationen. Ein auf eine Kante verschobener Punkt wird in Gleitkomma berechnet und liegt auf ihr bis auf etwa 1e-16 relativ, weit unter dem Raster der Overlays (1e-12 relativ, ADR 0005): Das Snap Rounding sieht ihn als Berührung, und Cut schneidet. Ein auf eine Ecke verschobener Punkt hat genau dieselben Zahlen. Die Prädikate sind exakt auf den Koordinaten; für sie macht erst eine in ein Segment eingefügte Ecke des Ziels „auf der Linie" wahr (eine eingefügte Ecke ist exakt, ein projizierter Punkt nicht).

  • Index: Die Stützpunkte und Segmente des Ziels liegen in einem SpatialIndex (ADR 0014), ein großes Ziel wird also nicht linear durchsucht. Eine PreparedGeometry als Ziel wird nicht mit ihrem eigenen Index genutzt; eine Überladung folgt, wenn eine Messung danach fragt.

  • Unterschied zu NTS: Der GeometrySnapper von NetTopologySuite (und JTS) verschiebt die Stützpunkte der Quelle nur auf Ecken des Ziels und fügt Ecken des Ziels in die Segmente der Quelle ein. SnapTo mit Vertices macht das auch und verschiebt zusätzlich einen Stützpunkt auf eine Kante des Ziels, wenn keine Ecke nahe ist: Ein Stützpunkt 2 cm neben der Mitte einer Kante bleibt bei NTS und geht hier auf die Kante. Der Test vergleicht mit NTS, wo beide dasselbe tun (jeder Stützpunkt entweder nahe einer Ecke des Ziels oder weit von seinen Kanten), und zeigt den Unterschied in einem eigenen Test. NTS hat nichts wie Ends.

  • Tests (ADR 0008): Punkte (Ecke vor Kante, Kante, nichts, Ziele jeder Art, Z und M), die Enden (vor der Kante, Überstand über ein und mehrere Segmente, die drei SnapEnds, eine Ecke gewinnt, geschlossene Pfade und Polygone, der Schnitt, der nicht schnitt und nach dem Fangen in UTM-Koordinaten schneidet), Vertices (verschobene und eingefügte Stützpunkte, Nachbarflächen, die sich danach berühren und zu einem Teil vereinigen, Z und M eingefügter Stützpunkte), Zusammenfallen, die Überladung für jede Geometrie, Fehler, NTS wie oben, und zwei Eigenschaften: Kein Punkt wandert weiter als die Toleranz, und jeder Punkt in ihr endet auf dem Ziel; eine Sehne eines konvexen Polygons, deren Enden um bis zu 9 mm nach innen oder außen verschoben sind, schneidet nach SnapTo(polygon, 0.01) immer in zwei Teile. Die Methoden sind durch Tests abgedeckt ([Covers]), nicht durch Fixtures: Die Playground-Beispiele liegen in samples/snapping/.

  • Playground: der Eintrag snapTo (Toleranz, Modus mit Auto für den Standard der Art, Enden). Die Einträge mit zwei Eingaben und einem exakten topologischen Ergebnis, cut, relate, alle Prädikate und die Overlays (intersection, union, difference, symDifference), bekommen die Parameter „Snap B to A, tolerance" (leer = aus) und den Modus, Ends bei cut und Vertices bei den übrigen. Die Richtung ist immer B auf A, bei cut also die Schnittlinie auf das Polygon. Das Ergebnis nennt, wie viele Stützpunkte von B verschoben wurden und um wie viel (die Hausdorff-Distanz), ein Schnitt, der nicht schnitt, nennt ein Ende der Schnittlinie, das näher als ein Tausendstel der Größe von A liegt, und der Text eines fast wahren Prädikats verweist auf die Snap-Toleranz. Die Alternativen der Prädikate nennen SnapTo zuerst für Intersects, Disjoint, Touches, Crosses und EqualsTopo. clip hat keine zweite Geometrie und kein Fangen; equalsExact vergleicht absichtlich die exakten Koordinaten.

  • Dokumentation: dieses ADR, ein Abschnitt auf der Konzeptseite von Cut, ein Kochbuch-Rezept und Glossareinträge, die die drei Bedeutungen von „Snap" auseinanderhalten: Fangen an ein Ziel (SnapTo), Snap Rounding der Overlays (ADR 0005) und auf das Raster legen (SnapToGrid, ADR 0027).

  • Nicht jetzt: eine Geometrie an sich selbst fangen (Lücken zwischen ihren eigenen Teilen schließen), viele Geometrien auf einmal aneinander fangen (eine Abdeckung), eine Snap-Toleranz als Parameter von Cut oder der Prädikate, und eine PreparedGeometry als Ziel.

Considered Options

  • Ein Parameter snapTolerance von Cut (verworfen: Er änderte die Regel von ADR 0007 für eine Operation, und derselbe Bedarf besteht bei den Overlays und den Prädikaten; eine Funktion vor allen sagt dasselbe und bleibt kombinierbar)
  • Nur die Enden von Linien (als einziger Modus verworfen: Nachbarflächen brauchen alle Stützpunkte und die eingefügten Ecken; als Standard für Linien behalten)
  • Nur das letzte Segment verlängern, wie Editierwerkzeuge es tun (als einziger Weg verworfen: Unter schleifendem Winkel trifft die Verlängerung weit weg oder nie; als SnapEnds.Extend behalten)
  • Nur auf Ecken des Ziels, wie NTS (verworfen: Ein Ende mitten auf einer Kante, der Fall des Playgrounds, bewegte sich gar nicht)
  • Das Ergebnis im Inneren gültig machen (verworfen: wie bei Smooth ist MakeValid einen Aufruf entfernt)
  • Eine Standard-Toleranz (verworfen: Kein Wert passt zugleich zu Vermessungsdaten und digitalisierten Daten)
  • Stattdessen die Projektion im Playground reparieren (die Kanten vor dem Projizieren verdichten) (als Antwort verworfen: Das verbärge den Effekt nur im Playground, während ihn jeder Client mit gezeichneten oder projizierten Daten hat; der Playground projiziert weiter nur Stützpunkte, ADR 0010)