search

georust / geo

Rust geospatial primitives & algorithms
https://crates.io/crates/geo
Other
1.56k stars 199 forks source link

Add geodesic distance/length algorithm #234

Closed frewsxcv closed 4 years ago

frewsxcv commented 6 years ago

It seems to be more accurate than Vincenty and always converges: https://github.com/geopy/geopy/pull/144

Psykopear commented 5 years ago

I'm working on this. I have the Inverse algorithm implemented, and it passes all the test cases found on the python implementation of geographiclib (I used that as a reference since it looked more readable to me). At the moment it is a 1:1 implementation, so lots of not idiomatic code, but it should be easier to debug the port.

I'll publish it on github and link it here once a I have a working implementation of at least the "Direct" algorithm too, so you guys can take a look at it.

frewsxcv commented 5 years ago

Awesome! Looking forward to it!

Psykopear commented 5 years ago

Here is the repo.

Considerations:

This port has two problems: 1) As I said, the code isn't idiomatic, it's mostly a 1:1 port. 2) The implementation seems to be on average 3 times slower than bindings to a C implementation I found here (you can try it by following the README)

About 1) the code could easily be made more idiomatic, but losing the naming might make porting the rest of the features, or future updates, harder.

As for 2) performance wise, there are a lot of low hanging fruit that would be solved by just refactoring the code for the first point, using right data structures, avoiding unnecessary clones ecc.

Anyway it's a starting point, a big part of the dirty work is done.

That said, I did this port as an exercise, and I'm not going to spend much more time over it (at least in the near future), so if anyone is willing to take it from here, the code is there for everyone to use, and I can answer questions about what I did.

michaelkirk commented 4 years ago

Hi @Psykopear - thanks for publishing that transcription!

I've forked it. You can see my WIP here: https://github.com/Psykopear/geodesic-rs/compare/master...michaelkirk:mkirk/correctness?expand=1

Beyond the unit tests you've implemented, I wanted to further validate the behavior using the test dataset published here: https://geographiclib.sourceforge.io/html/geodesic.html#testgeod

I built a test harness to do that here: https://github.com/michaelkirk/validate_geographiclib Which compares results against the reference cpp and python implementations.

This surfaced some correctness issues in the rust transcription, addressed in my fork linked above.

Now that we're getting accurate results for the published test set, I'm going to take a look at making some broader changes to address the performance stuff.

edit: accuracy changes merged here: https://github.com/michaelkirk/geographiclib-rs/pull/1

michaelkirk commented 4 years ago

I've followed up with the performance work and some other cleanup here https://github.com/michaelkirk/geographiclib-rs/pull/2

The summary is that I was able to shave off about 90% of the runtime in my benchmark. It's still about 50% slower than the c-wrappers, but I think it's fast enough to incorporate.

I'll be following up with a PR to incorporate this work into georust/geo.