Calculates a Voronoi tessellation or a Delaunay triangulation of the x-y plane, and plots these as graphs (D.B. Baird).
Options
PLOT = string tokens |
Type of plot to display (Voronoi, Delaunay, combined); default Voro |
RANGE = scalar or variate |
Range to use in the plots, either a scalar giving the percentage of the data range to use as a margin around the points, or a variate of length four giving the minimum x and y values and maximum x and y values; default 5 |
WINDOW = scalars |
Window numbers for the graphs; default 3 |
SCREEN = string tokens |
Whether to clear the screens before plotting or to continue plotting on the old screen (clear, keep); default clea |
Parameters
Y = variates |
Y coordinates for the points |
X = variates |
X coordinates for the points |
Z = variates |
Z coordinates for the points to be plotted as a colour for the tiles in a Voronoi plot |
TITLE = texts |
Titles for the plot; default uses an automatic title |
LABELS = variates or texts |
Labels to display beside the points in the plot |
COLOURS = variates or texts |
Colours to use for the tiles in a Voronoi plot when Z has been set; default !t('red','yellow','green') |
VLINES = pointers |
Pointer containing four variates, labelled ‘X1’, ‘Y1’, ‘X2’ and ‘Y2’, to store the points at the ends of the lines in a Voronoi plot |
DLINES = pointers |
Pointer containing four variates, labelled ‘X1’, ‘Y1’, ‘X2’ and ‘Y2’, to store the points at the ends of the lines in a Delaunay plot |
TRIANGLES = pointers |
Pointer containing six variates, labelled ‘X1’, ‘Y1’, ‘X2’, ‘Y2’, ‘X3’ and ‘Y3’, to store the vertices in the triangles in a Delaunay plot |
TILES = pointers |
Pointer containing a factor indexing the tiles and two variates containing the vertices of the tiles in a Voronoi plot, labelled ‘Tile’, ‘X’ and ‘Y’ |
Description
The TRIANGULATION procedure calculates the lines and tiles in a Voronoi tessellation or a Delaunay triangulation for a set of points in the x-y plane. A Delaunay triangulation connects the points in an optimal mesh. The mesh connects each point with its closest neighbours and maximises the minimum angles in the triangles connecting the points. A Voronoi tessellation divides the plane into a tile around each point, such that the tile contains the region of the plane closest to that point. The plots are related, as the bisectors of the sides of the triangles in the Delaunay plot form the edges of the tiles in the Voronoi tessellation. TRIANGULATION can then plot the points and lines that make up the mesh or tiles.
The Y and X parameters supply the y- and x-coordinates of the points to be triangulated. An optional Z parameter can be supplied to colour the tiles in a Voronoi tessellation in a similar manner to a contour plot.
The PLOT option specifies the types of plot to be displayed. By default a Voronoi plot is displayed. Alternatively, you can set PLOT=Delaunay to produce a Delaunay plot, or PLOT=combined to produce a plot combining both the triangulation and tessellation.
The RANGE option can set the lower and upper values for the x and y-axes in the plot. It can be set to a scalar, defining the percentage of the data range to be subtracted or added to the minimum or maximum data value, respectively, for both x and y-axes, Alternatively, it can be set to a variate of length four, specifying the minimum x and y values and the maximum x and y values, in that order. The specified range must contain all the data points.
The COLOURS option can be used to specify the colour of each tile. This can be a variate or text of the same length as X, to provide a distinct colour for each tile. Alternatively, if the variate or text has two or more values, these are used as parameters to the DCOLOURS procedure, to obtain a band of graduated colours which are then applied to the values in Z. The graphical settings (symbol, colour, thickness, size etc.) for the lines and points in the plots can be controlled using PEN 1 and 2 respectively. The LABELS can be coloured separately to the points by setting both the COLOUR and CSYMBOL options for PEN 2.
The WINDOW parameter defines the windows in which the graphs are drawn (default 3). The TITLE parameter can be used to provide a title for the graph. If there are multiple plots, TITLES can be a text containing two strings. These are applied to the graphs in the order in which they are produced. The SCREEN parameter controls whether the graphical display is cleared before the graph is plotted. Both WINDOW, and SCREEN can be lists if more than one plot has been selected.
The components of the graphs can be saved by using the VLINES, DLINES, TRIANGLES, TILES parameters. VLINES saves the ends of the lines in a Voronoi plot in a pointer containing four variates, labelled ‘X1’, ‘Y1’, ‘X2’, ‘Y2’. DLINES saves the ends of the lines in a Delaunay triangulation in a pointer containing four variates, labelled ‘X1’, ‘Y1’, ‘X2’, ‘Y2’. Each row in these four variates specifies the start and end position of the lines. TRIANGLES saves the vertices of the triangles that make up the mesh in a Delaunay triangulation in pointer containing six variates, labelled ‘X1’, ‘Y1’, ‘X2’, ‘Y2’, ‘X3’, ‘Y3’. Each row in these six variates specifies the three vertices of the triangles. TILES saves the vertices of the tiles that make up the tessellation in a Voronoi plot in pointer containing a factor and two variates, labelled ‘Tiles’, ‘X’, ‘Y’. The factor indexes the tiles around each point, and the variates contain the x and y values for vertices of the tiles.
Options: PLOT, RANGE, WINDOW, SCREEN.
Parameters: Y, X, Z, TITLE, LABELS, COLOURS, VLINES, DLINES, TRIANGLES, TILES.
Method
TRIANGULATION uses the C++ algorithm of Stephen Fortune which has been compiled into the DataLoad library.
Action with RESTRICT
You can arrange to plot only a subset of the points by restricting the Y or X parameters. If both are restricted, they must be restricted in the same way. Restrictions on the Z, COLOURS or LABELS parameters are ignored.
References
Fortune, S. (1986). A sweepline algorithm for Voronoi diagrams. Proceedings of the second annual symposium on Computational geometry. Yorktown Heights, New York, United States, pp. 313–322. 1986. ISBN 0-89791-194-6
https://en.wikipedia.org/wiki/Fortune%27s_algorithm.
See Also
Procedures: DCOLOURS.
Commands for: Graphics.
Example
CAPTION 'TRIANGULATION example'; STYLE=meta
"Generate 26 random points"
SET [SEED=75657]
CALCULATE X,Y = GRUNIFORM(26;0;1)
TRIANGULATION [PLOT=voronoi,delaunay] Y; X
TRIANGULATION [PLOT=combined] Y; X
"Colour surface by a Z variate"
CALCULATE Z = X + Y + GRUNIFORM(26;0;0.1)
TXPROGRESSION [INCLUDE=upper] FIRST='A'; LAST='Z'; PROGRESSION=Labels
PEN 1,2; COLOUR='navy','black' "Colors for lines and points"
TRIANGULATION Y; X; Z; LABELS=Labels; TITLE='Tessellation plot'
"Distinct colours using Genstat default colours"
PEN [RESET=yes] 1,2
PEN 2...17,19...29; SAVE=PS[1...26]
VARIATE [VALUES=PS[]['colour']} colours
PEN 2; COLOUR='black'; SYMBOL='circle'
TRIANGULATION [PLOT=voronoi] Y; X; Z; TITLE='Distinct colours'; \
COLOURS=colours; LABELS=Labels
"Restore pen 2"
PEN [RESET=yes] 2