vorosketch

Vorosketch is a simple tool to sketch small Voronoi diagrams as a bitmap. Use it wisely. It is not designed for speed or for accuracy: it may miss features of the diagram that are narrower than a pixel. For standard Euclidean Voronoi diagrams of larger numbers of points in the plane, AGB-DTVD is a thousand times faster and more precise. But Vorosketch is easy to adapt to different distance measures regardless of whether we understand the geometry of the bisectors yet. Vorosketch draws:

- additively/substractively or multiplicatively/divisively weighted
- first-order, second-order and farthest-site Voronoi diagrams under the
*Euclidean*(L2),*squared Euclidean*(power diagrams),*Manhattan*(L1) metrics for point sites or polyline sites,*Lp*(for any finite non-zero p),*Euclidean highway*(with faster travel on specified line segments),*Karlsruhe*,*city*,*Koeln*,*orbit-in*, and*orbit-out*distance measures for point sites,*angular-size*,*detour*, and*dilation*measures for polyline sites,*turn*,*left-turn*, and*Dubins path length*measures for half-line sites,- and weighted combinations of these distance measures,

- with or without distance contour lines (lines of equidistant points)
- in black and white or with colour-coded sites and regions.

Below you can find the source code, examples of input and output, some technical background on the different types of diagrams, and some answers to possibly-asked questions.

Vorosketch is written in C++, here is the source-code. The current version is 0.13 beta. 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.

Here are some examples of what Vorosketch can do.

A standard Voronoi diagram of points in the Euclidean plane.

`vorosketch <sites >image.bmp`

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

`vorosketch <sites >image.bmp`

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`

With the -i and -g options one can add contour lines and shading:

Euclidean distance with multiplicative weights.

`vorosketch -d <sites >image.bmp`

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`

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`

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`

For a vehicle, rotating can be an issue too. Here is a Voronoi diagram of 18 cars, where 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:

Or 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`

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 -b -c <sites >image.bmp`

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`

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`

If your distance measure is the total energy of the two launches needed for a round trip, use Vorosketch's ability to add up multiple distance measures:

`vorosketch -m orbitin+orbitout -b -c <sites >image.bmp`

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`

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`

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):

`vorosketch -m 0.9*azimuth+logradius -b -c -e 0.01 <sites >image.bmp`

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.1:

`vorosketch -m highway -b -c -e 0.01 -i 0.1 <sites >image.bmp`

Finally, a second-order Voronoi diagram:

`vorosketch -2 -b -c <sites >image.bmp`

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. 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 case of Euclidean distance is well-known. Contour lines of point sites are concentric circles. Bisectors of point sites are straight lines and/or hyperboles (in the additively/subtractively weighted case) or Apollonian circles (in the multiplicatively/divisively weighted case). With unweighted line segment sites, contour lines consist of concentric circular arcs and straight line segments that advance at unit speed. Bisectors that are traced out by advancing circular arcs meeting advancing straight line segments take the form of parabolic curves.

With this distance measure, a contour line is the locus of points from which a site looks equally large in the field of view. If the sites are line segments, then, by the inscribed-angle theorem, the contour lines are (non-concentric) circles with the segment endpoints on the boundary. The bisectors are interesting curves with inflection points, whose properties I have not investigated yet.

With the detour and dilation metrics, the “distance” between a point *X* and a line segment *AB* is defined as |*AX*|+|*XB*|-|*AB*|; in the case of dilation, this number is subsequently divided by |*AB*|. Thus, a contour line (locus of points equidistant to *AB*) consists of the points *X* with constant sum |*AX*|+|*XB*|, which constitutes an ellipse. I have not thought about what shapes the bisectors have yet; any thoughts welcome!.

The speed of an object at position *X* in an elliptic orbit around the origin *O* is proportional to √(1/|*OX*| - 1/(2*a*)), where *a* is the length of the semi-major axis of the ellipse, and therefore the kinetic energy is proportional to 1/|*OX*| - 1/(2*a*). If we want to launch a space ship from *X* such that it will reach *Y*, we have to give it a direction and a kinetic energy that puts it into an orbit that reaches *Y*. Since this energy increases with *a*, we are looking for the orbit that includes *X* and *Y*, has *O* as one of its focal points, and has the smallest possible semi-major axis (non-elliptical, that is, open-ended orbits do not need to be considered: they would require more energy in any case). Note that, in an ellipse, *a* is exactly 1/4 of the length of the path *OXFYO*, where *F* is the second focal point. Therefore, to minimise *a*, we minimise the length of *OXFYO*, which we achieve by putting *F* on the line segment *XY*. Thus, the required energy is proportional to 1/|*OX*| + 2/(|*OX*|+|*XY*|+|*YO*|), which is straightforward to compute.

When *X* is given (as an input site), then the first term is fixed, and a contour line (locus of points at equal distance) consists of points *Y* with constant |*XY*|+|*YO*|: that is an ellipse with focal points *X* and *O*. When *Y* is the input site, the situation seems to be more complicated. I have not given the shape of the resulting bisectors any thought yet; I would appreciate any thoughts.

These metrics are simply the Euclidean and the Manhattan metrics after the coordinates have been converted to a polar coordinate system with a logarithmic radius axis, and where the azimuth axis wraps around from 2π to 0. If the sites are not weighted, the resulting bisectors consist of straight line segments in the logarithmic polar coordinate system. 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.

With the *turn* distance, the distance between a point *P* and a ray from *A* through *B* is the angle between *AP* and *AB*. If the rays are not weighted, then the bisectors consist of straight line segments, circular arcs (see Alegría et al.) and hyperbolic segments (see Haverkort and Klein).

With unweighted point sites in the highway distance, finding the shortest path between points becomes part of the challenge. Each segment of such a shortest path has two endpoints. Some of these endpoints are inherent to the input configuration (point sites, endpoints of highway segments, and intersection points of highway segments), the others (where one enters or leaves a highway at an arbitrary point) we may call *free*. Two observations help us limit the complexity of finding shortest paths.

First, when we enter or leave a highway with speed *s*>1 at a free point, we always enter or leave it under an angle with cosine equal to 1 divided by *s*. (Here, the speed of travelling cross-country is taken to be 1.) If we would enter the highway at a bigger angle, we would be making too much of a detour; if we would enter the highway at a smaller angle, we would not be taking advantage of the highway enough.

Second, to find shortest paths, we only need to consider segments with at most one free endpoint. To see this, consider any segment *c* with two free endpoints, that is, a segment that shortcuts from one highway segment *g* to another highway segment *h*. Let *b* on *g* be the previous segment of the shortest path. When we move the endpoints of *c* on their respective highway sections to the left or to the right, while maintaining the slope of *c* (following the first observation), the total path length changes linearly. Thus, in at least one direction, the total path length will not increase and we can move the endpoints of *c* until one of them, say the endpoint on *g*, hits either (i) a site, a highway endpoint or an intersection point *p*, or (ii) the free endpoint that started *b*. In case (i), the other endpoint of *c* must be the free endpoint where a ray from *p* hits *h* at the right angle. Given *p* and *h*, there are at most two such points, so we can actually precompute all such candidate free endpoints. In case (ii), *b* is now eliminated, and, because of the first observation, the previous segment of the shortest path must be collinear with *c*. Thus, we can treat the latter two segments as one shortest path segment and repeat our argument with two segments less than before. Eventually, we can transform any shortest path into a shortest path in which each segment has at least one non-free endpoint, and all free endpoints come from a finite set that can be computed easily.

These observations allow us to precompute much of the shortest paths that we need to generate the diagram. After that, all that is left to do is figuring out, for each pixel, what is the first input point or highway segment on that path. To do this efficiently, Vorosketch uses a heuristic solution: it first computes the eligible input points and highway segments for each cell in a 100×100 grid (using conservative bounds on the distances that can be computed fast); then, for each pixel in the cell, only shortest paths that go through these input points or highway segments need to be considered.

Contours of a point site are circular arcs and straight line segments advancing at unit speed, where the straight line segments originate from highway sections at an angle with sine equal to 1 divided by the highway speed. However, the circular arcs in a contour may have different radius, as they may grow from given points (for example, highway endpoints) that are at different distances to the starting point (site). Thus, bisectors can be straight line segments (as in unweighted Voronoi diagrams), hyperbolic arcs (as in additively weighted Voronoi diagrams) or parabolic arcs (as in line segment Voronoi diagrams).

**Mr. Haverkort, could you please add feature X?**

Just ask me and I will have a look.

**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 at the top of my to-do list now.

**Could diagram X not be computed faster?**

Certainly, and for most diagrams I have some clear ideas about how I would try to do this. However, since I have to budget the time I spent programming, I try to be selective in what computations I choose to optimise. So far, most diagrams that I wanted to produce were produced within seconds. Theoretically, speeding it up further only makes sense for types of diagrams of which thousands are going to be produced. If you are going to produce thousands of Voronoi diagrams that need to be rendered faster, please let me know and I might be tempted to speed up my efforts to speed it up.

vorosketch.txt · Last modified: 2022/04/05 08:52 by administrator