I am happy to announce after passing my exams, with no help from this large sidetrack that was far more interesting, I have been able to produce something for my efforts: a master’s degree. More relevantly, however, my sidetrack actually turned into something small and hopefully useful for some: DiscreteVoronoi.jl.
The package is very small, consisting of 4 core functions and 5 exported helper functions for dealing with the construction and plotting of discrete (sometimes called approximate) Voronoi diagrams. These diagrams are matrices of SVector{2, Int}, and the sites from which the diagrams are generated are held in a vector of SVector{2, Int}. By requiring end users store information in such a way, the algorithms can be implemented to be completely non-allocating! As such, they are rather speedy.
Here is an example use:
using DiscreteVoronoi
using StaticArrays
using Random
using Plots
Random.seed!(12)
Coord = SVector{2, Int} # Optional, I just like doing it
n = 50
p = 10
grid = zeros(Coord, n, n)
sites = [Coord(rand(1:n, 2)) for _ in 1:p]
redac_voronoi!(grid, sites)
heatmap(label_voronoi_grid(grid), aspect_ratio=1.0, size= (500, 500), legend=false)
This produces the following plot:
which is honestly not the best looking as it doesn’t show where the sites actually are. The main focus of the library, and the reason I was looking for one like it back in March, is performance. If you are in the position of needing to calculate millions of discrete Voronoi diagrams, then this is for you!
Contributions are welcome in every part of the package from feature suggestions, bugfixes, performance improvements, and general code improvements because lord knows you shouldn’t trust software built in 4 days by an unqualified maths student.
I must thank the other author of this package @goerch for his contributions to the original code and working with me on the ideas behind the blazingly fast redac_voronoi!.