Issue #43

[Fil]

This PR contains a fix and test for #43: the idea is that the cross-product ABxAC is not stable, so we have a majority vote on the sign of ABxAC, BCxBA, CAxCB. The formula for the majority vote is symmetric, so it always gives the same answer for a given triangle. (For performance, we don't call the vote if ABxAC is not too small.)

I've also included a fix and test files for related issues with the voronoi (https://observablehq.com/d/bd8a95abd9a01c79 & https://observablehq.com/d/b219d92fae85fc9b), but as these issues only show in voronoi (ie in d3-delaunay)—the tests don't actually fail. I'm not sure what to do with this part — I don't see a way of fixing that in d3-delaunay directly though, so I've stuck it here for discussion.

With these two, all the test notebooks are fixed.

[Fil]

Cleaner version. The fixes for voronoi will be in d3-delaunay (https://github.com/d3/d3-delaunay/pull/86).

[Fil]

asymmetric orientation tests can occur within a set of points > 3 (where pairwise they're stable but inconsistent as a system)

An asymmetric (but consistent) method could be to start with the top-left point of the set — but for triangles it would be less elegant (and probably more code).

inCircle tests may be unstable too

🤯

[mourner]

Did some exploration of the topic and came up with an alternative approach ("More precise" in the notebook) — @Fil check it out and let me know what you think: https://observablehq.com/@mourner/non-robust-arithmetic-as-art

[Fil]

👍 I like the fact that it separates l and r — hadn't thought of it that way.

And the notebook is ⚡️

[mourner]

It may be a little slower than the voting approach because of the extra operations for bounds checking, but the advantage is that it's a proven error bound — with arbitrary ones like 1e6, we can't be sure this won't break for some fringe cases.

[mourner]

Actually somehow it looks ~15-20% faster — here are my results if you change bench to generate points within 0..1 (to trigger collinearity more):

# with error bound
20000: 11.108ms
100000: 75.444ms
200000: 175.354ms
500000: 506.151ms
1000000: 989.714ms

# voting 
20000: 12.186ms
100000: 96.920ms
200000: 217.174ms
500000: 556.190ms
1000000: 1172.073ms

The tests failed at first but that turned out to be because of non-robust convex check. :) Updated to use the same formula there too and it passes now. Pushed my commit here.

[mbostock]

Fantastic work! 👏👏👏