Idea: use the Rust port of Shewchuk's robust orientation library

[urschrei]

The issue of numerical stability in computational geometry having arisen yet again this week, I went looking for a Rust port of Jonathan Shewchuk's Fast Robust Predicates for Computational Geometry, only to discover that @Stoeoef ported it to Spade ages ago. The incircle test is less important for us (IIRC, we aren't using one at the moment), but we make use of orientation tests. I'm wondering whether @Stoeoef is open to making exactpred.rs available as a separate crate? I realise it's yet more fragmentation, and it's not super-urgent for us, but I'm very aware that we haven't done much around testing for robustness in Geo generally, and this would be a good first step.

[Stoeoef]

That sounds like a good use case for a crate, especially once it has more than one upstream user. Also thanks for the link first link, I haven't seen that one.

Keep in mind that Shewchuk's paper is not the state of the art any more, there may be more modern solutions to this problem. CGAL's filtering kernel seems to be based on another paper:

H. Brönnimann, C. Burnikel, and S. Pion. Interval arithmetic yields efficient dynamic filters for computational geometry. Discrete Applied Mathematics, 109:25–47, 2001.

I did not look if there's an easily adaptable solution for this algorithm in the public domain, though.

In any case, that's actually a good reason to put this into a crate, since a more modern predicate calculation could then reach others easily. Starting with Shewchuk and implementing a more modern algorithm "some time" in the future seems like the most sensible path.

I'll put this into its own crate and will update this issue once that's done.

[hugoledoux]

I would be a user of that crate 🙋🏼‍♂️

I already use the .rs file in https://github.com/hugoledoux/startin, thanks for porting that code to Rust.

[urschrei]

I would be a user of that crate 🙋🏼‍♂️

I already use the .rs file in https://github.com/hugoledoux/startin, thanks for porting that code to Rust.

Ah, I'm pretty sure I saw your use of it when I was googling around for ports / standalone implementations, which was what prompted this issue!

PS prepair is amazing – I'd love to implement something similar for geo if / when I have time (…)

[hugoledoux]

🙏🏽

I wrote a triangulator in Rust to see if Rust was as nice as they say, and I ended up annoying everyone in the lab speaking only about Rust 😬 Now I want to only use Rust, and thus perhaps I could help with porting it to Rust actually. The problem is that a constrained DT is needed, and that's nasty thing to get right (and robust). But perhaps Spades' CDT is a start... I'll give it some thoughts.

[frewsxcv]

@Stoeoef Mind if I start working on extracting out exactpred.rs into a separate crate? I'll give you credit+ownership of everything, just would like to start using it in geo. No worries if you're still planning to do it, there's no real rush

EDIT: Also just came across this. To give us better confidence about the accuracy of the implementation, we can generate random points, feed them to the Rust version and the C version, and ensure the same outputs

[frewsxcv]

To give us better confidence about the accuracy of the implementation, we can generate random points, feed them to the Rust version and the C version, and ensure the same outputs

I just created a tool that does just this! Looks like there might be a difference in the Rust version that's worth investigating:

p_a: (x: -0.0000000000000000033732417326292235, y: -710.1201610753293)
p_b: (x: -0.0000000000000006803180046827075, y: 0.0000000000000007474653075557756) 
p_c: (x: -5921927286181025000000000, y: -70060321899175880000000000000)

predicates.c orient2d: 0
exactpred.rs orient2d: 4205279958339305000000000000

I can take a closer look at this in the coming days, unless someone gets to it first

[Stoeoef]

There is a known bug, see Stoeoef/spade#48 . Did you use the upstream version of exactpred.rs? It should be fixed on master.

Other than that, please feel free to move the exact computations into their own crate, having a shareable crate for this makes sense.

[frewsxcv]

Did you use the upstream version of exactpred.rs? It should be fixed on master.

Yeah I think I'm using the latest, assuming this is the version you're talking about. The tool I wrote just operates on orient2d, and it looks like the fix you're talking about only affects incircle.

[hugoledoux]

I honestly don't know what the "correct" answer would be for your 3 points, but the answer from predicates.c is certainly completely wrong. It returns 0 and that would mean the 3 points are collinear, and they are clearly not.

The 3 points abc, in that order, have a CCW orientation, which should be positive, which is what exactpred.rs returns.

Either predicates.c is wrong (which I doubt), or you didn't setup correctly the constant for your compiler, see details here.

I strongly support this as a separate crate, great that you are willing to spend time on this!

[frewsxcv]

Here's the separate crate that was just published: https://github.com/georust/robust

[bluenote10]

@frewsxcv Thanks, perfect timing! A few bugs of the JS reference implementation behind rust-geo-booleanop have recently been fixed by using robust predicates. I just wanted to port it myself to Rust, in order to bring these fixes to the Rust implementation as well.

I'm new to Rust, and I'm wondering if there is a good way to avoid the type conversion. Currently the robust crate interface relies on its own robust::Coord type. As far as I can see, computing orient2d on a geo::Coordinate requires to first duplicate the data into a robust::Coord, which seems unnecessary and a bit tedious. What is the best solution to that in Rust? Would it make sense to change the interface to orient2d(pa_x: f64, pa_y: f64, pb_x: f64, pb_y: f64, pc_x: f64, pc_y: f64)?

[urschrei]

Let's move discussion over to the issues page -->

[frewsxcv]

Should we open a separate issue for actually incorporating robust orientation algorithms into this (geo) crate's algorithms?

[urschrei]

@hugoledoux @Stoeoef @bluenote10 FYI, v0.2.2 is now available on crates.io.