Glätten von Linien und der Fläche unter Höhenlinien
Höhenlinien kommen aus einer Triangulierung als Ketten gerader Stücke mit einem kleinen Knick an jeder Dreieckskante, und ein Fluss oder eine Straße, die als Polylinie digitalisiert wurde, hat Ecken, wo geklickt wurde. Zwei Arten der Glättung antworten darauf: Smooth rundet jede Linie (und die Ringe eines Polygons), und Triangulation.Resample glättet die Fläche, sodass Höhenlinien von ihr glatt sind und sich, in der Natur einer Fläche, nicht kreuzen können.
English version: 0043-glaetten-von-linien-und-flaechen.md
Consequences
Ort:
Smoothund die AufzählungSmoothingMethodin einer neuen statischen KlasseSmoothing(Smoothing.cs),Resampleein Mitglied vonTriangulationin einer eigenen Datei (Triangulation.Resample.cs), beides inSpatialNET.Extensions. Für die Paketvalidierung und die API-Verfolgung ist das nur eine Ergänzung (ADR 0028).API:
IPolyline2D Smooth(this IPolyline2D line, int iterations = 2, SmoothingMethod method = SmoothingMethod.Chaikin, IGeometryFactory? factory = null) IPolygon2D Smooth(this IPolygon2D polygon, int iterations = 2, SmoothingMethod method = SmoothingMethod.Chaikin, IGeometryFactory? factory = null) IGeometry2D Smooth(this IGeometry2D geometry, int iterations = 2, SmoothingMethod method = SmoothingMethod.Chaikin, IGeometryFactory? factory = null) IPolyline2D SmoothToTolerance(this IPolyline2D line, double tolerance, SmoothingMethod method = SmoothingMethod.Chaikin, IGeometryFactory? factory = null) // und dasselbe für IPolygon2D und IGeometry2D enum SmoothingMethod { Chaikin, CatmullRom } Triangulation Triangulation.Resample(double cellSize, bool keepVertices = false)Smoothersetzt jeden Pfad durch eine Kurve mit2^iterations-mal so vielen Segmenten (iterationsvon 0, das ist eine Kopie, bis 10; das Ergebnis darf das Stützpunktbudget vonDensifynicht überschreiten, ADR 0019). Die typisierten Überladungen folgenDensify: Ein Polygon wird nach seiner Normalisierung Ring für Ring geglättet, ein Punkt oder Multipunkt wird kopiert.Chaikinschneidet jede Ecke bei einem Viertel der beiden angrenzenden Segmente ab. Die Kurve ist ein quadratischer B-Spline: Sie bleibt in der konvexen Hülle der Stützpunkte, schwingt nie über und entfernt sich von den Stützpunkten (sie geht nicht hindurch). Innerhalb der Hälfte des längsten Segments der Eingabe folgt sie der Eingabe.CatmullRomist ein zentripetaler Spline (alpha 0,5, die Form nach Barry–Goldman): Er geht durch jeden Stützpunkt, ohne die Schleifen und Spitzen der gleichmäßigen Variante bei ungleichem Abstand. Zwischen zwei Stützpunkten kann er etwas überschwingen. Der fehlende Nachbar an einem Ende ist das Spiegelbild des nächsten Stützpunkts. Zwischen zwei Punkten, die so dicht beieinander liegen, dass die Knoten sie nicht unterscheiden (ein Abstand von 1e-69 neben einem von 1, vom Stresstest gefunden), gibt es keine Kurve: Die Spanne bleibt gerade.- Enden, geschlossene Pfade, Z und M. Die Enden eines offenen Pfads bleiben. Ein Pfad, dessen erster und letzter Punkt gleich sind (mit mindestens drei verschiedenen Punkten), ist geschlossen und wird ganz herum geglättet, bleibt also geschlossen und hat keine Ecke an seinem Anfang. Aufeinanderfolgende Punkte mit gleichem X und Y zählen einmal. Z und M werden linear entlang der Segmente mit demselben Parameter interpoliert (auch beim Spline: Nur X und Y folgen der Kurve), sodass eine Höhenlinie ihre Höhe genau behält und M monoton bleibt. Ein Pfad aus zwei Punkten hat nichts zu glätten.
- Auf eine Distanz statt auf eine Zahl von Durchläufen:
SmoothToTolerance(tolerance, method). Die Segmente werden so oft halbiert, bis kein Stützpunkt weiter alstolerancevon der Linie zwischen seinen beiden Nachbarn liegt, sodass das Ergebnis im Maßstab der Toleranz wie eine Kurve aussieht und nicht feiner (eine Linie, die schon so glatt ist, wird unverändert zurückgegeben). BeiChaikinist das ein Durchlauf nach dem anderen, höchstens 10; beiCatmullRomdieselbe Zahl von Stücken für jede Spanne (1, 2, 4 … höchstens 1024), damit auch die Ecke an einem Stützpunkt zählt (eine erste Fassung entschied je Spanne aus ihren inneren Punkten und übersah die Spitze an einem scharfen Stützpunkt: vom Test gefunden). Das Stützpunktbudget vonDensifybeendet die Arbeit früher, eine sehr kleine Toleranz gibt also das Feinste, das erlaubt ist. Die Toleranz ist in den Einheiten der Koordinaten. Sie begrenzt den Abstand des Polygonzugs zur Kurve im Sinne der nächsten Verfeinerung, nicht, wie scharf die Kurve selbst ist: Das Glätten einer Spitze mitChaikinlässt eine schmale Spitze stehen, deren Polygonzug innerhalb der Toleranz ihrer Kurve liegt. Es ist ein eigener Name und keine ÜberladungSmooth(line, double), weilSmooth(line, 1)sonst stillschweigend einen Durchlauf bedeutete, wo ein Meter gemeint war. - Keine Garantie gegen Kreuzungen. Die Kurve folgt der Linie innerhalb eines Teils des längsten Segments, also können sich zwei Linien, die dichter nebeneinander laufen, nach dem Glätten kreuzen, und ein Polygon, dessen Teile so dicht sind, kann ungültig werden (ein Ring wird an konvexen Ecken nach innen und an Reflexecken nach außen abgeschnitten;
MakeValidrepariert das).Smoothist für das, was Platz hat; für Höhenlinien ist die Fläche der bessere Ort zum Glätten (nächster Punkt).
Resampleglättet die Fläche. Die Höhen eines regelmäßigen Rasters der ZellecellSize(an Vielfachen davon ausgerichtet) werden mitInterpolateNaturalNeighbour(ADR 0041) interpoliert, und die Rasterpunkte werden zusammen mit dem Rand und den Zwangskanten durch die Constrained-Delaunay-Maschinerie aus ADR 0038 (der Neubau aus Punkten und Kanten, denRefinein seiner ersten Fassung benutzte, ADR 0045) innerhalb des Gebiets des Originals neu trianguliert. Die Randeckpunkte und die Bruchkanten behalten ihre Höhen, und die überdeckte Fläche ist dieselbe, auch bei einem Polygon mit Löchern.- Warum das Glätten der Fläche Höhenlinien auseinanderhält. Über einem Dreieck ist die Fläche eine Ebene, also sind die Höhenlinien verschiedener Höhen dort parallele Strecken. Sie können sich innerhalb eines Dreiecks nicht kreuzen, und wo sie es verlassen, treffen sie das Nachbardreieck an denselben Punkten der gemeinsamen Kante. Also kreuzen sich die Linien jeder Triangulierung nicht, und die Linien einer feineren sind feiner: Das kann
Smootheiner Linie nicht versprechen. - Die inneren Eckpunkte entfallen standardmäßig. Eine Interpolation geht durch ihre Daten, und die Fläche der natürlichen Nachbarn hat an jeder Messung einen Punkt (überall sonst ist sie glatt). Die Messpunkte zu behalten, ließe an jedem einen Knick in der Höhenlinie stehen: Gemessen an z = x² + y² mit 120 verstreuten Punkten ist der mittlere Richtungswechsel einer Höhenlinie 8,0° auf der ursprünglichen Fläche, 8,0° auf der neu abgetasteten mit den Messpunkten und 5,6° ohne sie. Deshalb lässt der Standard sie weg: Das Ergebnis ist eine geglättete Fläche, wie ein Raster, das aus den Messpunkten interpoliert wurde, und
keepVertices: truebehält sie für eine Fläche, die hindurchgehen muss. Eckpunkte auf dem Rand oder auf einer Zwangskante bleiben immer, ebenso die Bruchkanten. - Glatt ist nicht dasselbe wie näher an der Wahrheit. Derselbe Test misst den Abstand der Höhenlinie vom wahren Kreis: 0,88 auf der neu abgetasteten Fläche (mit den Messpunkten) gegen 0,47 auf der ursprünglichen. Die Interpolation einer gekrümmten Fläche durch natürliche Nachbarn ist zu den Nachbarn hin verzerrt, die einen Punkt umgeben, ungefähr so stark wie die lineare Interpolation (eine konvexe Funktion wird um die Streuung der Nachbarn zu hoch interpoliert, und die natürlichen Nachbarn streuen weiter als die drei Ecken eines Dreiecks). Die Dokumentation sagt deshalb glatt, nicht genau.
- Rasterartefakte. Auf einem regelmäßigen Raster knickt eine Höhenlinie um Vielfache von 45° ab, wo sie eine Diagonale kreuzt, sodass der größte Richtungswechsel größer sein kann als beim Original (39° gegen 32° im Test). Danach mit
Smoothrunden (ein oder zwei Durchläufe): erst die Fläche, dann die Linien. - Wo natürliche Nachbarn nicht gehen (eine Triangulierung mit Zwangskanten, ein Punkt auf der Hülle, ADR 0041), sind die Höhen der Rasterpunkte die linearen: Das Ergebnis ist feiner, nicht glatter. Rasterpunkte auf einem Eckpunkt, auf dem Rand oder auf einer Zwangskante entfallen, Eckpunkte ohne Z geben Punkte ohne Z, eine Zellgröße, die mehr als fünf Millionen Rasterpunkte ergäbe, wird abgelehnt, und der Aufruf gibt dieselbe Instanz zurück, wenn kein Rasterpunkt innen liegt.
- Parallel. Die Höhen werden zeilenweise parallel berechnet und in der Reihenfolge der Zeilen zusammengefügt, das Ergebnis ist also bei jedem Lauf dasselbe.
- Warum das Glätten der Fläche Höhenlinien auseinanderhält. Über einem Dreieck ist die Fläche eine Ebene, also sind die Höhenlinien verschiedener Höhen dort parallele Strecken. Sie können sich innerhalb eines Dreiecks nicht kreuzen, und wo sie es verlassen, treffen sie das Nachbardreieck an denselben Punkten der gemeinsamen Kante. Also kreuzen sich die Linien jeder Triangulierung nicht, und die Linien einer feineren sind feiner: Das kann
Geschwindigkeit. Einmalmessungen (
--quick-terrain, Release-Build):Resamplevon 10.000 Punkten auf ein Raster mit vier Punkten je Messung (40.000 Eckpunkte, 79.000 Dreiecke) braucht 0,25 s, von 50.000 Punkten (200.000 Eckpunkte) 1,0 s.Smootheiner Linie mit 100.000 Stützpunkten mit drei Durchläufen braucht für beide Verfahren 90 ms.Tests (ADR 0008):
Smooth: eine Ecke, geschlossene Pfade, die Zahl der Stützpunkte, Enden und konvexe Hülle, die Schranke der Hälfte des längsten Segments, eine Gerade, Z und M, der Spline durch jeden Stützpunkt, ein abgetasteter Kreis, Polygone und Löcher, Fehler.Resample: Eine Ebene bleibt eine Ebene (auch mitkeepVertices), der Rand und die Fläche, Rasterpunkte an Vielfachen der Zellgröße und die Reihenfolge der Threads, die Richtungswechsel einer Höhenlinie gegen das Original und gegen die Fassung mit den Messpunkten, Höhenlinien verschiedener Höhen, die sich nicht berühren (zufälliges Gelände), ein Polygon und eine Bruchkante, kein Z, Fehler. Ein Kochbuch-Rezept mit den zwei Schritten.Playground und Dokumentation: der Eintrag
smooth(Durchläufe und Verfahren; eine Zickzacklinie und ein Polygon als Beispiele), die ParametercellSizeundsmoothvoncontourundcontourBands(und ein Beispiel „A smoothed hill“), ein Rezept im Kochbuch, Glossareinträge, die Konzeptseite.Nicht jetzt: das Glätten der Stufen von
ContourBands(benachbarte Stufen müssen die geglättete Linie teilen, sie müssten also aus den geglätteten Linien gebaut werden, was eine andere Konstruktion ist), Bézier und andere Splines und ein Glätten, das gegebene Stützpunkte festhält.
Considered Options
- Nur die Linien glätten, durch einen Spline oder Eckenschneiden (als einzige Antwort verworfen: Es ist, was ein allgemeines
Smoothtut, aber es kann zwei Linien nicht auseinanderhalten, was bei Höhenlinien zählt, also wird auch die Fläche geglättet) - Höhenlinien aus einem regelmäßigen Raster durch Marching Squares auf bilinearen Zellen (verworfen: Eine Triangulierung des Rasters und
Contourliefern dieselben sich nicht kreuzenden Linien mit der vorhandenen Maschinerie, und die Sattelfälle von Marching Squares entfallen) - Die Messpunkte in der neu abgetasteten Fläche standardmäßig behalten (verworfen: Die gemessenen Knicke in den Höhenlinien bleiben; als Option
keepVerticeserhalten) - Nur auf das Raster abtasten, ohne Rand und Zwangskanten (verworfen: Die Fläche würde am Rand zu einer Treppe von einer Zelle Breite, und Bruchkanten gingen verloren)
- Ein Parameter
smoothanContourundContourBands(verworfen:terrain.Resample(5).Contour(z).Smooth(2)sagt dasselbe, und die Linien sind der einzige Teil, denSmoothkennen muss) - Kubische Bézier- oder B-Splines mit einer Toleranz als Standardverfahren (vorerst verworfen: Zwei Verfahren, die jeder kennt, eines annähernd und eines interpolierend, decken ab, was gefragt ist; eine Toleranz kann folgen)
- Das Ergebnis in
Smoothfür ein Polygon gültig machen (verworfen: Die Kosten einer Prüfung bei jedem Aufruf für einen Fall, der Merkmale braucht, die dichter beieinander liegen, als das Glätten bewegt;MakeValidist ein Aufruf entfernt)