Skip to main content

GPU-Accelerated Jump Flooding Algorithm for Voronoi Diagram in log*(n)

Project description

JFA*

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 -- results
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
JFA_star JFA
steps = log*(2000) = 4 steps = log(720) ~= 10

...for x = 720; y = 720; seeds = 2000 (read as n = 2000; p = 720).

Thanks

Poznan University of Technology
OpenCl

Project details


Release history Release notifications

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Files for fast-gpu-voronoi, version 0.0.1
Filename, size & hash File type Python version Upload date
fast_gpu_voronoi-0.0.1-py2.py3-none-any.whl (26.8 kB) View hashes Wheel py2.py3
fast_gpu_voronoi-0.0.1.tar.gz (12.9 kB) View hashes Source None

Supported by

Elastic Elastic Search Pingdom Pingdom Monitoring Google Google BigQuery Sentry Sentry Error logging AWS AWS Cloud computing DataDog DataDog Monitoring Fastly Fastly CDN SignalFx SignalFx Supporter DigiCert DigiCert EV certificate StatusPage StatusPage Status page