Natural neighbour interpolation, quality meshes and questions about whole surfaces
The terrain methods of ADR 0037 and ADR 0039 answer what a triangulation says in its triangles: the height at a point, the slope of a triangle, the volume above a plane. Four questions go beyond that and are asked in practice: a smooth height instead of the creases of the linear one, a finer mesh without sharp triangles as the input of a calculation, how much earth lies between two surfaces (before and after an excavation), and where it is steep, and what can be seen from where. This ADR adds them to Triangulation.
German version: 0041-natuerliche-nachbarn-qualitaetsnetze-und-flaechenfragen.de.md
Consequences
Placement: members of the class
Triangulation, in three partial files inSpatialNET.Extensions(Triangulation.Interpolation.cs,Triangulation.Refine.cs,Triangulation.Surfaces.cs). For the package validation and the API tracking this is an addition only (ADR 0028).API:
double InterpolateNaturalNeighbour(Coordinate point) Triangulation Refine(double minAngle = 20, double? maxArea = null, int maxSteinerPoints = 100_000) double MinAngle(int triangle) double MinAngle() (double Above, double Below) Volume(Triangulation other) IReadOnlyList<IPolygon2D> SlopeZones(IReadOnlyList<double> limits, IGeometryFactory? factory = null) bool LineOfSight(Coordinate from, Coordinate to, double observerHeight = 0, double targetHeight = 0)InterpolateNaturalNeighbouris Sibson interpolation. The height at a point is the mean of the heights of the vertices it would be connected to if it were inserted, weighted by the area of their Voronoi cells that the new point would take over. It is continuous, smooth except at the vertices, reproduces a plane exactly, and stays within the range of the heights around the point (a polynomial can overshoot, the linear interpolation has creases on every edge). How it is computed, with the structure that is already there:- The triangles whose circumcircle contains the point (exact
InCircle, ADR 0005) are the cavity that the point would cut out; they are found from the triangle that contains it by their neighbours. - The boundary of the cavity is the ring of the neighbours. The new Voronoi corners are the circumcentres of the point with every boundary edge, the old ones those of the cavity triangles, both from the circumcentre of the Voronoi diagram (ADR 0036), which is exact for slivers. The part that the new cell takes from a neighbour is the polygon of two new corners and the old corners between them; its area is the weight.
- The Delaunay property is required. A triangulation with constraints (a break line, a polygon) gives the linear
InterpolateZ, which is the right answer where a surface must have a crease. The same holds for a point on the hull (its cell is unbounded), and as a safeguard when an area cannot be computed (a circumcentre beyond double precision). A point on a vertex gives its height, a point outside the triangles and a neighbour without Z giveNaN, asInterpolateZdoes. - Tests: the definition itself as the oracle (the areas that every cell loses when the point is added, computed by the independent half-plane clipping of the Voronoi tests), a plane, the range of the heights, and the stress tests for dirty sites.
- The triangles whose circumcircle contains the point (exact
Refineis Delaunay refinement after Ruppert. It adds points until no triangle has an angle belowminAngle(degrees) or an area abovemaxArea. The surface stays what it was:- The border and the constraints stay where they are; an edge that is in the way of an added point (the point lies in its diametral circle) is split in the middle, so constraints become chains of shorter constrained edges (
IsConstrainedstays true on them, a border edge of a polygon stays a constraint). A triangulation fromFromPolygonstays inside its rings, with its holes. - The added points get their height from the triangulation that is refined, linear on a split edge, interpolated in the triangle for a circumcentre, so they lie on the original surface.
- A bad triangle is repaired by adding its circumcentre, unless that would encroach an edge, which is then split instead. The edges come first. The worst triangle is repaired first, one point at a time, in a mesh that is changed in place (ADR 0045: a triangle is divided, the edges around the new vertex are flipped back to Delaunay, and the edges of the border and the constraints are never flipped, only split); the work is proportional to the number of points that are added, not to the size of the mesh. (A first version rebuilt the triangulation after every round of insertions with the constrained Delaunay machinery of ADR 0038, which took 28 seconds for 100,000 points; found by the measurement.)
- Termination. Ruppert's method is proven to stop for
minAngleup to about 20.7 degrees when no two constraints meet at a smaller angle; in practice it stops to about 30. Above 34 degrees the call is rejected. Where the input has a smaller angle (the tip of a thin wedge) the sharp triangles at the tip cannot be avoided, and a triangle whose circumcircle is smaller than 1e-7 of the extent is left as it is.maxSteinerPointsends the work in any case, and the result is then a valid triangulation, only not as fine as asked. A call that has nothing to do returns the same instance. MinAngleis the smallest angle in degrees of a triangle (60 for an equilateral one) and of the whole triangulation (NaNwithout triangles).- Tests: no angle below the limit, the area, every original vertex kept, every new vertex on the surface (a plane as the oracle), the largest area, a break line that stays a chain of constrained edges on the line, a polygon with its border, the limit of the points, and stress tests on dirty sites.
- The border and the constraints stay where they are; an edge that is in the way of an added point (the point lies in its diametral circle) is split in the middle, so constraints become chains of shorter constrained edges (
Volume(other)is the cut and fill between two surfaces, exact over the area that both cover: the two triangulations are laid over each other, every triangle of one is cut with the triangles of the other (convex clipping against three half-planes, the candidates from the index), and over every piece the difference of two planes is a plane, so the volume above and below is the same integral asVolume(z)(ADR 0039).Aboveis where this surface lies above the other,Belowwhere it lies below; swapping the two swaps them, andAbove − Belowis the difference of the net volumes. Triangles with a vertex without Z are not counted; no common area gives (0, 0). Tests: slabs, a ramp against a plane, partial overlap, the equality withVolume(z)for a flat second surface, and the symmetry.SlopeZonesis the map of the slopes. The triangles are sorted into classes bySlope(class 0 below the first limit, classifrom limiti − 1up to limiti, the last from the last limit up) and every class becomes one polygon; a class without area is an empty polygon. The polygon is not made with the overlay: the edges that have a triangle of another class (or none) on the other side are the boundary, they are chained to rings with the area on the left, clockwise rings are holes and are given to the smallest ring that holds them, and a ring that touches itself in a vertex (a pocket that meets the border in a point, two parts that meet in a corner) is cut there, so that every ring is simple. The triangles of a triangulation never overlap, so nothing has to be united. The limits must be finite and strictly ascending. Tests: a flat part against a ramp, the classes tile the surface, every triangle lies in its class, every zone is valid and equals the union of its triangles (by the overlay, as the oracle), holes and parts that touch in a corner, and the stress test on dirty sites.LineOfSightasks whether the ground blocks the view. The line from the eye (the surface atfromplusobserverHeight) to the target (the surface attoplustargetHeight) is compared with the surface at every place where it crosses an edge or a vertex, which are the same cuts asDrape(ADR 0039), and the surface is linear between them, so that these places are all that has to be looked at. A line that only touches the ground (a flat field with both heights 0, a ridge exactly in the way) is free, with a tolerance of 1e-9 of the height. A point outside the surface or without a height givesfalse; where the line leaves the surface (a notch of a polygon) there is no ground to block it. Tests: a hill, flat ground, symmetry and that a higher eye or target never sees less.Speed. One-shot measurements (
--quick-terrain, Release build, uniform random points with heights):Points 100k InterpolateZ(ms)100k InterpolateNaturalNeighbour(ms)Volume(other)(ms)SlopeZones(ms)10k short LineOfSight(ms)1k long LineOfSight(ms)10,000 144 386 44 17 115 95 50,000 201 408 269 304 218 220 Points Refine(25)(ms)Triangles before → after Smallest angle before → after 1,000 31 1,978 → 5,705 0.00 → 25.00 10,000 181 19,977 → 51,884 0.00 → 25.00 100,000 2,195 199,974 → 510,423 0.00 → 25.00 Natural neighbour costs about two to two and a half times the linear height.
Refinegrows about linearly, and a 100,000 point surface is refined in two seconds.SlopeZonesneeds no overlay and takes a quarter of a second for 100,000 triangles (it took 14 seconds when the triangles were united withUnionAll). A line of sight (andDrape) costs the triangles along the line: it is cut into pieces of a few triangle sizes and the index is asked for the envelope of every piece, not for the envelope of the whole line, which for a diagonal grows with the square of its length (before this, 1,000 lines across 50,000 points took 1.8 seconds, now 0.2).Exceptions (ADR 0012):
ArgumentOutOfRangeExceptionfor coordinates or heights that are not finite, forminAngleoutside 0 to 34, for amaxAreathat is not greater than 0, for a negativemaxSteinerPointsand for a triangle index out of range;ArgumentNullExceptionfornull;ArgumentExceptionfor limits that are not finite or not ascending;InvalidOperationExceptionwithout a factory.Playground and documentation: entries
naturalNeighbour,refine,slopeZones,lineOfSightandsurfaceVolumewith examples (the terrain examples are shared, a new one for the view over a hill and one for an excavation), sections in the concept page "Triangulation, Voronoi and terrain", glossary entries.Not now: a grid or raster of interpolated values (call
InterpolateNaturalNeighbourper cell), natural neighbour with the break lines respected, Laplace or other interpolations, a viewshed (the area that can be seen from a point), and the conforming and the minimum-size meshes of Shewchuk (the offcentre and the concentric shells at small input angles).
Considered Options
- Natural neighbour by inserting the point into a copy of the mesh and reading the areas from it (rejected: it copies the triangulation for every query; the cavity of the point and the areas of the Voronoi cells give the same weights from the unchanged structure)
- Laplace (non-Sibson) interpolation, which needs only edge lengths (rejected: it is not the usual reference, and its weights differ from the Sibson ones, so a user who compares with other software gets different numbers; it can be added)
- Natural neighbour with the constraints respected (rejected: the cavity logic needs the Delaunay property, and a constraint means that the surface has a crease, which the smooth interpolation is meant to remove; the fallback to the linear height is the honest answer)
- Refining by rebuilding the constrained triangulation after every round of insertions (the first version; rejected after the measurement: it reuses the tested code, but costs a full construction per round, 28 seconds for 100,000 points, against 2 seconds with a mesh that is changed in place, ADR 0045)
- Refinement with the proofs of Shewchuk (offcentres, concentric shells for small input angles) (rejected for now: the size floor and the cap on the points make the method stop, and the guarantee of the angle holds where the input allows it)
- A function that returns a raster or grid of heights (rejected: a grid is a different structure of the library, and the call per cell is simple; the natural neighbour has no creases, so a coarse grid is enough)
Volume(other)by sampling both surfaces on a grid (rejected: not exact; the cut of two linear surfaces is exact and fast)- A viewshed instead of a single line of sight (rejected for now: a viewshed is a polygon from a sweep around the observer, a bigger piece of work; the line of sight is its building block and answers the question for one point)