Floating point precision can lead to incorrect triangulation

[ghost]

In rare cases the triangulation fails and appears to originate from the precision of the data sent to the earcut function.

Below is data for a simple ring with a hole which triangulates correctly:

[[143.129527283745121, 61.240160826593642, 12.157953862848911],
  [147.399527283763751, 74.780160826630892, 12.157953862848911],
  [154.049527283757931, 90.260160827077932, 12.157953862848911],
  [174.429527283762581, 81.710160826332872, 12.157953862848911],
  [168.03952728374861, 67.040160826407372, 12.157953862848911],
  [159.099527283746281, 53.590160826221112, 12.157953862848911]],

[[156.85952728375561, 67.430160827003422, 12.157953862848911],
  [157.489527283760251, 67.160160826519132, 12.157953862848911],
  [159.969527283741631, 68.350160826928912, 12.157953862848911],
  [161.339527283766071, 67.640160826966172, 12.157953862848911],
  [159.649527283763751, 63.310160826891662, 12.157953862848911],
  [155.759527283749781, 64.880160826258362, 12.157953862848911]]
]

Modifying the y-coordinate of the first ring point slightly (61.240160826593642 -> 61.240160826593640) produces incorrect triangles (tested with the triangulation test of earcut):

[[143.129527283745121, 61.240160826593640, 12.157953862848911],
  [147.399527283763751, 74.780160826630892, 12.157953862848911],
  [154.049527283757931, 90.260160827077932, 12.157953862848911],
  [174.429527283762581, 81.710160826332872, 12.157953862848911],
  [168.03952728374861, 67.040160826407372, 12.157953862848911],
  [159.099527283746281, 53.590160826221112, 12.157953862848911]],

[[156.85952728375561, 67.430160827003422, 12.157953862848911],
  [157.489527283760251, 67.160160826519132, 12.157953862848911],
  [159.969527283741631, 68.350160826928912, 12.157953862848911],
  [161.339527283766071, 67.640160826966172, 12.157953862848911],
  [159.649527283763751, 63.310160826891662, 12.157953862848911],
  [155.759527283749781, 64.880160826258362, 12.157953862848911]]
]

In the above case, the triangulation appears to deviate in the isEar function, around line 250, where in one case we have a value of t at -1.xxxe-13 and in the other at +1.xxxe-13 leading to different test results on (t >= 0).

Tested with version 1.4.0 of earcut.

[mourner]

Interesting! I'll take a look. Perhaps we should be less rigid in ear tests and compare things according to some Epsilon error value.

[ghost]

Ok, great, thanks for looking into this! An epsilon error value sounds like a good idea (I quickly tried this with the 't >= 0' test and it seems to work)... not sure if there is a big impact on performance though.

[mourner]

Wow, the original sample doesn't triangulate correctly for me...

[mourner]

Nevermind, it was a regressed viz page not working correctly... So, epsilon in that particular test seems to help with this example but breaks tests for other shapes. So looks like it'll be pretty tricky to solve...

[ghost]

ah, sorry to hear that... is there a way of easily/rapidly detecting if triangulation fails and returning an error code in this case? I could fallback to a slower triangulation library in this case... Thanks again for your help!

[mourner]

@sctf4 check out how it's done the tests... Basically I'm calculating sum of triangle areas and comparing it to the area of the original polygon. If it doesn't match within a tolerance — it's broken.

[ghost]

@mourner ok, I just wonder if there is a large performance cost with calculating the areas after each triangulation... I'll run some tests. I was wondering if the 'last resort' pass == 2/splitEarcut fails then would it be possible to return an error code (or empty triangles array) ?

[mourner]

@sctf4 actually I just figured out that it fails because of the cureLocalIntersections routine; if we disable that and go straight to splitEarcut, it works!

[ghost]

great!

[mourner]

BTW just wondering, where are you using the library?

[mourner]

OK seems to be fixed, without much of a perf hit. Added your test case so that it doesn't regress in future. Let me know if you find any other failing cases.

[ghost]

Currently testing it at F4: http://demo.f4map.com/ - mainly for OSM building triangulation. Tests here show that we get a good 20% to 30% speed increase over other libraries. If the triangulation works well we'd like to use it and add you to the credits list - if that's ok with you.

[mourner]

Awesome! F4 is such an amazing map. Bummer that it's only 20-30% though, I'd expect a bigger difference. :) Or is it overall processing speed, not just triangulation?

[ghost]

Great - thanks for the rapid bug fix! :)

Sorry, yes, the 20%-30% speed increase is an overall processing speedup!

[ghost]

The bug fix seems to work great for the buildings - they all seem to triangulate correctly - thanks!

I have another case however which unfortunately doesn't work, but it is quite an extreme case: a 'relatively' small hole in a very large bounding box. The data is as follows:
[[
[-20037508.34,19971868.877628453,0],
[-20037508.34,-19971868.877628453,0],
[20037508.34,-19971868.877628453,0],
[20037508.34,19971868.877628453,0]
],
[
[537637.6007702783,5907542.234420554,0],
[539500.1483225027,5905165.501947839,0],
[538610.3146341922,5905217.430281373,0],
[538040.6306361248,5906132.0755739985,0],
[538068.958329954,5906571.138846622,0],
[537711.0379352621,5906645.06648362,0],
[537629.886026485,5907533.69114742,0]
]]

This passes the tests in earcut because the area of the hole is so small compared to the size of the bounding zone, but only 6 triangles are produced. I'm working on a work-around to this on the application side but if you get a chance to look at it too and manage to handle these extreme cases that would be great!

[mourner]

I'll look at it, thanks!

[mourner]

@sctf4 fixed! Committing a patch now.