# Optimising voronoi computation

**URL:** <https://discourse.julialang.org/t/optimising-voronoi-computation/119297>\
**Category:** Performance\
**Tags:** question\
**Created:** [September 11, 2024, 9:04pm UTC](https://discourse.julialang.org/t/optimising-voronoi-computation/119297 "2024-09-11T21:04:01Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![Manasa\_S](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/manasa_s/32/209514_2.png) [@Manasa\_S](https://discourse.julialang.org/u/Manasa_S)\
**Post date:** [September 11, 2024, 9:04pm UTC](https://discourse.julialang.org/t/optimising-voronoi-computation/119297/1 "2024-09-11T21:04:01Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [September 12, 2024, 6:00am UTC](https://discourse.julialang.org/t/optimising-voronoi-computation/119297/2 "2024-09-12T06:00:11Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![Manasa\_S](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/manasa_s/32/209514_2.png) [@Manasa\_S](https://discourse.julialang.org/u/Manasa_S)\
**Post date:** [September 12, 2024, 6:40am UTC](https://discourse.julialang.org/t/optimising-voronoi-computation/119297/3 "2024-09-12T06:40:15Z")

</div>

```julia
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

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [September 12, 2024, 7:08am UTC](https://discourse.julialang.org/t/optimising-voronoi-computation/119297/4 "2024-09-12T07:08:39Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![DanielVandH](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/danielvandh/32/31134_2.png) [@DanielVandH](https://discourse.julialang.org/u/DanielVandH)\
**Post date:** [September 12, 2024, 8:20am UTC](https://discourse.julialang.org/t/optimising-voronoi-computation/119297/5 "2024-09-12T08:20:43Z")

</div>

You probably need to use spatial sorting.

Related:

> **[Any chance of multi-threading support? ·...](https://github.com/JuliaGeometry/DelaunayTriangulation.jl/discussions/179)**
>
> I generated a mesh in 517 seconds and the CPU was only used 10% on average. Multi-threading would speed up the computation significantly!

> **[Spatial sorting for fast insertion · JuliaGeometry/DelaunayTriangulation.jl ·...](https://github.com/JuliaGeometry/DelaunayTriangulation.jl/discussions/145)**
>
> It would be nice to have a method for sorting points in space, such as with a Hilbert sort. Obviously this could be provided by the user (with the point\_order kwarg), but it would be nice to have a...

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.