GPU-Accelerated Jump Flooding Algorithm for Voronoi Diagram in log*(n)
Project description
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
JFA* | JFA+ | JFA | ||
---|---|---|---|---|
used improvement | noise+selection | noise | -- | |
num. of needed steps | log*(n) | log4(p) | log2(p) | |
step size | p/(3^i) | p/(2^i) | p/(2^i) | |
research | (our) | (our) | [Guodong 2006] |
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 git@github.com: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
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
fast_gpu_voronoi-0.0.3.tar.gz
(12.9 kB
view hashes)
Built Distribution
Close
Hashes for fast_gpu_voronoi-0.0.3-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 400015dd34e8be72f3be87b2fa38ca70c9142bd3da8704e56d5e4789d695cf25 |
|
MD5 | 704a09e627af3fb02a47c63c51219ada |
|
BLAKE2b-256 | 7cc43df8e25d1ca48bb517e0b2fb2b3b62b26adddbbc712e42e896f0c1c1a3d0 |