log*（n）中voronoi图的gpu加速跳洪算法
fast-gpu-voronoi的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 |
实现的算法
| 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] |
安装示例
可以使用pip：
$ pip3 install fast_gpu_voronoi
这里有一个小例子可以激发您的食欲：
fromfast_gpu_voronoiimportInstancefromfast_gpu_voronoi.jfaimportJFA_starfromfast_gpu_voronoi.debugimportsaveI=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
开发
如果您想参与，请首先克隆git存储库，然后运行测试：
$ git clone git@github.com:maciejczyzewski/fast_gpu_voronoi.git $ pip3 install -r requirements.txt $ pytest
结果
| Our method | Current best |
|---|---|
| JFA* | JFA |
| steps = log*(2000) = 4 | steps = log(720) ~= 10 |
…对于x=720；y=720；seeds=2000（读作n=2000；p=720）。
谢谢
欢迎加入QQ群-->： 979659372
