Closed andreesteve closed 3 years ago
@andreesteve this is great! The perf hit is definitely worth it, although it seems to be much bigger than the JS equivalent — perhaps an issue with the robust
crate code which might have room for optimization.
I'm not sure why the original issue isn't reproducible, but it's worth checking whether all the other "robustness" test cases pass the validation without the robust orientation, and additionally the test case reported in #10.
Not sure where the connectivity issue comes from — needs investigation (debugging the same case side by side with the JS version to see what goes differently).
@mourner - to make sure I am not missing anything, when you talk about the robustness checks you are talking about the triangle vs hull area error check done in https://github.com/mapbox/delaunator/blob/master/test/test.js? I see we have the same checks for our test cases.
Thanks for pointing to issue #10 - I added a test case to cover it. Interestingly enough I get a visually correct triangulation with and without the orient2d changes in this PR. Also the area checks and half-edge connection checks pass in both master and this robust branch.
I have added all the robustness test inputs from the JS:
Running tests/tests.rs (target/debug/deps/tests-9dd7cff8b40a6e26)
running 15 tests
test bad_input ... ok
test issue11js ... ok
test issue24js ... ok
test issue43js ... ok
test issue13js ... ok
test robust6 ... ok
test robust5 ... ok
test issue10 ... ok
test robust2 ... ok
test unordered_collinear_points_input ... ok
test robustness ... ok
test robust4 ... ok
test basic ... ok
test ukraine ... ok
test robust3 ... ok
test result: ok. 15 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.04s
Doc-tests delaunator
running 1 test
test src/lib.rs - (line 6) ... ok
test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.17s
I was wondering if this could be hardware specific, but I got the same output on the VM I host my blog. I'll ping the person that reported the bug and see if they would be able to try that input with this new changes.
For the connectivity, I'll investigate that and send a separate PR.
Hi @mourner ! Sorry for the hiatus. I got time to get back to this and tackle the last open items from #15 related to robustness:
I also validated that these changes fix #10 - I added all the details and screenshots on the issue's discussion page.
With this, #15 is almost done. The only thing left is adding the update
method, but I'd prefer to do that on a separate PR since this is too big already!
I think this is good to merge. Please let me know your feedback. Thanks!
This PR addresses the robustness issue tracked in #15, based on mapbox/delaunator/pull/68
Changes
cargo test
Benchmark
The robust checks are slower by about ~8-10%
Commentary
During testing, I was not able to reproduce issue mapbox/delaunator/issues/61 with or without this change.
For example, this is what the triangulation output looks on current master:
This is what it looks like with the new orient2d checks:
And this is what it looks as reported on the original issue:
While testing, I came across #18, so I added the checks for connectivity on the test case but left commented out for now, until we can address that issue (which is unrelated to this).
Additionally, this change may lead to supporting the ask in #4, at least for f32 if we move from our Point struct to the Coord struct defined in the robust crate.
Overall, the performance impact is significant but worth it in my mind to guarantee correctness. I am just unsure about these changes because I couldn't repro the original issue yet. Please let me know your thoughts.