search

georust / geo

Geospatial primitives and algorithms for Rust
https://crates.io/crates/geo
Other
1.49k stars 194 forks source link

Linear implementation of Frechet distance #1199

Closed gliderkite closed 2 weeks ago

gliderkite commented 2 weeks ago

This PR is due to the fact that when using the frechet_distance methods on our tools with long routes (200km+) we were not able to run it due to fatal runtime error: stack overflow.

This patch includes a new linear implementation (inspired from here) that removes recursion and allows to avoid the stack overflow fatal errors, while improving overall performances (~70% faster when testing 1000 10km-long routes).

urschrei commented 2 weeks ago

Oh and if you could contrive a test that fails using the old algorithm but passes now, that would be useful…

gliderkite commented 2 weeks ago

Oh and if you could contrive a test that fails using the old algorithm but passes now, that would be useful…

That would be tricky to do, because we would need to generate a huge route, store it somewhere so that it can be accessed locally and on CI to run tests. If you have suggestions or prior examples on how to do this as part of this repo (not sure if you already use git lfs, or have other tests that read from test resources, eg include_str, etc), I will be happy to add this.

urschrei commented 2 weeks ago

Oh and if you could contrive a test that fails using the old algorithm but passes now, that would be useful…

That would be tricky to do, because we would need to generate a huge route, store it somewhere so that it can be accessed locally and on CI to run tests. If you have suggestions or prior examples on how to do this as part of this repo (not sure if you already use git lfs, or have other tests that read from test resources, eg include_str, etc), I will be happy to add this.

Ah, in that case probably not worth the hassle.

gliderkite commented 2 weeks ago

Ah, in that case probably not worth the hassle.

I can create a deterministic test where we generate two very big LineString stored in memory to then compute the Frechet distance. We are not interested in the result, just that the test completes without panicking. This test will fail with the current implementation (but pass with the new one). If this sounds good to you I can add it as part of this PR.

urschrei commented 2 weeks ago

If this sounds good to you I can add it as part of this PR.

If you have time / capacity, that would be great.