search

maciejczyzewski / fast_gpu_voronoi

GPU-Accelerated Jump Flooding Algorithm for Voronoi Diagram in log*(n)
https://git.io/jfa_star_slides
MIT License
25 stars 4 forks source link

Scipy-compatible output #3

Open AntonBiryukovUofC opened 4 years ago

AntonBiryukovUofC commented 4 years ago

@maciejczyzewski and @KamilPiechowiak ,

I was wondering if there is a way to add a few more attributes to the output. So far you are storing X/Y and the matrix of points labelled by the region it belongs to.

I noticed that Scipy Voronoi implementation (https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.Voronoi.html) actually has really convenient access to vertices and regions. While I know it is possible to extract similar attributes likely via scipy.ConvexHull, it might also add the overhead to the calculation that is "almost" done in openCL performant code.

Do you think it would be difficult to actually do the calc directly in OpenCL and expose similar attributes?

Thanks, Anton.

PS. Why am I asking? I am trying to make an open-source library for stippling in python that relies on: https://github.com/ReScience-Archives/Rougier-2017/issues/3 They are using Voronoi diagrams there obtained via Scipy, and so far according to the code profiler that is one of the slower spots (I have sped up some of the calculation via numba).

maciejczyzewski commented 4 years ago

Great idea. I'll try to research/implement it next week. Do you know any other projects/case of use where our version of fast voronoi will be useful?

nikhilbv commented 3 years ago

Hello @maciejczyzewski

I am a mapping guy working on extracting centreline from a polygon that relies on https://centerline.readthedocs.io/en/latest/ . They are using a scipy.spatial.Voronoi which is computationally expensive. It would really be helpful if you expose similar attributes to scipy.spatial.Voronoi

Thanks, Nikhil