{ "info": { "author": "Maciej A. Czyzewski", "author_email": "maciejanthonyczyzewski@gmail.com", "bugtrack_url": null, "classifiers": [ "License :: OSI Approved :: MIT License", "Programming Language :: Python", "Programming Language :: Python :: 3", "Programming Language :: Python :: 3.6", "Programming Language :: Python :: Implementation :: CPython", "Programming Language :: Python :: Implementation :: PyPy" ], "description": "\n
\n \"JFA*\"
\n
\n\n
\n\n| | Research | Authors |\n|:----|:---------|:--------|\n| \\[[slides](https://maciejczyzewski.github.io/fast_gpu_voronoi/slides_small.pdf)\\] | __GPU-Accelerated Jump Flooding Algorithm for Voronoi Diagram in log*(n)__ [this] | Maciej A. Czyzewski |\n| \\[[article](https://vgl.csa.iisc.ac.in/pdf/pub/ICVGIP14_Talha.pdf)\\] | Facet-JFA: Faster computation of discrete Voronoi diagrams [2014] | Talha Bin Masood, Hari Krishna Malladi, Vijay Natarajan |\n| \\[[article](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.101.8568&rep=rep1&type=pdf)\\] | Jump Flooding in GPU with Applications to Voronoi Diagram and Distance Transform [2006] | Guodong Rong, Tiow-Seng Tan |\n\n# Implemented Algorithms\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
JFA*JFA+JFA
used improvementnoise+selectionnoise--\"results\"
num. of needed stepslog*(n)log4(p)log2(p)
step sizep/(3^i)p/(2^i)p/(2^i)
research(our)(our)[Guodong 2006]
\n\n# Installation & Example\n\nProject can be installed using `pip`:\n\n```bash\n$ pip3 install fast_gpu_voronoi\n```\n\nHere is a small example to whet your appetite:\n\n```python3\nfrom fast_gpu_voronoi import Instance\nfrom fast_gpu_voronoi.jfa import JFA_star\nfrom fast_gpu_voronoi.debug import save\n\nI = Instance(alg=JFA_star, x=50, y=50, \\\n pts=[[ 7,14], [33,34], [27,10],\n [35,10], [23,42], [34,39]])\nI.run()\n\nprint(I.M.shape) # (50, 50, 1)\nsave(I.M, I.x, I.y, force=True) # __1_debug.png\n```\n\n# Development\n\nIf you want to contribute, first clone git repository and then run tests:\n\n```bash\n$ git clone git@github.com:maciejczyzewski/fast_gpu_voronoi.git\n$ pip3 install -r requirements.txt\n$ pytest\n```\n\n# Results\n\n| Our method | Current best |\n|:-------------------------------:|:---------------------:|\n| JFA\\* | JFA |\n| ![JFA_star](docs/jfa_star2.gif) | ![JFA](docs/jfa2.gif) |\n| steps = log\\*(2000) = 4 | steps = log(720) ~= 10 |\n\n_...for x = 720; y = 720; seeds = 2000 (read as n = 2000; p = 720)._\n\n# Thanks\n\n
\n \"Poznan
\n \"OpenCl\"\n
\n\n\n", "description_content_type": "text/markdown", "docs_url": null, "download_url": "", "downloads": { "last_day": -1, "last_month": -1, "last_week": -1 }, "home_page": "https://github.com/maciejczyzewski/fast_gpu_voronoi", "keywords": "", "license": "MIT", "maintainer": "", "maintainer_email": "", "name": "fast-gpu-voronoi", "package_url": "https://pypi.org/project/fast-gpu-voronoi/", "platform": "", "project_url": "https://pypi.org/project/fast-gpu-voronoi/", "project_urls": { "Homepage": "https://github.com/maciejczyzewski/fast_gpu_voronoi" }, "release_url": "https://pypi.org/project/fast-gpu-voronoi/0.0.1/", "requires_dist": [ "imageio (==2.4.1)", "matplotlib (==3.0.3)", "pyopencl (==2018.2.5)", "numpy (==1.16.2)", "tqdm (==4.28.1)" ], "requires_python": ">=3.1.0", "summary": "GPU-Accelerated Jump Flooding Algorithm for Voronoi Diagram in log*(n)", "version": "0.0.1" }, "last_serial": 5320131, "releases": { "0.0.1": [ { "comment_text": "", "digests": { "md5": "747080fa291e59b1270cbea32a2f84c3", "sha256": "3145f2bccee5cfde6ae78e2ebec9281a59774a6090a4075a2072d672d7d50d5c" }, "downloads": -1, "filename": "fast_gpu_voronoi-0.0.1-py2.py3-none-any.whl", "has_sig": false, "md5_digest": "747080fa291e59b1270cbea32a2f84c3", "packagetype": "bdist_wheel", "python_version": "py2.py3", "requires_python": ">=3.1.0", "size": 26781, "upload_time": "2019-05-27T00:20:52", "url": "https://files.pythonhosted.org/packages/93/d7/e72101aa42f64de08f02403b45a5228412ac32072f5668c37669a77a9757/fast_gpu_voronoi-0.0.1-py2.py3-none-any.whl" }, { "comment_text": "", "digests": { "md5": "2b91bfd57d14085fc42723b9819342a8", "sha256": "aa1febbca8fcec88493ebe5311a5310212a521bdf1c91da9fbdf6c1cbbc72b18" }, "downloads": -1, "filename": "fast_gpu_voronoi-0.0.1.tar.gz", "has_sig": false, "md5_digest": "2b91bfd57d14085fc42723b9819342a8", "packagetype": "sdist", "python_version": "source", "requires_python": ">=3.1.0", "size": 12864, "upload_time": "2019-05-27T00:20:55", "url": "https://files.pythonhosted.org/packages/10/a9/870a8ceff318f138b0815b7c0b08d0ce464c23bc1bf7c4d4d681a69bd813/fast_gpu_voronoi-0.0.1.tar.gz" } ] }, "urls": [ { "comment_text": "", "digests": { "md5": "747080fa291e59b1270cbea32a2f84c3", "sha256": "3145f2bccee5cfde6ae78e2ebec9281a59774a6090a4075a2072d672d7d50d5c" }, "downloads": -1, "filename": "fast_gpu_voronoi-0.0.1-py2.py3-none-any.whl", "has_sig": false, "md5_digest": "747080fa291e59b1270cbea32a2f84c3", "packagetype": "bdist_wheel", "python_version": "py2.py3", "requires_python": ">=3.1.0", "size": 26781, "upload_time": "2019-05-27T00:20:52", "url": "https://files.pythonhosted.org/packages/93/d7/e72101aa42f64de08f02403b45a5228412ac32072f5668c37669a77a9757/fast_gpu_voronoi-0.0.1-py2.py3-none-any.whl" }, { "comment_text": "", "digests": { "md5": "2b91bfd57d14085fc42723b9819342a8", "sha256": "aa1febbca8fcec88493ebe5311a5310212a521bdf1c91da9fbdf6c1cbbc72b18" }, "downloads": -1, "filename": "fast_gpu_voronoi-0.0.1.tar.gz", "has_sig": false, "md5_digest": "2b91bfd57d14085fc42723b9819342a8", "packagetype": "sdist", "python_version": "source", "requires_python": ">=3.1.0", "size": 12864, "upload_time": "2019-05-27T00:20:55", "url": "https://files.pythonhosted.org/packages/10/a9/870a8ceff318f138b0815b7c0b08d0ce464c23bc1bf7c4d4d681a69bd813/fast_gpu_voronoi-0.0.1.tar.gz" } ] }