Skip to main content

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

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]])

print(I.M.shape)                 # (50, 50, 1)
save(I.M, I.x, I.y, force=True)  # __1_debug.png


If you want to contribute, first clone git repository and then run tests:

$ git clone
$ pip3 install -r requirements.txt
$ pytest


Our method Current best
JFA_star JFA
steps = log*(2000) = 4 steps = log(720) ~= 10

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


Poznan University of Technology

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