Smoothing lines, and the surface under contour lines
Contour lines come out of a triangulation as chains of straight pieces with a small crease at every edge of a triangle, and a river or a road digitised as a polyline has corners where the operator clicked. Two kinds of smoothing answer this: Smooth rounds any line (and the rings of a polygon), and Triangulation.Resample smooths the surface, so that contour lines of it are smooth and, by the nature of a surface, cannot cross.
German version: 0043-glaetten-von-linien-und-flaechen.de.md
Consequences
Placement:
Smoothand the enumSmoothingMethodin a new static classSmoothing(Smoothing.cs),Resamplea member ofTriangulationin its own file (Triangulation.Resample.cs), both inSpatialNET.Extensions. For the package validation and the API tracking this is an addition only (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) // and the same for IPolygon2D and IGeometry2D enum SmoothingMethod { Chaikin, CatmullRom } Triangulation Triangulation.Resample(double cellSize, bool keepVertices = false)Smoothreplaces every path by a curve with2^iterationstimes as many segments (iterationsfrom 0, which is a copy, to 10; the result must not exceed the vertex budget ofDensify, ADR 0019). The typed overloads followDensify: a polygon is smoothed ring by ring after its normalization, a point or multipoint is copied.Chaikincuts every corner at a quarter of the two adjacent segments. The curve is a quadratic B-spline: it stays inside the convex hull of the vertices, never overshoots, and moves away from the vertices (it does not pass through them). Within half of the longest segment of the input it follows the input.CatmullRomis a centripetal spline (alpha 0.5, the Barry–Goldman form): it passes through every vertex, without the loops and the cusps of the uniform variant at uneven spacing. It can overshoot a little between two vertices. The missing neighbour at an end is the mirror image of the next vertex. Between two points so close together that the knots cannot tell them apart (a spacing of 1e-69 next to one of 1, found by the stress test) there is no curve: the span stays straight.- Ends, closed paths, Z and M. The ends of an open path stay. A path whose first and last point are the same (with at least three different points) is closed and is smoothed all the way round, so it stays closed and has no corner at its start. Consecutive points with the same X and Y count once. Z and M are interpolated linearly along the segments with the same parameter (for the spline too: only X and Y follow the curve), so a contour line keeps its height exactly and M stays monotonic. A path of two points has nothing to smooth.
- To a distance instead of a number of iterations:
SmoothToTolerance(tolerance, method). The segments are halved as often as it takes for no vertex to lie further thantolerancefrom the line between its two neighbours, so that the result looks like a curve at the scale of the tolerance and no finer (a line that is that smooth already is returned as it is). ForChaikinthat is one iteration after the other, at most 10; forCatmullRomthe same number of pieces for every span (1, 2, 4 … at most 1024), so that the corner at a vertex counts as well (a first version decided per span from its inner points and missed the cusp at a sharp vertex: found by the test). The vertex budget ofDensifyends the work early, so a very small tolerance gives the finest that is allowed. The tolerance is in the units of the coordinates. It is a bound on the distance of the polyline to the curve in the sense of the next refinement, not on how sharp the curve itself is: smoothing a spike withChaikinleaves a narrow spike whose polyline is within the tolerance of its curve. It is a separate name, and not an overloadSmooth(line, double), becauseSmooth(line, 1)would otherwise silently mean one iteration where one metre was meant. - No guarantee against crossings. The curve follows the line within a part of the longest segment, so two lines that run closer than that can cross after smoothing, and a polygon whose parts are that close can become invalid (a ring is cut inwards at its convex corners and outwards at the reflex ones;
MakeValidrepairs it).Smoothis for what has room; for contour lines the surface is the better place to smooth (next point).
Resamplesmooths the surface. The heights of a regular grid ofcellSize(aligned to multiples of it) are interpolated withInterpolateNaturalNeighbour(ADR 0041), and the grid points together with the border and the constraints are triangulated again by the constrained Delaunay machinery of ADR 0038 (the rebuild from points and segments thatRefineused in its first version, ADR 0045), inside the domain of the original. The border vertices and the break lines keep their heights, and the area that is covered is the same, also for a polygon with holes.- Why smoothing the surface keeps contour lines apart. Over a triangle the surface is a plane, so the contour lines of different heights are parallel straight lines there. They cannot cross inside a triangle, and where they leave it they meet the neighbouring triangle at the same points on the shared edge. So the lines of any triangulation do not cross, and the lines of a finer one are finer: that is what
Smoothof a line cannot promise. - The inner vertices are dropped by default. An interpolation passes through its data, and the natural neighbour surface has a point at every measurement (it is smooth everywhere else). Keeping the measurements would keep a kink in the contour line at every one of them: measured on z = x² + y² with 120 scattered points, the mean change of direction of a contour line is 8.0° on the original surface, 8.0° on the resampled one with the measurements and 5.6° without them. So the default drops them: the result is a smoothed surface, as a raster that was interpolated from the measurements is, and
keepVertices: truekeeps them for a surface that must pass through them. Vertices on the border or on a constraint are always kept, so are the break lines. - Smooth is not the same as closer to the truth. The same test measures the distance of the contour from the true circle: 0.88 on the resampled surface (with the measurements) against 0.47 on the original. Natural neighbour interpolation of a curved surface is biased towards the neighbours that surround a point, about as much as the linear interpolation is (a convex function is interpolated too high by the spread of the neighbours, and the natural neighbours spread wider than the three corners of one triangle). The documentation therefore says smooth, not accurate.
- Grid artefacts. On a regular grid a contour line turns by multiples of 45° where it crosses a diagonal, so the largest change of direction may be larger than on the original (39° against 32° in the test). Round the lines afterwards with
Smooth(one or two iterations): surface first, lines second. - Where natural neighbour cannot be used (a triangulation with constraints, a point on the hull, ADR 0041) the heights of the grid points are the linear ones: the result is finer, not smoother. Grid points on a vertex, on the border or on a constraint are left out, vertices without Z give points without Z, a cell size that would give more than five million grid points is rejected, and the call returns the same instance if no grid point lies inside.
- Parallel. The heights are computed in parallel by row and joined in row order, so the result is the same on every run.
- Why smoothing the surface keeps contour lines apart. Over a triangle the surface is a plane, so the contour lines of different heights are parallel straight lines there. They cannot cross inside a triangle, and where they leave it they meet the neighbouring triangle at the same points on the shared edge. So the lines of any triangulation do not cross, and the lines of a finer one are finer: that is what
Speed. One-shot measurements (
--quick-terrain, Release build):Resampleof 10,000 points to a grid of four points per measurement (40,000 vertices, 79,000 triangles) takes 0.25 s, of 50,000 points (200,000 vertices) 1.0 s.Smoothof a line of 100,000 vertices with three iterations takes 90 ms for both methods.Tests (ADR 0008):
Smooth: a corner, closed paths, the number of vertices, ends and convex hull, the bound of half the longest segment, a straight line, Z and M, the spline through every vertex, a sampled circle, polygons and holes, errors.Resample: a plane stays a plane (also withkeepVertices), the border and the area, grid points at multiples of the cell size and the order of the threads, the turning of a contour line against the original and against the version with the measurements, contour lines of different heights that do not touch (random terrain), a polygon and a break line, no Z, errors. A cookbook recipe with the two steps.Playground and documentation: the entry
smooth(iterations and method; a zigzag line and a polygon as examples), the parameterscellSizeandsmoothofcontourandcontourBands(and an example, "A smoothed hill"), a recipe in the cookbook, glossary entries, the concept page.Not now: smoothing the bands of
ContourBands(neighbouring bands have to share the smoothed line, so they have to be made from the smoothed lines, which is a different construction), Bézier and other splines, and smoothing that keeps given vertices fixed.
Considered Options
- Smoothing only the lines, by a spline or corner cutting (rejected as the only answer: it is what a general
Smoothdoes, but it cannot keep two lines apart, which matters for contour lines, so the surface is smoothed as well) - Contour lines from a regular grid by marching squares on bilinear cells (rejected: a triangulation of the grid and
Contourgive the same non-crossing lines with the machinery that exists, and the saddle cases of marching squares are avoided) - Keeping the measurements in the resampled surface by default (rejected: the measured kinks in the contour lines stay; kept as the option
keepVertices) - Resampling onto the grid only, without the border and the constraints (rejected: the area would become a staircase one cell wide at the border, and break lines would be lost)
- A
smoothparameter onContourandContourBands(rejected:terrain.Resample(5).Contour(z).Smooth(2)says the same, and the lines are the only part thatSmoothhas to know about) - Cubic Bézier or B-spline with a tolerance as the default method (rejected for now: two methods that everyone knows, one approximating and one interpolating, cover what is asked; a tolerance can follow)
- Making the result valid inside
Smoothfor a polygon (rejected: the cost of a check on every call for a case that needs features closer together than the smoothing moves;MakeValidis one call away)