help delaunaydelaunay v1.2 (GitHub)

DELAUNAY

delaunay implements the S-Hull algorithm (Sinclair 2016) for generating the Delaunay triangles. The Convex hull is a derived as a residual. The Voronoi tessellations are generated as a dual to the triangles.

The Delaunay and Voronoi routines are based on Mapbox and D3 implementations respectively.
S-hull, or sweeping-hull, is a divide-and-conquer algorithm that iterates over radially-sorted points, relative to an intial seed point, and generates and flips triangles as it moves along.
It is exceptionally fast as compared to other implementations.

Syntax

delaunay y x [if] [in] [, rescale triangles hull voronoi(lines polygons) offset(value) replace addbox]

The options are described as follows:

delaunay y x The command requires an (y,x) coordinate pair stored as two numeric variables.
Please make sure that the order of the variables is correct.
Running the command will automatically add the _ID variable to the dataset.

rescale Delaunay triangles and Voronoi tessellations are not agnostic about the scale of the axes. They are designed for physical geometry where the relation of the x and y scales matter.
If we are working with data where one variable is several times the magnitude of the other, then the command will correctly execute the triangles but they might be stretched in one direction.
The rescale option normalizes both the x and y variables on the [0,1] range,
calculates the triangles and rescales them back to provide reasonable looking triangles.

triangles Export the triangles in the _triangles.dta files. Each triangle is identified by a _group variable. Each coordinate has an _ID variable that allows it to be matched to the original data.

hull Exports the convex hull back to Stata as three new variables hull_ID, hull_X, hull_Y. hull_ID corresponds to the variable _ID. The remaining two variables are the coordinates.
The starting point is repeated at the end, in order to draw a fully enclosed hull in Stata.

voronoi(lines polygons) Exports the Voronoi tesselations back to Stata as lines or polygons or both.
The lines option generates a _vorlines.dta file, which contains four variables vline_x1, vline_y1, vline_x2, vline_y2 which are the end coordinates of each line.
The polygons option generates a _vorpoly.dta file, which contains three variables _ID, _X, _Y. This is essentially a shapefile can be used with the main data using the spmap command.

offset(value) Voronoi tesselations, have a bounding box defined as xmax + xdisp, xmin - xdisp, ymax + ydisp, ymin - ydisp, where xdisp = (xmax - xmin) * offset and ydisp = (ymax - ymin) * offset.
The default offset is 0.05 or +5% displacement.

replace This option replaces the existing files and hull variables. If replace is not specified, and the files already exist, the command will throw an error.
This ensures that files are not accidentally overwritten.

addbox This is an experimental command that is used for adding a bounding box for triangles.
This is still being tested and it is highly recommended to use this only with triangles. It might result errors with Voronoi exports.

NOTE: The program will generate a unique identifier, _ID, in the main file. If this variable already exists, the replace option will overwrite it.

For code examples, please see the GitHub page.
If you find and error, please open an Issue.

Version history

- 1.2 : Stable release. Triangles and Voronoi are exported as files. The command is now much faster.
- 1.11: Order of x and y flipped. Faster export to Stata. Error messages added.
- 1.10: Delaunay point skipping fixed. Voronoi rays fixed. Voronoi polygons and offset added.
- 1.02: Rescale function added. id option removed. The program generates its own _id variable.
- 1.01: Minor code cleanups. [if] [in] conditions.
- 1.00: First release

Package details

Version : delaunay v1.2
This release : 04 Sep 2022
First release: 05 Dec 2021
Repository : GitHub
Keywords : Stata, delaunay, voronoi, convex hull, s-hull, algorithm,
License : MIT

Author : Asjad Naqvi
E-mail : asjadnaqvi@gmail.com
Twitter : @AsjadNaqvi

Want to cite this package?

Naqvi, A. (2022). Delaunay v1.2: A Stata package for Delaunay triangles, Convex hulls, and Voronoi tessellations. https://github.com/asjadnaqvi/stata-delaunay-voronoi.

Acknowledgments

The package greatly benefited from discussions with Eric Melse and William Buchanan.

References

Sinclair, D.A. (2016). S-hull: a fast radial sweep-hull routine for Delaunay triangulation. arXiv 1604.01428.

Mapbox (2022). Delaunator library.

D3 (2022). d3-delaunay.