fast_gpu_voronoi
GPU-Accelerated Jump Flooding Algorithm for Voronoi Diagram in log*(n)
MIT License
Ecosystems:
Python
| Research | Authors | |
|---|---|---|
| [slides] | GPU-Accelerated Jump Flooding Algorithm for Voronoi Diagram in log*(n) [this] | Maciej A. Czyzewski |
| [article] | Facet-JFA: Faster computation of discrete Voronoi diagrams [2014] | Talha Bin Masood, Hari Krishna Malladi, Vijay Natarajan |
| [article] | Jump Flooding in GPU with Applications to Voronoi Diagram and Distance Transform [2006] | Guodong Rong, Tiow-Seng Tan |
Implemented Algorithms
Installation & Example
Project can be installed using pip:
$ pip3 install fast_gpu_voronoi
Here is a small example to whet your appetite:
from fast_gpu_voronoi import Instance
from fast_gpu_voronoi.jfa import JFA_star
from fast_gpu_voronoi.debug import save
I = Instance(alg=JFA_star, x=50, y=50, \
pts=[[ 7,14], [33,34], [27,10],
[35,10], [23,42], [34,39]])
I.run()
print(I.M.shape) # (50, 50, 1)
save(I.M, I.x, I.y, force=True) # __1_debug.png
Development
If you want to contribute, first clone git repository and then run tests:
$ git clone [email protected]:maciejczyzewski/fast_gpu_voronoi.git
$ pip3 install -r requirements.txt
$ pytest
Results
| Our method | Current best |
|---|---|
| JFA* | JFA |
 |
 |
| steps = log*(2000) = 4 | steps = log(720) ~= 10 |
...for x = 720; y = 720; seeds = 2000 (read as n = 2000; p = 720).
Thanks
Package Rankings
Top 20.98% on Pypi.org