How it works
The convex hull of a set of points is the smallest convex solid that holds them all: stretch a
skin round them and it pulls tight into flat faces. Points on a sphere are all on the outside, so every
one is a corner of the hull, and its faces are triangles (unless four or more points share a plane).
A closed solid of triangles with n corners has 2n - 4 faces and 3n - 6 edges.
Hull to sphere pushes each flat face out along rays from the centre until it lies on the sphere.
The same three corners now bound a spherical triangle with great-circle sides, and together those
triangles are the Delaunay triangulation on the sphere. The reason is the face's plane: it cuts
the sphere in a circle through its three points (Circle), and every other point is on the inner
side of the plane, so the cap beyond it holds no point. An empty circle through three points is what
makes a triangle Delaunay.
The face's outward normal, from the centre of the sphere, meets the sphere at the middle of
that cap: the point equally far from the three corners and no nearer to any other. That is a
Voronoi vertex. Join the normals of faces that share an edge with great-circle arcs and you
have the Voronoi diagram, the cells of the sphere nearer to one point than to any other.
Nothing more than the hull is needed for either.
Ties. The corners of a cube put four points on each face's circle. The hull's square faces
can be split into triangles along either diagonal, both equally Delaunay, and their two Voronoi
vertices are the same point. The hull here breaks ties with a fixed jitter far below anything drawn,
so a square comes out as two triangles in one plane.
One hemisphere. When the points fit in a hemisphere the centre of the sphere is outside the
hull. The faces it can see (amber) have circles wider than a hemisphere, and pushed out from the
centre they land on the same ground as the others, with arcs that cross them. Leave them out and the
rest triangulate only the points' hull on the sphere, as STRIPACK does. Keep them and they are the
sphere's version of the outside of a map, and the Voronoi diagram still needs all of them.
The map is stereographic, which takes every circle on the sphere to a circle in the plane. So
each face's circle is its triangle's circumcircle in the map, still empty, and the triangles there are
the planar Delaunay triangulation of the mapped points. That is Brown's (1979) route to planar
Delaunay and Voronoi: lift the plane onto a sphere by inverse stereographic projection and take the
hull. The point opposite the map centre goes to infinity; the faces whose circle holds it are the
outside of the map, and their edges with the rest (Faces on, in green) are the convex hull of
the points in the plane. Lifting onto a paraboloid instead of a sphere (Edelsbrunner and Seidel, 1986)
is the same trick, and d3-geo-voronoi runs it backwards, building the Delaunay on the sphere from a
stereographic projection and a planar triangulation.
The hull is the incremental one (Clarkson and Shor, 1989; de Berg et al. chapter 11): start from four
points, add each in turn, remove the faces it can see and join it to their rim. Qhull (Barber et al.,
1996), behind scipy.spatial and R's geometry, does the same job faster. Core
in src/core/sphull.js, checked in test/check-sphull.mjs: Euler's counts,
empty circles, cells that tile the sphere, the map against proj4js and the map's hull against a planar
one.
Hash keys: set, n, seed, pts (edited points, lon,lat
pairs), inflate, hull, del, vor, cells,
circ, coast, mlon, mlat, z (map zoom),
cam.
- Brown, K. Q. (1979) Voronoi diagrams from convex hulls, Information Processing Letters 9(5),
223-228.
- Clarkson, K. L. and Shor, P. W. (1989) Applications of random sampling in computational geometry,
II, Discrete and Computational Geometry 4, 387-421.
- de Berg, M., Cheong, O., van Kreveld, M. and Overmars, M. (2008) Computational Geometry: Algorithms
and Applications, 3rd edition, Springer.
- Edelsbrunner, H. and Seidel, R. (1986) Voronoi diagrams and arrangements, Discrete and
Computational Geometry 1, 25-44.
- Barber, C. B., Dobkin, D. P. and Huhdanpaa, H. (1996) The Quickhull algorithm for convex hulls, ACM
Transactions on Mathematical Software 22(4), 469-483 (Qhull).
- Renka, R. J. (1997) Algorithm 772: STRIPACK, Delaunay triangulation and Voronoi diagram on the
surface of a sphere, ACM Transactions on Mathematical Software 23(3), 416-434.
- Van Oosterom, A. and Strackee, J. (1983) The solid angle of a plane triangle, IEEE Transactions on
Biomedical Engineering 30(2), 125-126 (triangle and cell areas).
- d3-geo-voronoi, Philippe Riviere.
- Station positions are approximate. Coastlines from Natural
Earth; the map checked with proj4js; drawn with
three.js.