VoronoiGraph

given vertices in generator-coordinates, collect the verts belonging to generator pairs, i.e. boundary vertices

starting at given points, run the ray shooting descent to find vertices

vertexheuristic(d, n)

expected number of vertices for n points in d dimensions c.f. [Dwyer, The expected number of k-faces of a Voronoi Diagram (1993)]

BFS of vertices starting from S0

mc_integrate(f::Function, i::Int, xs::Points, nmc=1000, nmc2=1000, searcher=Raycast(xs))

Integrate function f over cell i and its boundary using nmc rays per cell and nmc2 points per ray for the volume integral.

Returns:

• Vf::Real: the volume integral of f
• Af::SparseVector: Af[j] is the surface integral of f over the intersection between cells i and j.
• V::Real: the volume of cell i
• A::SparseVector: A[j] is the surface area of the intersection between cells i and j.

mc_volume(i, xs, nmc, searcher)

Estimate the area and volume of the i-th Voronoi cell from the Voronoi Diagram generated by xs by a Monte Carlo estimate from random rays

mc_volumes(xs::Points, nmc=1000)

Estimate the areas and volumes of the Voronoi Cells generated by xs using nmc Monte Carlo samples.

Returns

• SparseMatrix: the areas of the common boundaries of two cells
• Vector: the volumes of each cell

mc_volumes(sig::Vertices, xs::Points, nmc=1000)

In the case when the simplicial complex is already known this information can be used to speed up the Monte-Carlo sampling by restricting the search space

neighbors(sig::Vertices) --> Dict{Int, Vector{Int}}

Compute the neighbors of all generators.

generate a random ray orthogonal to the subspace spanned by the given points

generate a random ray orthogonal to the subspace spanned by the given points

shooting a ray in the given direction, find the next connecting point. This variant (by Poliaski, Pokorny) uses a binary search

Shooting a ray in the given direction, find the next connecting point. This variant uses an iterative NN search

shooting a ray in the given direction, find the next connecting point. This is the bruteforce variant, using a linear search to find the closest point

compute initial candidate assuming the resulting delauney simplex was regular this reduces number of extra searches by about 10%

affine transformation rotatinig and translating such that the boundary is aligned with the first dimension. A->B will be mapped to const*[1,0,0,...] and (A+B)/2 to [0,0,...]

build the connectivity matrix for the SQRA from adjacency and boundary information

construct the voronoi diagram from x through breadth-first search

construct a (partial) voronoi diagram from x through a random walk

starting at vertices, walk nsteps along the voronoi graph to find new vertices

find the vertex connected to v by moving away from its i-th generator