Table of Contents
Hyperbolic Voronoi diagrams with Vorosketch
Vorosketch can draw Voronoi diagrams of sites in the hyperbolic plane, rendered according to one of various models/projections. Sites can be specified in the following ways:
- random point sites uniformly distributed in the hyperbolic unit disk1) can be generated with the -@ option;
- some pre-defined sets of sites can be generated with the -# option (25 or 79 sites in the origin and in two or three rings around it; 50 vertices of a tiling with equilateral triangles);
- user-defined point sites can be specified on the input in the usual way by giving their Cartesian coordinates in the chosen model/projection.
Currently, Vorosketch does not implement conversions between models/projections in all directions. As a result, sites generated with -@ or -# will not be drawn in the diagram: only their regions will be drawn. You can still see where the sites are though if you draw contour lines with the -i option; see below for several examples.
Admittedly, Vorosketch is quite slow when drawing hyperbolic Voronoi diagrams. This is because effective filters for the pre-scan phase have not been implemented yet.
Available projections
To specify the projection, use -m “hyperbolic(projection)”, where projection is one of the following.
| projection | drawing area | examples | notes |
|---|---|---|---|
| Klein | unit disk | 50 sites | preserves lines (shortest connections) |
| Poincaré disk | unit disk | 50 sites | preserves circles and angles; lines are projected onto lines through the centre and circular arcs orthogonal to the boundary |
| Poincaré halfplane | halfplane y > −1 | 50 sites, 79 sites | preserves circles and angles; lines are projected onto vertical lines and circular arcs orthogonal to the boundary; Vorosketch puts the edge of the halfplane at y = −1 (instead of the usual y = 0), so that the origin is a fixed point among all projections |
| Gans | full plane | 50 sites | |
| equidistant | full plane | 79 sites | a modified Gans projection that preserves distances from the origin |
| equal-area | full plane | 79 sites | a modified Gans projection that preserves area |
Internally, Vorosketch uses the Gans projection, calculating the distance between two points p and q as acosh(√( (||p||² + 1)·(||q||² + 1) ) − <p,q>). A point p = (px, py) by Cartesian coordinates in another projection is converted to the Gans projection as follows:
Klein to Gans: p → p / √(1−||p||²);
Poincaré disk to Gans: p → p · 2 / (1−||p||²);
Poincaré halfplane to Gans: p → (p'x, ½·(||p'||² − 1) ) / p'y, where p' = p + (0,1);
Equidistant to Gans: p → p · sinh(||p||) / ||p||;
Equal-area to Gans: p → p · √(¼·||p||² + 1).
Speeding up
The most expensive step of the computation is the application of the acosh function to get the distance from the hyperbolic cosine of the distance. If contour lines at regular distance intervals are not needed, this step can be skipped: just use -m “cosh hyperbolic(projection)”. Subtracting a number slightly larger than 1 from this distance, as in -m “cosh hyperbolic(projection)-1.01”, creates a disk of negative distance around each site, which is rendered shaded.
Pre-defined sets of sites
The sets of sites available with the -# option are the following:
| -# 25 | the origin, 6 sites uniformly spaced at distance 1 from the origin, and 18 sites uniformly spaced at distance 2 from the origin |
| -# 50 | corners of a tiling with 63 regular triangles, corresponding to the centres of 50 tiles of a tiling with regular heptagons, centred on the origin |
| -# 79 | the 25 points' set extended with 54 sites uniformly spaced at distance 3 from the origin |
Examples
In most examples below, -0.20 has been added to the distance measure, so that a shaded disk of negative distance around each site is generated.
Klein disk projection, 50 sites
Note that the 15 regions that are not on the boundary all have the same shape and size.
vorosketch -m "hyperbolic(klein)-0.2" -p trubetskoy-modified -hbi 0.1 -w 1.2 -\# 50
[From version 0.36] Note that the same figure, without distance contours, can be created much faster by:
vorosketch -m "cosh hyperbolic(klein)-1.02" -p trubetskoy-modified -hb -w 1.2 -\# 50
Poincaré disk projection, 50 sites
vorosketch -m "hyperbolic(poincare disk)-0.2" -p trubetskoy-modified -hbi 0.1 -w 1.2 -\# 50
Poincaré halfplane projection, 50 sites
vorosketch -m "hyperbolic(poincare halfplane)" -cbhg 0.5 -i 0.1 -w 6 -\# 50
Poincaré halfplane projection, 79 sites
vorosketch -m "hyperbolic(poincare halfplane)-0.2" -p bright -hbi 0.1 -w 5 -\# 79
Gans projection, 50 sites
vorosketch -m "hyperbolic(gans)-0.2" -p brightstone -hbi 0.1 -w 12 -\# 50
Equal-area projection, 79 sites
vorosketch -m "hyperbolic(equal-area)-0.2" -i 0.1 -w 5 -\# 79
Equidistant projection, 79 sites
vorosketch -m "hyperbolic(equidistant)-0.2" -i 0.1 -w 3.5 -\# 79
Page Tools
