trianglewins / sizing

Sizing fields and map projections

laridae's refinement takes a sizing field: the largest triangle area allowed at each point, as a function or a grid (laridae: refinement, angle, area and sizing fields). A map projection already stretches space, so a mesh that is uniform in one CRS is graded somewhere else. When can a projection do the job of a sizing field, and what is left that only the mesh engine can do?

The short version:

What a map does to a mesh

Mesh uniformly in a CRS and then transform the vertices. Close up, the transform is a linear map: a scale in each of two directions, the axes of the Tissot ellipse, a (the larger) and b. Then:

A laridae sizing field is one number per point. It asks for "this big, and still well shaped". Count what each side can supply:

what you want functions to choose can a map supply it?
area only, shape does not matter 1, any yes, always: some map has exactly that area density (the "equidistribution" map of moving-mesh methods)
size with good shape (laridae size=) 1, any only if log of size is harmonic, using a conformal map
deliberately stretched triangles (a metric) 3 only if the metric is flat, because a map has just 2 functions
constraints, holes, breaklines, feature size, grading limits none no: these come from the input, not from space

Conformal: the right shape, for a narrow set of fields

In a conformal map a = b = k, so a uniform mesh comes out with edges scaled by 1/k and the same angles. The size field it implies is k itself. For a map from flat to flat, log k is always harmonic (its Laplacian is zero). That is a strong restriction:

On the sphere there is even less choice: the conformal maps to the plane are stereographic, Mercator, Lambert conformal conic and their relatives, each with its own fixed scale pattern.

The unit square meshed four ways: laridae's linear area field by the engine and by a stretch map, and an exponential field by a conformal map and by the engine. Below each, the smallest angle of every triangle

case how smallest angle (30 requested)
(a) linear area field engine sizing field 30.3
(b) the same field uniform mesh in x' = G(x), mapped back 8.8
(c) exponential field uniform mesh in w = exp(-z log(21) / 2), mapped back 29.6
(d) exponential field engine sizing field 30.3

The stretch map in (b) gets the areas right (the median area is the same share of the target as the engine's), but the triangles are squashed at one end and pulled out at the other, 21 to 1 across the square. In (c) the field is log-linear, so a conformal map does it, and it matches the engine in both size and shape.

Equal-area: the right size, the wrong shape

An equal-area projection keeps a times b = 1, so a uniform mesh has uniform ground area. Away from the centre a and b part, though, so the angle guarantee is spent on the Tissot ellipse. A sizing field changes size, not shape, so nothing applied later gets the angles back.

The northern hemisphere, meshed uniformly in polar stereographic, in polar stereographic with a compensating field, and uniformly in Lambert azimuthal equal-area. Colour is ground area on one scale; below, the smallest angle of every triangle measured on the sphere

Northern hemisphere, polar aspect, smallest angle 30 requested in the CRS, everything measured on the sphere:

case ground area, pole / equator smallest angle on the sphere edges not Delaunay on the sphere
stereographic, uniform 2.89 29.8 0
stereographic, area = target times k^2 1.06 29.3 0
Lambert azimuthal equal-area, uniform 0.99 18.8 5.8%

The middle row is the recipe: a conformal CRS plus a scalar field that compensates for its scale gives triangles that are the same size and well shaped on the ground. The projection supplies the shape and the field supplies the size. With an equal-area CRS the size comes free and the shape is gone for good.

Do angle guarantees survive?

Refinement promises a smallest angle in the CRS it ran in. After the transform:

The Delaunay property is a sharper story. Stereographic maps circles to circles, so a Delaunay mesh in polar stereographic is exactly Delaunay on the sphere (no failures above). That is special to stereographic. Other conformal maps keep circles only approximately, and the equal-area map broke 5.8% of edges. If it matters downstream (interpolation, Voronoi cells), flip edges again on the target surface after the transform; the vertices stay where they are. Grids as meshes shows the same thing from the other direction: Delaunay in which frame is a choice made before meshing.

Edges after the transform

A straight edge in the CRS is a curve in the target. Measured as the gap between the transformed edge and the great circle at its midpoint, divided by edge length: about 0.003 typically and 0.01 to 0.013 at most for these meshes, smaller for smaller triangles. Three things follow, and they are about the mesh, not about stretching:

  1. Densify constraints in the meshing CRS. A breakline that is straight on the ground is a curve in the CRS. Give the engine that curve, densified, or the transformed mesh will not follow it. Curves: bigcurve and s2 covers how.
  2. Say which straight line you mean. The transformed chord, the great circle and the rhumb line differ by about the same amount as the gap above. A mesh stores vertices and connectivity, so an edge is straight in whatever space it is drawn in, and that is worth writing down.
  3. Check for flipped triangles. Coarse triangles where a projection bends hard (near its edge or a seam) can turn over when transformed. The sign of each triangle's orientation in the target catches it.

A field from data: population density

Triangles graded by population are a popular way to draw density: put vertices where people are and connect them. That is a sizing field, and a good test of everything above.

No projection can produce it. A conformal map's log scale is harmonic, and a harmonic function has no peaks or pits away from the edge of its domain (the maximum principle). Population has a pit in triangle size at every city, so no conformal map gives it with good shapes. A projection can put one fine spot at a singular point (Mercator at a pole, log-polar at its centre), never one per city. An area-only map (moving-mesh equidistribution) could match the density, at the cost of shape, as in panel (b) of the square above.

So it is the engine's job. Below, the Americas mainland is meshed in an oblique stereographic CRS centred at 10N 80W, following the recipe: the ground density is a Gaussian kernel (sigma 120 km) over Natural Earth places weighted by population, plus a rural floor of 2 people per km2; the target ground area is about 63,000 people per triangle, held between 15 km and 600 km on a side; and the CRS area is that times the PROJ areal scale k^2. Three meshes:

The Americas meshed by population density three ways: Delaunay of points sampled by population, refinement to the population sizing field without an angle bound, and with a 30 degree bound. Below, the US north east up close

mesh vertices triangles obtuse smallest angle under 20 smallest angle, 1st percentile
sampled points, Delaunay 10,019 18,499 53% 25% 3.8
refined, area only 7,807 13,956 22% 3.1% 10.3
refined, min angle 30 10,019 17,200 18% 0.3% 30.4

All three show the same density pattern from a distance. Up close, the sampled mesh is mostly obtuse slivers, because random points land arbitrarily close to each other and Delaunay can only choose the best of a bad set. The refined meshes put each new vertex at the centre of a too-large or too-skinny triangle, so the points are spaced by construction; the angle bound removes most of what is left. The few triangles still under 20 degrees sit at sharp corners in the coastline, where the input angle itself is small. The sampled look is a fine aesthetic. For a mesh that will carry values (interpolation, a finite-volume model, a heat map that should not show the triangles), refinement gives the same grading without the slivers.

The figure and numbers come from survey/sizing/population.py (numpy, matplotlib, triangle, shapely, pyproj; it downloads Natural Earth from GitHub).

What only the engine can do

A recipe for laridae and cdtr

  1. Choose a conformal CRS for the region: polar stereographic, Lambert conformal conic, or Mercator for a band of latitude. Angles survive and, in polar stereographic, so does Delaunay.
  2. Densify the constraints in that CRS, following the curve they make on the ground (bigcurve).
  3. Write the target as a ground area A(lon, lat) and give laridae size = function(x, y) A(inverse(x, y)) * k(x, y)^2. PROJ reports the scale factors: for a conformal projection the areal scale is k^2.
  4. Transform the vertices, flip to Delaunay on the target if needed, and check that no triangle has turned over.

cdtr refines to one global max_area and min_angle, with no field, so for cdtr the projection is the only lever for grading: choose a conformal CRS and accept its scale pattern, which is size proportional to 1/k on the ground.

The figures and numbers come from survey/sizing/experiments.py (numpy, matplotlib, triangle). It uses Shewchuk's Triangle, from the same Delaunay refinement family as laridae, so it runs without CGAL; an R version with laridae and PROJ scale factors on a real region is still to do.