Any chance of multi-threading support?

[zkk960317]

I generated a mesh in 517 seconds and the CPU was only used 10% on average. Multi-threading would speed up the computation significantly!

[DanielVandH]

I have thought about it a bit here #151 (there are a lot more papers not linked to in that thread, the linked paper is probably more complex than what is needed to just get basic multithreading support)

I agree that it would be very nice to have multi-threading, it's just not so simple to implement. Maybe eventually I can get around to thinking a bit more about it.

[DanielVandH]

Also note that another really good way to improve the mesh generation time is to use spatial sorting on your points to optimise the insertion order. I've not got a good example of that yet but it is usually recommended. An implementation of spatial sorting would be needed to get a good parallel implementation as well.

[DanielVandH]

One idea for parallelising the unconstrained triangulation stage is:

• Partition the data into $N$ spatial buckets $P_1, \ldots, P_N$ such that they overlap either not at all or only across a sequence of edges. Let $E_{ij}$ denote this sequence of edges for $P_i \cap P_j$ (which could be $E_{ij} = \emptyset$).
• Triangulate each $P_i$ in parallel.
• Next, initialise a constrained triangulation using the convex hull of the points and insert the segments from each $E_{ij}$ into the triangulation.
• Insert all the triangles from the triangles of each $P_i$ into the triangulation.
• Free all the constrained segments from the $E_{ij}$ and legalise them (legalise_edge! does this).
  I saw an idea like this in a paper somewhere, I don't remember the authors currently. If you wanted to have a go at this I'm happy to help, otherwise I'll try and get to it eventually.

[zkk960317]

This scheme of yours suffers from the complexity of handling subregion junctions, I have a scheme I thought of myself here for your reference, but I don't have the energy to realize it.

1. first give a few straight lines to divide the region $n$ equal.
2. Starting from the line segment intersected with the dividing line on the boundary, quickly find its delaunay triangle according to the empty circle property of delaunay edges, get the other two edges, and then choose the edge intersected with the dividing line to repeat this step until another boundary is reached. The result is a delaunay triangle junction strip. For different strips can be calculated in parallel.
3. According to these dividing strips the nodes in the region are dispersed into subregions for parallel computation to complete the delaunay triangulation.
4. Finally, the subregion mesh and the delaunay strips can be merged simply.

[DanielVandH]

Interesting. Thanks for your ideas. Once I start working on it properly I'll read up some more about it and see what I can do. Another area that the package could be sped up (other than spatial sorting as mentioned) in is in find_triangle if you happen to be interested in that, that's where like 90% of the work is done.

[DanielVandH]

FYI, I'm slowly working on v2.0 in https://github.com/JuliaGeometry/DelaunayTriangulation.jl/tree/v2 where a lot of speed improvements will be made. It reduces the allocations by like 99% (literally) as well, and spatial sorting is almost done (not committed into the branch yet). If you want to try it out maybe you can help see if that branch has improved the computation time of your problem @zkk960317, and maybe again once spatial sorting is actually done (which can improve runtime by a crazy amount).

[Maybe your code can be run without changes, but in case it can't see https://github.com/JuliaGeometry/DelaunayTriangulation.jl/blob/v2/NEWS.md#v20 for possible fixes]

You can also submit code that generates your mesh and maybe I can try and profile it to help see what else I can improve for v2.0 if you like.