Stata implementation of Delaunay triangulation + Voronoi tessellation + convex hull

[Asjad Naqvi]

Dear all,

I have been working on a native implementation of Delaunay triangulation, Voronoi tessellation, and Convex hull in Stata.

The installation instructions for the beta version and sample code are here:
https://github.com/asjadnaqvi/stata-delaunay-voronoi

It is based on the S-hull algorithm, which is incredibly fast and is also the industry standard now. The Voronoi tessellation is recovered as a dual to the triangles, and the convex hull is a by-product of the search algorithm.

As some of you know, my interest is in expanding the visual capabilities of Stata so this was the primary aim. But Delaunay and Voronoi also have applications for spatial analysis.

Therefore, before I do some bug fixes, add other elements, and finetune the code, I would really appreciate the feedback on the community (if any). It will be great to know:

1) What features will be great to have
2) What could be potential applications

Suggestions for improving code structure are always welcome since I am new to the ado/Mata world. Packaging this up was already a fairly steep learning curve.

Asjad

[ericmelse]

Dear Asjad,

Yet another welcome contribution to the expanding library of packages for scientific visualization!
Thank you very much for making this effort.
I have installed your package and the replication of your example is perfect.

I suppose the first functional addition could be to have options to use the Voronoi tessellation for the classification of cases (assuming that the 'mapping' has a substantive geometric interpretation on the Euclidean plane set by x and y).
Certainly, I am not an expert on this subject but Google provides plenty references, like here.
For this to be practical, we would also need to have a parameter (option) to control the (size of the) regions. Or, alternatively, control the number of regions on the plane. I suppose this is useful even in the current implementation.

Even more ambitious, you could facilitate higher-order Voronoi subdivision of 3D space set by xyz (which would required 3 plots to visualize).

Then, besides using the Euclidean plane as such, I understand it is also possible to employ the metrics defined by the Mahalanobis distance.
Using that would add another statistical objective to this fine visualization.

[Asjad Naqvi]

Dear Eric,

Thank you so much for the feedback and also your support!

So for you points:
1) The size of regions is endogenous. The tessellations give the shortest distance from each point. This can be used, for example, to look at the catchment area of schools, hospitals, chain stores, etc. Reducing the number of regions essentially implies reducing the number of points required for calculations. This can already be done in the current setup. There are different algorithms that determine different types of tessellations (e.g. some that use Mahalanobis/Manhattan distance etc) but there are whole projects on their own and definitely worth looking into.

2) Regard adding a z-element. Yes definitely! The current set up is flexible enough to be extended to the third dimension. I have to solve two small bugs in the algorithm and then I will also add the z option. Most of the 3d figures we see online use delaunay triangles. They are the fastest and safest way for dealing with surfaces so it is definitely worth the investment.

[Asjad Naqvi]

Ver 1.02 update:

1) id option removed. Now you just type "delaunay x y", instead of "delaunay x y, id(id)". A new _id variable will be created. (Question: should it be make "delaunay y x" to be more comparable with other Stata functions dealing with x,y coordinates?)

2) "rescale" option added. Triangulation is not scale free since it is designed to deal with actual geometry. But if we want to triangulate abstract values where one variable is many times the magnitude of the other, then the program will generate stretched triangles. The rescale option normalizes both the x and y variables on a common range to calculate the triangles and tessellations and rescales them back.

installation instructions and examples here:
https://github.com/asjadnaqvi/stata-delaunay-voronoi

[Jared Greathouse]

Hey Asjad Naqvi, I'm only familiar with convex hulls within the framework of synthetic controls, which classically demand a set of points to fall within the convex-hull to generate weights.

Would your command be of use to researchers who use synthetic controls who might, for expository purposes, want to show what a convex hull is and why we'd want to use one in applications?

[Asjad Naqvi]

Dear Jared Greathouse, yes definitely the program can be used to calculate the convex hull in synthetic control applications. The program spits out ready-to-draw hull coordinates and it can easily be looped over data subsets.

Since the hull is a by-product of the program, i have not really looked into pure hull-specific applications but will catch up on the synth control literature.


A quick example below:

clear
sysuse auto

net install delaunay, from("https://raw.githubusercontent.com/asjadnaqvi/stata-delaunay-voronoi/main/installation/") replace

delaunay mpg weight if mpg < 25, rescale hull

twoway ///
   (scatter weight mpg, msize(small)) ///
   (line hull_y hull_x, lw(thin)) ///
       , legend(off)

[ericmelse]

Dear Asjad,

Great to see your latest update and example!

My 'vote', following your question in #4, is 'yes': make "delaunay y x" to be more comparable with other Stata functions dealing with x,y coordinates.

I suppose that it was (long ago) decided to follow the 'paradigm' of command depvar indepvar(s) too in Stata graphics/plottypes commands, like tw scatter y x and I suggest you should do the same.

Best,
Eric

[Asjad Naqvi]

Version 1.10 of the Stata Delaunay package is out! Voronoi tessellations can now be exported as shapes. This allows us to find points inside the boundaries (using geoinpoly) and color the cells based on different categories. An offset option added to increase or decrease the clip area of the tessellations. Several bug fixes including calculations of infinite rays, points being skipped, and finding the edges of boxes.

See installation files, example code, and other features here:
https://github.com/asjadnaqvi/stata-delaunay-voronoi


Next update will be sent to SSC so please report bugs, code improvements etc!