Optimising voronoi computation

General Usage Performance
1

Hi,

I am currently working on a project that needs to compute voronoi of points. The points increase exponentially over time. I am currently using DelaunayTriangulation package. I compute tri for the points and then voronoi.

Is there a way to reduce the computation time or compute the voronoi directly?

this is one example
Number of points - 73184
triangulation time - 75.524421458 s
vornoi computation time - 0.18559375 s

2

Hi! Can you post a minimum working example (self-contained code that does what you want, albeit too slowly) so that other people have an easier time helping out?

3 
function compute_voronoi(points)
    triangulate_time = @elapsed begin
        triangulation = triangulate(points)
    end
    println("tri time - $triangulate_time")
    voronoi_time = @elapsed begin
        voronoi = DelaunayTriangulation.voronoi(triangulation;)
    end

    println("vorn time - $voronoi_time")

    return voronoi
end

This is my function which is taking a lot of time especially for triangulation computation

4

Thanks! Can you provide a complete code that people can just run, including imports and data? To see why your specific use case is so slow, it would help to have a concrete example.

1 Like
5

You probably need to use spatial sorting.

Related:

I have some ideas for improving the speed of triangulate(points) but I haven’t found the time. Currently I’m the only person working on the package so progress can be slow. Contributions are welcome.

compute the voronoi directly

Not currently (probably never unless someone else wants to do it, I have no intention on it). It would have the same problem anyway.

And, as @gdalle says and as I have mentioned in all your other posts, if you want more detailed help you need to actually post runnable code.