Parity with the JS version

[mourner]

@delfrrr happy to discover this port — great work! Just wanted to point out that several fixes that were made in the last week are very important for the algorithm robustness, so should definitely be ported out:

• mapbox/delaunator@dcfaf92
• mapbox/delaunator@3a61ecc
• mapbox/delaunator@b1f360c
• mapbox/delaunator@0cea584
• mapbox/delaunator@77a7992
• mapbox/delaunator@d7a7ce6

I'd also recommend porting over the tests from the JS version to make sure the edge cases are handled the same way.

[morishuz]

this is great! thanks for pointing this out.

we already discovered the hash key overrun issue, but came up with a different fix - essentially something like:

return Math.floor(pseudoAngle(x - this._cx, y - this._cy) * (this._hashSize-1)

but also added a guard for division by zero (admittedly not as much of an issue in js) for the case that:

(Math.abs(dx) + Math.abs(dy) = 0

[mourner]

@morishuz your hash key fix will have a different behavior — essentially the last item in the hash will almost never be used. I'd recommend keeping parity with the JS version.

As for the division by zero check — it's unnecessary because a point can't be equal to the seed triangles' circumcenter.

[delfrrr]

@mourner thanks! It was a bit a surprise to see that issue discovered by @morishuz with hashing was just fixed in JS version along with other improvements.

Yes that's a plan:

• delaunator-cpp as a port should follow the logic of JS version as close as possible so it's easy to port new changes
• I will add test from JS version (already started)
• Then I will port new changes provided by @mourner

[mourner]

Also note that the code changed quite a bit in mapbox/delaunator#32

[delfrrr]

Not sure about 4f072c2

My test does not show broken triangles even without race condition fix 🤔

[delfrrr]

Made it finally very close to delaunator@3.0.1; I guess that's it

[mourner]

Awesome! There's also this nice optimization that didn't yet make it into release but will: mapbox/delaunator#33