Strange issue triangulating certain polygons

[dhowe]

I'm comparing some of the different triangulation libraries on opentype fonts, and have run into a strange issue with earcut that I can't solve. See the image below:

As you can see, the upper hole for the percent-sign is not correct with earcut.

[dhowe]

More perplexing still, this only seems to happen after I've first rendered the p-character, as you can see below:

[dhowe]

The data being input to the three libraries (correct and incorrect) are here:

earcut([272.65000055654116, 123.90565782485673, 273.43186418809927, 130.50881049432792, 275.7524724871386, 136.7323496252764, 279.4944249790162, 142.23839184455574, 284.43238831004714, 146.7004567309341, 290.28296075442927, 149.86217257360113, 296.7046091845317, 151.53918036725955, 303.3653444646393, 151.6608259321656, 309.8579660705465, 150.219733984099, 315.8176358256489, 147.27806596420706, 320.91884044628245, 142.99822680730722, 324.85628113771673, 137.64108043884045, 327.40631344406864, 131.51111824424007, 328.431264241552, 124.93641692795792, 327.8935170979705, 118.30797780468129, 325.8057433114911, 111.99641607865343, 322.2643188096525, 106.3465177990438, 317.5112865351897, 101.71999395124732, 311.77834375849926, 98.33761266223155, 305.413434644416, 96.41928467340767, 298.764883596755, 96.05572864010246, 292.21757991796477, 97.25715342277545, 286.15449861431847, 99.97523169373744, 280.9099566441321, 104.0530848402239, 276.76721924245356, 109.27100020945072, 273.9912200155202, 115.30178454495035, 272.72451470680534, 121.8368895214051, 314.0499989271819, 123.90549289577612, 312.4584948063829, 130.3005772112869, 308.0161185257137, 135.17358751371503, 301.77699953842676, 137.34595728587593, 295.25761859836064, 136.33733346881348, 289.9910646148026, 132.3485624022782, 287.2668820463121, 126.34290095195175, 287.6904494531452, 119.75019118711354, 291.17497291108594, 114.1536534355022, 296.91898931860925, 110.88651757836342, 303.5100271829404, 110.72041164720432, 309.40269737243653, 113.67713584899903, 313.1783829212189, 119.0856644153595], [27], 2); // returns 120 triangles  (correct)

earcut([200.95000055654114, 69.90565782485673, 201.73186418809928, 76.50881049432792, 204.05247248713854, 82.73234962527638, 207.79442497901618, 88.23839184455574, 212.7323883100471, 92.70045673093409, 218.58296075442922, 95.86217257360113, 225.00460918453172, 97.53918036725955, 231.66534446463922, 97.66082593216561, 238.15796607054654, 96.21973398409901, 244.1176358256489, 93.27806596420706, 249.2188404462824, 88.99822680730722, 253.15628113771672, 83.64108043884043, 255.70631344406866, 77.51111824424007, 256.73126424155197, 70.93641692795792, 256.19351709797047, 64.30797780468129, 254.1057433114911, 57.996416078653425, 250.56431880965246, 52.346517799043795, 245.8112865351897, 47.719993951247304, 240.07834375849924, 44.33761266223155, 233.71343464441597, 42.419284673407674, 227.06488359675492, 42.055728640102465, 220.51757991796475, 43.257153422775446, 214.45449861431845, 45.97523169373744, 209.20995664413203, 50.053084840223896, 205.06721924245355, 55.271000209450726, 202.29122001552022, 61.30178454495035, 201.02451470680535, 67.8368895214051, 242.34999892718187, 69.90549289577612, 240.7584948063828, 76.30057721128688, 236.31611852571368, 81.17358751371503, 230.07699953842675, 83.34595728587593, 223.55761859836056, 82.33733346881347, 218.2910646148026, 78.34856240227819, 215.5668820463121, 72.34290095195175, 215.9904494531453, 65.75019118711353, 219.47497291108593, 60.1536534355022, 225.2189893186092, 56.88651757836341, 231.8100271829404, 56.72041164720431, 237.70269737243652, 59.67713584899902, 241.47838292121884, 65.0856644153595], [27], 2); // returns 75 triangles (incorrect)

earcut([106.00000055654118, 69.90565782485673, 106.78186418809928, 76.50881049432792, 109.10247248713858, 82.73234962527638, 112.8444249790162, 88.23839184455574, 117.7823883100471, 92.70045673093409, 123.63296075442923, 95.86217257360113, 130.05460918453173, 97.53918036725955, 136.71534446463923, 97.66082593216561, 143.20796607054655, 96.21973398409901, 149.16763582564892, 93.27806596420706, 154.2688404462824, 88.99822680730722, 158.20628113771673, 83.64108043884043, 160.75631344406867, 77.51111824424007, 161.781264241552, 70.93641692795792, 161.24351709797048, 64.30797780468129, 159.1557433114911, 57.996416078653425, 155.61431880965247, 52.346517799043795, 150.86128653518972, 47.719993951247304, 145.12834375849926, 44.33761266223155, 138.76343464441598, 42.419284673407674, 132.11488359675496, 42.055728640102465, 125.56757991796476, 43.257153422775446, 119.50449861431844, 45.97523169373744, 114.25995664413203, 50.053084840223896, 110.11721924245357, 55.271000209450726, 107.34122001552024, 61.30178454495035, 106.07451470680535, 67.8368895214051, 147.39999892718188, 69.90549289577612, 145.80849480638284, 76.30057721128688, 141.3661185257137, 81.17358751371503, 135.12699953842676, 83.34595728587593, 128.6076185983606, 82.33733346881347, 123.3410646148026, 78.34856240227819, 120.6168820463121, 72.34290095195175, 121.04044945314527, 65.75019118711353, 124.52497291108594, 60.1536534355022, 130.26898931860924, 56.88651757836341, 136.8600271829404, 56.72041164720431, 142.75269737243653, 59.67713584899902, 146.52838292121888, 65.0856644153595], [27], 2); // returns 120 triangles  (correct)

[mourner]

OK seeing the issue, in the middle of debugging. Some weird race condition here.

[dhowe]

thanks

[mourner]

Should be fixed now! Published as 2.0.2. cc @kkaefer

[dhowe]

Great, thanks -- do you mind explaining what the issue was? I looked into it a bit without success...

[mourner]

Well, kinda hard to explain — the race condition was in the splitPolygon routine that splits the polygon into two parts if it can't find an ear to cut. In this particular case, it found a split diagonal which was invalid, cutting off the hole part of the ring instead of splitting the polygon into two.

[dhowe]

Thanks again for the quick fix...