# Herman Haverkort

### Site Tools

fundamental_types_of_voronoi_diagrams_with_vorosketch

# Fundamental types of Voronoi diagrams with Vorosketch

Vorosketch supports the rendering of various types of Voronoi diagrams.

### Input format

The sites whose Voronoi diagram is to be generated are given on the standard input. A Vorosketch input file with simple point sites starts with the number of sites, and then specifies each site by four numbers, separated by spaces:

1 x y w

The first number specifies the number of points that defines the site, which is 1 for simple point sites. The next two numbers specify the location of the site in Cartesian coordinates. The last number is the weight of the site, and can simply be set to zero for an unweighted Voronoi diagram.

Here is an example input file, which we will take as input for the examples on this page:

```7
1 -0.75 -0.15 0
1 -0.70 -0.70 0
1 -0.45 -0.70 0
1  0    -0.60 0
1  0.65 -0.15 0
1  0.30  0.15 0
1 -0.55  0.45 0```

### Types of Voronoi diagrams

By default, a first-order subtractively weighted Voronoi diagram is constructed based on the Euclidean distance between points and sites in the plane. The result is an image in bmp-format that is produced on the standard output. Additively weighted diagrams can be constructed by negating each site's weight in the input. For an unweighted Voronoi diagram, one should set the weights in the input file to zero. Other types of Voronoi diagrams can be selected with the following command line options.

option  effect
-m zzz measure: use distance measure zzz. See below for details.
-d divisively weighted: create a divisively weighted Voronoi diagram: divide the distance between a point and a site by the site's weight, instead of subtracting the weight from the distance. Multiplicatively weighted diagrams can be constructed by replacing each site's weight by its inverse in the input.
-e x equality: set distance equality threshold to x times the width of a pixel (default: 0); a point is considered to be equidistant to two sites if the distance to one site differs by at most x pixel widths from the distance to the other site. This option is needed for diagrams based on distance measures such as L1, which may feature larger areas that are equidistant to two sites and which might not be recognised as such due to rounding errors if the -e option is not used.
-2 second-order: render the second-order Voronoi diagram, that is, the subdivision into regions such that within a region, each point has the same pair of sites as its closest pair of sites. Warning: Vorosketch has no mechanism to break ties between the second- and third-closest site in a predictable manner. The -e option cannot be used with second-order Voronoi diagrams.
-n next-closest: render the next-closest-site diagram, that is, the subdivision into regions such that within a region, each point has the same site as its second-closest site. Warning: Vorosketch has no mechanism to break ties between the first-, second- and third-closest site in a predictable manner. The -e option cannot be used with next-closest-site diagrams.
-f farthest: render farthest-site Voronoi diagram
-@ n roll a die: use n random unweighted sites instead of reading sites from standard input. This is meant to facilitate quick testing, without any guarantees for consistent behaviour across successive versions of Vorosketch. For most distance measures, the generated sites will be points uniformly distributed in the square [−1,1]×[−1,1]. For distance measures that support other types of sites, appropriate sites might be generated according to an appropriate distribution. When using the Manhattan (L1) or Euclidean (L2) metric, denoting them by Manhattan or Euclidean may cause the -@ option to generate segment sites, whereas denoting the distance measure by L1 or L2 results in single-point sites.

Also useful:

option  effect
-v verbose mode: gives a report on the options selected and shows progress bars on the computations

### Distance measures

With the -m option, the distance measure that defines the distance between a site s and any point q in the plane can be selected. The following distance measures are available:

 name alias properties Lp the Lp distance defined by (dxp + dyp)1 / p, where dx and dy are the absolute difference in x- and y-coordinate between s and q. The parameter p can be any real number. There are several special/limit cases: L-inf min the distance is min(dx, dy) Lp with p < 0 the distance is 0 when dx = 0 or dy = 0, otherwise it is simply (dxp + dyp)1 / p L0 bbox the distance is dx · dy (as proposed and analysed here) L1 Manhattan the distance is dx + dy L2 Euclidean the distance is the Euclidean distance Linf max the distance is max(dx, dy) squared the square of the Euclidean distance (this produces a power diagram) triangular the L1 distance between s and q if both are represented by three coordinates corresponding to their orthogonal projections on three axes through the origin at 60 degrees' angles. The unit circle under this distance measure is a regular hexagon with side length 1. karlsruhe distance between s and q if travelling only on lines through the origin and on circle centred on the origin, as discussed by Klein koeln like karlsruhe, if any distance travelled is divided by the current distance to the centre (as if modelling congestion in the centre). This is equivalent to the L1 distance in a polar coordinate system with an azimuth scale that wraps around from 0 to 2π and a logarithmic radius scale. The centre itself lies at −∞ on this scale, and is unreachable. If the sites are not weighted, the resulting bisectors consist of straight line segments in the logarithmic polar coordinate system; these are Thus, in the original coordinate system (that is, what you see), the bisectors consist of segments of straight lines through the origin and of circles and logarithmic spirals around the origin. city like koeln, but without the restriction to travel on lines through and circles around the origin. This is equivalent to the L2 distance in the polar coordinate system with logarithmic radius scale.

For distance measures for diagrams with highways, for sites on the sphere, for sites in the hyperbolic plane, for sites that have an orientation, for sites with orientation and speed/magnitude, and for sites that are larger than a point, please consult the dedicated linked pages.

New distance measures can be composed from existing distance measures by arithmetic operations. For example:

 -m “Linf + 0.707107*L1” sum of the L∞ distance and 0.707107 times the L1 distance output -m “Linf & 0.707107*L1” minimum of the L∞ distance and 0.707107 times the L1 distance output -m “Linf | 0.707107*L1” maximum of the L∞ distance and 0.707107 times the L1 distance output -m “Linf < 0.707107*L1 ? L2” L2-distance if the L∞ distance is less than 0.707107 times the L1 distance; infinite otherwise output

Besides the usual (multiplication, division, addition, subtraction, parentheses) and the minimum, maximum, comparison and conditional operators used above, the following operators and functions are supported:

 x~y absolute value of x−y x^y xy ln(x) natural logarithm of x sq(x) x² sqrt(x) √x abs(x) absolute value of x sx x-coordinate of the site sy y-coordinate of the site sr Euclidean distance from the origin to the site fx x-coordinate of the point whose distance to the site is to be determined fy y-coordinate of the point whose distance to the site is to be determined fr Euclidean distance from the origin to the point whose distance to the site is to be determined dt angle soq in radians, where s is the site, o is the origin, and q is the point whose distance to the site is to be determined @Lp like Lp, but measuring the distance to the origin, independent of the site @triangular like triangular, but measuring the distance to the origin, independent of the site translated(d) apply distance measure d after translating the coordinate system such that the site lies in the origin (that is, after subtracting s from q). The measure d should not depend on the site. Admissible measures are, for example, fx, fy, fr, @Lp and @triangular

Note: currently only negation of constants is supported. So -L2 will not work, but 0-L2 and -1*L2 are fine.

Warning: new distance formulas can give unexpected results if the sites are larger than single points: for example, segments, polylines, or finite sets of points. See the page on diagrams of sites larger than a point for an explanation.

### Examples

Below are the Voronoi diagrams generated with the four combined distance functions listed above. The options -bci 0.1 -r 1200 specify the use of black bisectors, coloured regions, distance contour lines at 0.1 intervals, and an image size of 1200×1200 pixels. Further options to control the style and colours of Vorosketch's output are discussed on a separate page.

#### A sum of distances:

`vorosketch -m "Linf + 0.707107*L1" -e 0.01 -bci 0.1 -r 1200`

#### A minimum of distances:

`vorosketch -m "Linf & 0.707107*L1" -e 0.01 -bci 0.1 -r 1200`

#### A maximum of distances:

`vorosketch -m "Linf | 0.707107*L1" -e 0.01 -bci 0.1 -r 1200`

#### A conditional distance:

`vorosketch -m "Linf < 0.707107*L1 ? L2" -e 0.01 -bci 0.1 -r 1200`

Possibly more useful applications of conditional distances can be found on the page on Voronoi diagrams of points with an orientation.