Site Tools


Voronoi diagrams of sites larger than a point with Vorosketch

Vorosketch supports, to some extent, Voronoi diagrams for sites that consist of a segment, a polyline, or of multiple points. If you want to define your own distance formulas and use sites that consist of more than a single point, you may need to understand how Vorosketch handles such sites.

Input format for segments or polylines

A polylinear site can be specified by giving the number of vertices; then, for each vertex, its x- and its y-coordinate, and finally the weight of the site (use 0 for unweighted sites). Here is an input file that specifies four polylinear sites:

4 -0.4 -0.1 -0.2 0.4 0.1 -0.1 -0.3 0 0
2 -0.7 -0.5 0.1 -0.8 0
5 -0.5 0.5 0.2 0.5 0.2 -0.2 -0.5 -0.2 -0.5 0.5 0
2 0.4 0.3 0.7 -0.5 0

Distance measures for segments or polylines

Vorosketch supports Voronoi diagrams for polylinear sites under three types of distance measures:

  • L1 or Manhattan, L2 or Euclidean, and squared Euclidean distance
  • angle or angular size distance
  • detour and dilation distance

Here is an example with the L1 distance. Note the use of -e 0.0001 to define some slack in the distance equality tests: without this option, some parts of the upper right corner of the diagram would incorrectly be rendered enirely blue, yellow or black.

vorosketch -m l1 -bce 0.0001 -i 0.05 -r 800

The angle (or: angular size) distance between a point p and a polylinear site is 2π divided by the size of the site in the field of view from p, minus 1. Sites are treated as transparent: they do not block lines of sight to other sites. Thus, if p is completely surrounded by a site, the distance to that site is 0; if p lies just next to the site's convex hull, the distance is 1. 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.

In the example below, the distance to the yellow square site is zero inside the square. Due to rounding errors, the calculated distance for some points inside the square may be negative, while for others it is not. With the standard options, the (arbitrary) points with negative distance would be shaded. The -o option that is used below suppresses that shading.

vorosketch -m angle -bcoe 0.0001 -i 0.2 -r 800

With the detour and dilation distance measures, the distance between a point p and a line segment ab is defined as ||a−p||+||p−b||−||a−b||; in the case of dilation, this number is subsequently divided by ||a−b||. Thus, a contour line (locus of points equidistant to the line segment under this measure) consists of the points p with the same value for the sum ||a−p||+||p−b||. Thus, contour lines are ellipses. For the distance of a point p to a polylinear site, we take the minimum distance over all segments of the polyline.

vorosketch -m detour -bc -i 0.1 -r 800

Sites and groups

Vorosketch distinguishes between basic sites and groups of sites. Vorosketch draws the Voronoi regions of the groups. For the most basic Voronoi diagrams, each group consists of exactly one point site, but for more advanced Voronoi diagrams, this does not need to be the case. When a group consists of more than one site, the distance to the group is the distance to the site that minimises the complete distance formula.

Example: if a group consists of the points (0,0) and (-0.3,0.6) and the distance measure is L1+L2, then the distance to the point (0.8,0.6) is not 2.1 (the L1 distance from the group, which is 1.1, plus the L2 distance from the group, which is 1.0), but the distance to (0.8,0.6) is 2.2 (the distance from the basic site that minimises the sum of the L1 and the L2 distance).

Groups of sites can be specified explicitly on the input. To do so, just define sites in the normal way (each site given by its number of defining points, the coordinates, and the weight), but write the number of defining points of a site as a negative number if it should be put into one group with the next site. The first line of the input should give the number of groups, not the number of sites.

For example, with this input:

-1  0    0.7 0
-1  0.8  0.6 0
 1  0.8 -0.3 0
-1 -0.6  0.8 0
-4  0    0.3  0.5  0.4  0.4 -0.2  0    0.3 0
 2 -0.8 -0.2  0.1 -0.8  0
 2 -0.6 -0.1 -0.2 -0.2  0
 1  0.3  0.2 0

we can call Vorosketch like this:

vorosketch -bc -r 800 

to obtain this diagram:

Note how Vorosketch interpreted the input as four groups, that each consist of a number of points and/or segments, and produced the Voronoi diagram for these groups under the default distance measure, that is, the Euclidean (L2) distance.

In contrast, the following line tricks Vorosketch in using the generic implementation for Lp distances, which does not support segment or polyline sites. Therefore sites of multiple points are now interpreted as groups of isolated points:

vorosketch -m L2.0 -bc -r 800 

Implicit groups

For efficiency reasons, Vorosketch implicitly handles segment sites and polylinear sites as groups. When a site that consists of multiple points is specified in the input, Vorosketch automatically interprets it as a group that consists of a chain of point sites and/or segment sites, depending on what the implementation of the distance measure supports. In combination with the above, this means that you should be careful if you want to use composite distance formulas for segment sites or polylinear sites. Here is what you might need to know.

When using the Euclidean or the squared Euclidean distance, any segment or polyline site is handled as a group of multiple sites: the vertices and the interiors of the segments. The distance between a point and a segment interior is only defined if the point lies in the open strip that consists of all lines that intersect the interior of the segment at a right angle. When using the Manhattan distance, the same mechanism is used, where the strips consist of horizontal or vertical lines, depending on the slopes of the segments.

The detour and dilation measures use segment sites. Combining these measures with any of the aforementioned distances results in undefined distances outside the aforementioned strips. The angle distance measure is defined for actual polyline sites; these are not handled as a group of segments. If, however, one combines this distance measure with any of the aforementioned measures, the polyline sites will be taken apart into groups of segment sites. These are features that I do not consider desirable, but chose to tolerate when optimising Vorosketch for more usual distance measures. If you have a use for combined distance functions that are made impossible by these mechanisms, please let me know and I will consider implementing a solution.

voronoi_diagrams_of_sites_larger_than_a_point_with_vorosketch.txt · Last modified: 2023/03/22 13:43 by administrator