VoronoiGraph
Voronoi diagrams in N dimensions using an improved raycasting method.
Science Score: 54.0%
This score indicates how likely this project is to be science-related based on various indicators:
-
✓CITATION.cff file
Found CITATION.cff file -
✓codemeta.json file
Found codemeta.json file -
○.zenodo.json file
-
✓DOI references
Found 2 DOI reference(s) in README -
✓Academic publication links
Links to: acm.org, zenodo.org -
○Committers with academic emails
-
○Institutional organization owner
-
○JOSS paper metadata
-
○Scientific vocabulary similarity
Low similarity (10.3%) to scientific vocabulary
Keywords
Keywords from Contributors
Repository
Voronoi diagrams in N dimensions using an improved raycasting method.
Basic Info
Statistics
- Stars: 7
- Watchers: 2
- Forks: 1
- Open Issues: 5
- Releases: 5
Topics
Metadata Files
README.md
VoronoiGraph
This Package implements a variation of the Voronoi Graph Traversal algorithm by Polianskii and Pokorny [1]. It constructs a Voronoi Diagram from a set of points by performing a random walk on the graph of the vertices of the diagram. Unlike many other Voronoi implementations this algorithm is not limited to 2 or 3 dimensions and promises good performance even in higher dimensions.
Usage
We can compute the Voronoi diagram with a simple call of voronoi
julia
julia> data = rand(4, 100) # 100 points in 4D space
julia> v, P = voronoi(data)
which returns the vertices v::Dict. keys(v) returns the simplicial complex of the diagram,
wheras v[xs] returns the coordinates of the vertex inbetween the generators data[xs].
Additionally P contains the data in a vector-of-vectors format, used for further computations.
It also exports the random walk variant (returning only a subset of vertices):
julia
julia> v, P = voronoi_random(data, 1000) # perform 1000 iterations of the random walk
Area / Volume computation
julia
julia> A,V = volumes(v, P)
computes the (deterministic) areas of the boundaries of neighbouring cells (as sparse array A)
as well as the volume of the cells themselves (vector V) by falling back onto the Polyhedra.jl volume computation.
Monte Carlo
Combining the raycasting approach with Monte Carlo estimates we can approximate the areas and volumes effectively:
julia
julia> A, V = mc_volumes(P, 1000) # cast 1000 Monte Carlo rays per cell
If the simplicial complex of vertices is already known we can speed up the process:
julia
julia> A, V = mc_volumes(v, P, 1000) # use the neighbourhood infromation contained in v
We furthermore can integrate any function f over a cell i and its boundaries:
julia
julia> y, δy, V, A = mc_integrate(x->x^2, 1, P, 100, 10) # integrate cell 1 with 100 boundary and 100*10 volume samples
Here y and the vector δy contain the integrals over the cell and its boundaries. V and A get computed as a byproduct.
References
[1] V. Polianskii, F. T. Pokorny - Voronoi Graph Traversal in High Dimensions with Applications to Topological Data Analysis and Piecewise Linear Interpolation (2020, Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining)
Owner
- Name: Alexander
- Login: axsk
- Kind: user
- Location: Berlin
- Company: Zuse Institute Berlin
- Repositories: 55
- Profile: https://github.com/axsk
Mathematician
Citation (CITATION.bib)
@misc{VoronoiGraph.jl,
author = {Alexander Sikorski},
title = {VoronoiGraph.jl},
url = {https://github.com/axsk/VoronoiGraph.jl},
version = {v0.1.0},
year = {2021},
month = {10}
}
GitHub Events
Total
- Watch event: 1
Last Year
- Watch event: 1
Committers
Last synced: 8 months ago
Top Committers
| Name | Commits | |
|---|---|---|
| Sikorski | s****i@z****e | 87 |
| github-actions[bot] | 4****] | 4 |
| CompatHelper Julia | c****y@j****g | 4 |
Committer Domains (Top 20 + Academic)
Issues and Pull Requests
Last synced: 7 months ago
All Time
- Total issues: 11
- Total pull requests: 8
- Average time to close issues: about 13 hours
- Average time to close pull requests: about 2 months
- Total issue authors: 3
- Total pull request authors: 1
- Average comments per issue: 0.82
- Average comments per pull request: 0.0
- Merged pull requests: 4
- Bot issues: 0
- Bot pull requests: 8
Past Year
- Issues: 0
- Pull requests: 0
- Average time to close issues: N/A
- Average time to close pull requests: N/A
- Issue authors: 0
- Pull request authors: 0
- Average comments per issue: 0
- Average comments per pull request: 0
- Merged pull requests: 0
- Bot issues: 0
- Bot pull requests: 0
Top Authors
Issue Authors
- axsk (9)
- asinghvi17 (1)
- JuliaTagBot (1)
Pull Request Authors
- github-actions[bot] (8)
Top Labels
Issue Labels
Pull Request Labels
Packages
- Total packages: 1
- Total downloads: unknown
- Total dependent packages: 0
- Total dependent repositories: 0
- Total versions: 5
juliahub.com: VoronoiGraph
Voronoi diagrams in N dimensions using an improved raycasting method.
- Documentation: https://docs.juliahub.com/General/VoronoiGraph/stable/
- License: MIT
-
Latest release: 0.2.2
published about 3 years ago
Rankings
Dependencies
- actions/cache v1 composite
- actions/checkout v2 composite
- codecov/codecov-action v2 composite
- julia-actions/julia-buildpkg v1 composite
- julia-actions/julia-docdeploy v1 composite
- julia-actions/julia-processcoverage v1 composite
- julia-actions/julia-runtest v1 composite
- julia-actions/setup-julia v1 composite
- JuliaRegistries/TagBot v1 composite
- actions/cache v1 composite
- actions/checkout v2 composite
- benchmark-action/github-action-benchmark v1 composite
- julia-actions/setup-julia v1 composite
- julia-actions/RegisterAction latest composite