Table of Contents

Vorosketch

Vorosketch is a simple tool that sketches small Voronoi diagrams as a bitmap in a few seconds. Vorosketch's raison d'être is that it is easy to adapt to different distance measures, regardless of whether we understand the geometry of the bisectors yet. Thus we can use Vorosketch for explorations and illustrations; it supports several novel distance measures. Vorosketch draws:

Use Vorosketch wisely; it is not designed for speed or for accuracy. Vorosketch may miss features of the diagram that are narrower than a pixel, and I made no attempt to analyse or control the error margins in the distance computations. For standard Euclidean Voronoi diagrams of large numbers of points in the plane, AGB-DTVD and many other implementations are orders of magnitude faster and more precise.

Below you can find Vorosketch's source code, examples of input and output, some technical background on the different types of diagrams, some answers to possibly-asked questions, and a list of what is new as compared to previous versions. There are separate pages on how to use Vorosketch for:

As a teaser, below is a travel-time Voronoi diagram of 150 points, where travel along highways is ten times as fast as across the plane. For more large figures, see the gallery.

Download

Vorosketch is written in C++, here is the source code. The current version is 0.37 beta of 22 March 2023. Vorosketch does not use any libraries apart from the standard template library, so it should be easy to compile with any C++ compiler. Please let me know if you have trouble compiling the code or if you find any bugs. Vorosketch is licensed under the Apache License, please see the source code for further details. To enable user-defined distances from userdistances.cpp (see the source code for an example), compile with the -D INCLUDE_USER_DISTANCES option.

Examples of input and output

Here are some examples of what Vorosketch can do. All examples were made with the “-r 1200” option to produce a drawing of 1200×1200 pixels in bmp-format. For convenience, we omit “-r 1200” from the command lines below. For publication on this webpage, the images were downsampled to 400×400 pixels and converted to png-format.

For a more complete list of options, please run Vorosketch with the -? option.

The basics

A standard Voronoi diagram of points in the Euclidean plane is produced by:
vorosketch <sites >image.bmp

input output
12
1 -0.321 0.108 0
1 -0.762 -0.150 0
1 0.342 -0.482 0
1 0.608 0.239 0
1 -0.195 0.053 0
1 -0.664 -0.703 0
1 -0.120 0.399 0
1 0.231 -0.769 0
1 0.314 0.267 0
1 0.166 0.371 0
1 -0.053 0.195 0
1 -0.160 0.686 0

Next: the same, with additive weights. The boundaries of the shaded areas are at equal weighted distance to their sites.
vorosketch <sites >image.bmp

input output
12
1 -0.321 0.108 0.241
1 -0.762 -0.150 0.011
1 0.342 -0.482 0.005
1 0.608 0.239 0.085
1 -0.195 0.053 0.008
1 -0.664 -0.703 0.000
1 -0.120 0.399 0.060
1 0.231 -0.769 0.104
1 0.314 0.267 0.013
1 0.166 0.371 0.166
1 -0.053 0.195 0.000
1 -0.160 0.686 0.085

Next: a power diagram (that is, using squared distances with additive weights). And why not add some colour, too, using Sasha Trubetskoy's beautiful colour scheme:
vorosketch -m squared -c <sites >image.bmp

input output
12
1 -0.321 0.108 0.241
1 -0.762 -0.150 0.011
1 0.342 -0.482 0.005
1 0.608 0.239 0.085
1 -0.195 0.053 0.008
1 -0.664 -0.703 0.000
1 -0.120 0.399 0.060
1 0.231 -0.769 0.104
1 0.314 0.267 0.013
1 0.166 0.371 0.166
1 -0.053 0.195 0.000
1 -0.160 0.686 0.085

With the -i and -g options one can add contour lines and shading:
vorosketch -i 0.05 -c -g 0.2 <sites >image.bmp

Euclidean distance with multiplicative weights:
vorosketch -d <sites >image.bmp

input output
12
1 -0.321 0.108 0.241
1 -0.762 -0.150 0.011
1 0.342 -0.482 0.005
1 0.608 0.239 0.085
1 -0.195 0.053 0.008
1 -0.664 -0.703 0.000
1 -0.120 0.399 0.060
1 0.231 -0.769 0.104
1 0.314 0.267 0.013
1 0.166 0.371 0.166
1 -0.053 0.195 0.000
1 -0.160 0.686 0.085

All you have seen so far, also works for polyline sites. Let us use colour (-c) and add the black region boundaries nonetheless (-b). As you can see, there are areas that are at equal distance from two sites:
vorosketch -b -c <sites >image.bmp

input output
5
2 0.231 -0.769 0.342 -0.482 0
2 -0.664 -0.703 -0.762 -0.150 0
4 -0.762 -0.150 -0.321 0.108 -0.195 0.053 -0.053 0.195 0
3 -0.053 0.195 -0.120 0.399 -0.160 0.686 0
4 -0.120 0.399 0.166 0.371 0.314 0.267 0.608 0.239 0

To cut the equal-distance areas in a sensible way, use the -s option to shorten the polylines slightly:
vorosketch -b -c -s 0.01 <sites >image.bmp

input output
5
2 0.231 -0.769 0.342 -0.482 0
2 -0.664 -0.703 -0.762 -0.150 0
4 -0.762 -0.150 -0.321 0.108 -0.195 0.053 -0.053 0.195 0
3 -0.053 0.195 -0.120 0.399 -0.160 0.686 0
4 -0.120 0.399 0.166 0.371 0.314 0.267 0.608 0.239 0

Points with directions (rays)

In the diagram below each site moves at constant speed in the direction indicated by the black “arm” that originates from its coloured dot. We define the distance from a point q to a site p as the distance one has to travel from q (at the same constant speed) to meet (catch) the moving site p. This leads to the following Voronoi diagram of moving points:
vorosketch -m catch -i 0.025 -c -g 1.25 <sites >image.bmp

input output
11
2 0.378 -0.006 0.279 -0.022 0
2 -0.234 -0.110 -0.274 -0.201 0
2 -0.412 -0.623 -0.313 -0.606 0
2 0.725 0.404 0.768 0.314 0
2 -0.127 0.365 -0.042 0.312 0
2 0.364 -0.319 0.264 -0.316 0
2 0.582 0.716 0.521 0.796 0
2 0.036 0.365 0.070 0.459 0
2 -0.421 0.008 -0.321 0.002 0
2 0.677 0.740 0.645 0.645 0
2 0.230 0.054 0.158 -0.015 0

We can also make a Voronoi diagram of points that move at different speeds, while the catcher moves at a fixed speed. For example:

Another interpretation of the same diagram is that a point q belongs to the site p that can reach q fastest, when the site's original speed and direction are subjected to an instantaneous directed acceleration of a fixed magnitude.

Now let the sites represent disks, oriented perpendicular to the drawing plane and perpendicular to the black arms drawn in the diagram. A disk at a point p emits light on the side of the black arm (whose end point we denote by p') but not on the other side. Naturally, the light received by a point q in the plane is now inversely proportional with the secant of the angle qpp' and with the squared distance to p. We want to produce a diagram that shows, for each point in the plane, from which disk it receives most light. For this purpose, we use Vorosketch's ability to multiply distance measures:
vorosketch -m squared*secant -i 0.05 -c -g 1 -b <sites >image.bmp

input output
11
2 0.378 -0.006 0.279 -0.022 0
2 -0.234 -0.110 -0.274 -0.201 0
2 -0.412 -0.623 -0.313 -0.606 0
2 0.725 0.404 0.768 0.314 0
2 -0.127 0.365 -0.042 0.312 0
2 0.364 -0.319 0.264 -0.316 0
2 0.582 0.716 0.521 0.796 0
2 0.036 0.365 0.070 0.459 0
2 -0.421 0.008 -0.321 0.002 0
2 0.677 0.740 0.645 0.645 0
2 0.230 0.054 0.158 -0.015 0

Now suppose the sites are oriented line segments, and the distance to a point p is how much we would have to rotate the segment around its starting point in order to point towards p:
vorosketch -m turn -b -c <sites >image.bmp

input output
11
2 0.378 -0.006 0.279 -0.022 0
2 -0.234 -0.110 -0.274 -0.201 0
2 -0.412 -0.623 -0.313 -0.606 0
2 0.725 0.404 0.768 0.314 0
2 -0.127 0.365 -0.042 0.312 0
2 0.364 -0.319 0.264 -0.316 0
2 0.582 0.716 0.521 0.796 0
2 0.036 0.365 0.070 0.459 0
2 -0.421 0.008 -0.321 0.002 0
2 0.677 0.740 0.645 0.645 0
2 0.230 0.054 0.158 -0.015 0

For a vehicle, rotating can be an issue too. Here is a Voronoi diagram of 18 cars, each visualised as a rooted vector. The origin of the vector (marked by a coloured dot) marks the current location of the car, and the length indicates its minimum turning radius. The distance from a car to a point is defined as the length of the shortest route that the car can take to that point while only driving forward and subject to its minimum turning radius:
vorosketch -m dubins -i 0.04 -b -c <sites >image.bmp

In semi-Voronoi diagrams, distances are as usual, except that the distance between a point and a rooted-vector site is infinite if the point is not in front of it, that is, if the site would have to rotate more than 90 degrees to be directed at the point. Semi-Voronoi diagrams can be produced by multiplying the usual distance measure with the special “semi” distance, for example: vorosketch -m semi*euclidean -b -c <sites >image.bmp

Special distance measures for line segments

Some of the distance measures for point sites also work for segment or polyline sites. In addition, Vorosketch implements some distance measures that are defined specifically for segment and polyline sites. For exampe, suppose we say the closest object to p is the one that has the largest angular size as seen from p:
vorosketch -m angle -b -c <sites >image.bmp

input output
10
2 0.231 -0.769 0.342 -0.482 0
2 -0.664 -0.703 -0.762 -0.150 0
2 -0.762 -0.150 -0.321 0.108 0
2 -0.321 0.108 -0.195 0.053 0
2 -0.195 0.053 -0.053 0.195 0
2 -0.053 0.195 -0.120 0.399 0
2 -0.120 0.399 -0.160 0.686 0
2 -0.120 0.399 0.166 0.371 0
2 0.166 0.371 0.314 0.267 0
2 0.314 0.267 0.608 0.239 0

Or the closest line segment qr to p is the one that minimises the detour if we would want to visit p on the way from q to r, that is, it minimises |qp| + |pr| - |qr|:
vorosketch -m detour -i 0.1 -b -c <sites >image.bmp

input output
10
2 0.231 -0.769 0.342 -0.482 0
2 -0.664 -0.703 -0.762 -0.150 0
2 -0.762 -0.150 -0.321 0.108 0
2 -0.321 0.108 -0.195 0.053 0
2 -0.195 0.053 -0.053 0.195 0
2 -0.053 0.195 -0.120 0.399 0
2 -0.120 0.399 -0.160 0.686 0
2 -0.120 0.399 0.166 0.371 0
2 0.166 0.371 0.314 0.267 0
2 0.314 0.267 0.608 0.239 0

Lp distances

Under the Manhattan (L1) metric, the distance between two points is determined by the shortest path that consists only of vertical and horizontal segments. To make sure that regions that are equidistant to two sites are recognisable as such, use the -e option to catch rounding errors:
vorosketch -m manhattan -e 0.01 -b -c <sites >image.bmp

input output
12
1 -0.321 0.108 0
1 -0.762 -0.150 0
1 0.342 -0.482 0
1 0.608 0.239 0
1 -0.195 0.053 0
1 -0.664 -0.703 0
1 -0.120 0.399 0
1 0.231 -0.769 0
1 0.314 0.267 0
1 0.166 0.371 0
1 -0.053 0.195 0
1 -0.160 0.686 0

In fact, we can calculate Voronoi diagrams for any geometric Lp distance measure, even for p < 1, for example the minimum measure L−∞, the product measure L0, or L0.5:
vorosketch -m L-inf -b -c <sites >image.bmp

input output
12
1 -0.321 0.108 0
1 -0.762 -0.150 0
1 0.342 -0.482 0
1 0.608 0.239 0
1 -0.195 0.053 0
1 -0.664 -0.703 0
1 -0.120 0.399 0
1 0.231 -0.769 0
1 0.314 0.267 0
1 0.166 0.371 0
1 -0.053 0.195 0
1 -0.160 0.686 0

vorosketch -m L0 -b -c <sites >image.bmp

input output
12
1 -0.321 0.108 0
1 -0.762 -0.150 0
1 0.342 -0.482 0
1 0.608 0.239 0
1 -0.195 0.053 0
1 -0.664 -0.703 0
1 -0.120 0.399 0
1 0.231 -0.769 0
1 0.314 0.267 0
1 0.166 0.371 0
1 -0.053 0.195 0
1 -0.160 0.686 0

vorosketch -m L0.5 -b -c <sites >image.bmp

input output
12
1 -0.321 0.108 0
1 -0.762 -0.150 0
1 0.342 -0.482 0
1 0.608 0.239 0
1 -0.195 0.053 0
1 -0.664 -0.703 0
1 -0.120 0.399 0
1 0.231 -0.769 0
1 0.314 0.267 0
1 0.166 0.371 0
1 -0.053 0.195 0
1 -0.160 0.686 0

Distances in which the centre is special

Under the Karlsruhe metric, distances are determined by paths that consist only of radial segments (to/from the centre of the map) and circular arcs (with the circle centre in the centre of the map):
vorosketch -m karlsruhe -e 0.01 -b -c -+ <sites >image.bmp

input output
12
1 -0.321 0.108 0
1 -0.762 -0.150 0
1 0.342 -0.482 0
1 0.608 0.239 0
1 -0.195 0.053 0
1 -0.664 -0.703 0
1 -0.120 0.399 0
1 0.231 -0.769 0
1 0.314 0.267 0
1 0.166 0.371 0
1 -0.053 0.195 0
1 -0.160 0.686 0

In a real city, say, Köln, you would also have to take account that travelling in the city centre is slow. Suppose we can travel only on radial segments and circular arcs, with a speed that is linearly proportional to the distance from the centre, slightly faster on the circular arcs than on the radial axes (in effect, this turns distances into L1-distances in polar coordinate space with a logarithmic radius axis, with the actual centre point becoming unreachable). We use Vorosketch's ability to add up multiple distance measures:
vorosketch -m 0.9*azimuth+logradius -b -c -e 0.01 <sites >image.bmp

input output
12
1 -0.321 0.108 0
1 -0.762 -0.150 0
1 0.342 -0.482 0
1 0.608 0.239 0
1 -0.195 0.053 0
1 -0.664 -0.703 0
1 -0.120 0.399 0
1 0.231 -0.769 0
1 0.314 0.267 0
1 0.166 0.371 0
1 -0.053 0.195 0
1 -0.160 0.686 0

Now suppose the closest site to p is the one that would require least energy to launch a space ship that reaches p from that site, subject to gravitation towards the centre:
vorosketch -m orbitout -b -c -+ <sites >image.bmp

input output
12
1 -0.321 0.108 0
1 -0.762 -0.150 0
1 0.342 -0.482 0
1 0.608 0.239 0
1 -0.195 0.053 0
1 -0.664 -0.703 0
1 -0.120 0.399 0
1 0.231 -0.769 0
1 0.314 0.267 0
1 0.166 0.371 0
1 -0.053 0.195 0
1 -0.160 0.686 0

The closest site to p is the one that would require least energy to launch a space ship that reaches the site from p:
vorosketch -m orbitin -b -c -+ <sites >image.bmp

input output
12
1 -0.321 0.108 0
1 -0.762 -0.150 0
1 0.342 -0.482 0
1 0.608 0.239 0
1 -0.195 0.053 0
1 -0.664 -0.703 0
1 -0.120 0.399 0
1 0.231 -0.769 0
1 0.314 0.267 0
1 0.166 0.371 0
1 -0.053 0.195 0
1 -0.160 0.686 0

Travel time diagrams using highways

Very different yet is the diagram that results, if one can travel in all directions, but travel on highways is faster than cross-country. For this diagram, the -i option is used to show contour lines at intervals of 0.05:
vorosketch -m highway -b -c -e 0.01 -i 0.05 -g 0.5 <sites >image.bmp

input output
12
1 -0.321 0.108 0
1 -0.762 -0.150 0
1 0.342 -0.482 0
1 0.608 0.239 0
1 -0.195 0.053 0
1 -0.664 -0.703 0
1 -0.120 0.399 0
1 0.231 -0.769 0
1 0.314 0.267 0
1 0.166 0.371 0
1 -0.053 0.195 0
1 -0.160 0.686 0
5
2 -1 -0.6 1 -0.2 3
3 -0.6 -0.52 -0.35 -0.14 0.1 -0.38 3
4 -0.35 -0.14 -0.3 0.2 -0.2 0.3 1 0.8 3
3 -0.02 0.02 -0.3 0.3 -0.7 1 3
3 0.235 -0.09 0.16 -0.29 0.2 -1 3

Second-order Voronoi diagrams

Finally, a second-order Voronoi diagram:
vorosketch -2 -b -c <sites >image.bmp

input output
12
1 -0.321 0.108 0
1 -0.762 -0.150 0
1 0.342 -0.482 0
1 0.608 0.239 0
1 -0.195 0.053 0
1 -0.664 -0.703 0
1 -0.120 0.399 0
1 0.231 -0.769 0
1 0.314 0.267 0
1 0.166 0.371 0
1 -0.053 0.195 0
1 -0.160 0.686 0

Documentation

There are separate pages on how to use Vorosketch for:

Technical background

In principle, Vorosketch simply computes, for each pixel, the distance to each site. Of course that is not a particularly efficient way to compute the diagrams, but it works for any type of diagram, and for small diagrams to be used as illustrations, it is fast enough. In fact, Vorosketch speeds up many computations by applying a filter that allows it to rule out a site as a closest site for a whole block of pixels at once.

If there are multiple closest sites, Vorosketch records two of them (if there are more than two, Vorosketches takes the first two by order in the input file). The reason that only the two closest sites are considered, is that so far, that was enough for my purposes. To handle situations in which there are more than two closest sites, we would first have to decide how we would want that to be visualised. I am open to suggestions if there is a need for it.

The pages listed above under documentation contain some more details on the computation of the distance measures discussed on those pages.

Possibly-Asked Questions

The output seems wrong. Why?
Sometimes I find bugs and fix them, or I adapt the user interface to catch problematic combinations of parameter settings. If you discover a bug, please check if you are using the newest version of Vorosketch. If you compiled with the -ffast-math option, then try without: Vorosketch relies on correct handling of ∞, −∞ and not-a-number. If the bug is still there, please let me know.

Why does shading by distance gradient (the -z option) does not work?
It should work. However, the distances are not scaled automatically. Depending on the input, some distance measures tend to produce rather small values for points in the [−1,1]x[−1,1] square, so that the distance gradients are small and the distance landscape appears flat. In particular, the squared Euclidean, secant, and catch distances may have this problem (whereas the turn and leftturn distances tend to have too much variation, producing steep gradients). To remedy this, scale the distances. For example, use “-m squared*5” instead of “-m squared”.

Could diagram X not be computed faster?
Certainly. The computation of the catch and push Voronoi diagrams (with sites moving at different speeds), Dubins Voronoi Diagrams and hyperbolic Voronoi diagrams is particularly slow, because good bounds for the pre-scan heuristic have not been implemented (you can check this by running with -v and see what it says about “Distance computations eliminated by filter”). Since I have to budget the time I spent programming, I try to be selective in what computations I choose to optimise. If you are going to produce thousands of Voronoi diagrams of some particular distance measure that need to be rendered faster, please let me know and I might be tempted to speed up my efforts to speed it up. Until then, you may want to know about the following options:

Why do I get an error: “Distance function is not compatible with or has not been implemented for any type of site”?
This happens if one combines distances whose domains (types of sites for which they are defined and implemented) are incompatible. For example, using “-m karlsruhe+dilation” results in this error, as the Karlsruhe distance has only been implemented for point sites, whereas the dilation distance is only defined for segment and polyline sites.

Why do I get an error: “missing distance name”?
This happens if, in the argument of the -m option, a distance name or formula is missing where one is expected. For example, using “-m euclidean+” results in this error, because the second operand of the + operator is missing.

Why do I get an error: “negative weight detected in input”?
If you use divisive (multiplicative) weighting (the -d option), weights are not allowed to be negative. The reason is that lower bounds on distances would become upper bounds and vice versa: the implementation would need to handle this and currently it does not. Please let me know if you had a use for negative divisive (multiplicative) weights.

Why do I get an error: “negative value -1.0842e-19 for upper bound on first operand to power operator detected” (or a similar message)?
The power operator does not accept negative values for the first operand (for taking squares, use the sq function instead). If you suspect that the negative value is the result of a rounding error, use the maximum operator | to round negative values up to 0, for example: -m “(ln(karlsruhe/euclidean)|0)^1.5”

Why do I get an error: “too many sites”?
Vorosketch is designed for relatively small inputs, it is not designed to scale well. The code sets a somewhat arbitrary maximum of 20,000 sites (less when using highway distance). Not very far above that, Vorosketch would crash because it uses a quadratic amount of memory (which is entirely avoidable, but would require some programming effort). With some inputs, distance measures and options, Vorosketch would be impossibly slow with far fewer sites already, due to the arithmetic operations involved.

Why is the output in this inefficient bmp-format?
Because I had C++ code for that lying around already and I did not get round to studying PNG yet. This is somewhere on my to-do list, but all the way at the bottom, to be honest.

Mr. Haverkort, could you please add feature X?
Just ask me and I will have a look.

What is new?

Some Voronoi diagrams, uncommented for now, maybe you recognise the distance measures?