fast_gpu_voronoi
fast_gpu_voronoi copied to clipboard
Published
20 hours ago •
maciejczyzewski
maciejczyzewski
GPU-Accelerated Jump Flooding Algorithm for Voronoi Diagram in log*(n)
| 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 [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
Metadata
24
Stars
4
Forks
Watchers
Owner
maciejczyzewski
Metadata
GPU-Accelerated Jump Flooding Algorithm for Voronoi Diagram in log*(n)