search

hugoledoux / startin

A Delaunay triangulator for processing TINs
MIT License
34 stars 9 forks source link

Laplacian interpolation 25 times slower than linear interpolation #16

Closed evetion closed 1 month ago

evetion commented 2 years ago

While some performance difference is expected, 25 times seems much.

One way of circumventing costly setup operations, such as calculating centre points, is to accept a vector of coordinates to interpolate for.

hugoledoux commented 2 years ago

that's a good idea.

then if that function is used:

  1. calculate and cache temporarily the centre of each triangle (its Voronoi dual)
  2. perform all the calculations
  3. flush the centres from memory
evetion commented 2 years ago

For reference, I benchmarked interpolation with 3.5M points/calls (via the C interface from Julia with some overhead because of raster interpolation) and got ~6 seconds for Laplacian and 0.24 seconds for Linear.

So while this could be faster, it's already pretty fast, kudos for that. 👍🏻

hugoledoux commented 1 month ago

Not sure why I never closed this issue, but here's the summary:

  1. for Laplace when I wrote this I must have been drunk or so, the Voronoi vertices I need are those are the temporarily inserted point for the interpolation location so you can't store them. I wouldn't know how to make Laplace faster, it is bound to be way slower than linear in TIN I'm afraid

  2. I have implemented in 64bc243ce7e83226fe81905dd98d6ed00cc0d820 this behaviour for NNI, you need to use the precompute param if you want to precompute.