Artifacts on degenerate input

[dy]

Take circumference points:

[[4,1],[3.7974166882130675,2.0837249985614585],[3.2170267516619773,3.0210869309396715],[2.337215067329615,3.685489874065187],[1.276805078389906,3.9872025288851036],[0.17901102978375127,3.885476929518457],[-0.8079039091377689,3.3940516818407187],[-1.550651407188842,2.5792964886320684],[-1.9489192990517052,1.5512485534497125],[-1.9489192990517057,0.44875144655029087],[-1.5506514071888438,-0.5792964886320653],[-0.8079039091377715,-1.394051681840717],[0.17901102978374794,-1.8854769295184561],[1.276805078389902,-1.987202528885104],[2.337215067329611,-1.6854898740651891],[3.217026751661974,-1.021086930939675],[3.7974166882130653,-0.08372499856146409]]

With delaunay-triangulate we get hull:

Vertices:

[2,1,0,16,15,0,15,2,0,3,2,15,14,13,15,4,3,5,5,3,15,13,12,15,6,5,7,7,5,15,12,10,15,11,10,12,9,8,7,9,7,15,10,9,15]

With delanuator we get broken image:

Vertices:

[15,2,1,2,5,1,5,15,1,0,16,1,5,3,2,9,5,2,15,9,2,15,12,9,5,4,3,15,14,12,9,8,6,12,10,9,8,7,6,14,13,12,12,11,10]

Is that expected behavior? (for me no)

[mourner]

Not expected, probably a bug that manifests on data with points uniformly placed on a circle.

[redblobgames]

Interesting bug. Something about symmetry? Changing the first 3.7974166882130675 to 3.79741668821306 makes it work again. (I made a page)

[mourner]

Likely floating point robustness issues. I'll investigate what's going on this week.

[redblobgames]

@mourner thanks for that link — the naiveLeftRight function there is something I've done in my own code and it also looks like the area function in delaunator

[mourner]

@redblobgames I believe the numeric issues are related to the inCircle test, since there are 3 points on a straight line for area to have an issue in this particular case.

[mourner]

I believe there's nothing we can do on Delaunator side for cases like this — small floating point numbers like this will introduce numerical instability. If I round the example above to 14 digits after the decimal point, it works correctly:

points = points.map(function (p) {
    var m = 1e14;
    return [Math.round(p[0] * m) / m, Math.round(p[1] * m) / m];
})

[dy]

Ok, just to let know: it is not a single case, it is at least a family of cases with symmetrical points on circumference, number of points can be any.

[mourner]

Reopening because I found the root cause of this bug, and it’s surprisingly not about floating point error. It’s a bug in the algorithm with a very simple fix. I’ll submit it after writing a better test tomorrow.