Infinite loop with some input coordinates

[jcelerier]

#include <delaunator.hpp>

int main() {
    std::vector<double> coords = {
        0,
        0,
        1022,
        0,
        0,
        1024,
        1022,
        1024,
        387,
        403,
        387.4791259765625,
        403.1723327636719,
        388.0328369140625,
        403.0395812988281,
        388.6558227539063,
        402.6470947265625,
        389.3426818847656,
        402.0401611328125,
        390.0880126953125,
        401.2640380859375,
        390.886474609375,
        400.364013671875,
        391.732666015625,
        399.3855590820313,
        392.6212463378906,
        398.3738403320313,
        393.5468139648438,
        397.3742065429688,
        394.5039978027344,
        396.4319763183594,
        395.4874267578125,
        395.5924987792969,
        396.49169921875,
        394.9010620117188,
        397.511474609375,
        394.4029235839844,
        398.5413818359375,
        394.1434936523438,
        399.5759887695313,
        394.1680297851563,
        400.6099853515625,
        394.5217895507813,
        401.637939453125,
        395.2501525878906,
        402.6545104980469,
        396.3984680175781,
        403.6543273925781,
        398.0119323730469,
        404.6320190429688,
        400.135986328125,
        405.5821533203125,
        402.8158569335938,
        406.4994201660156,
        406.096923828125,
        407.3783569335938,
        410.0243835449219,
        408.2136840820313,
        414.6436462402344,
        409,
        420,
        409.5401611328125,
        426.6988525390625,
        409.6764526367188,
        435.189453125,
        409.4627380371094,
        445.2825622558594,
        408.95263671875,
        456.7891540527344,
        408.2000122070313,
        469.52001953125,
        407.2585754394531,
        483.2860717773438,
        406.1820678710938,
        497.8982543945313,
        405.0243225097656,
        513.1673583984375,
        403.8389892578125,
        528.9043579101563,
        402.6799926757813,
        544.9199829101563,
        401.6009521484375,
        561.0253295898438,
        400.6557006835938,
        577.031005859375,
        399.8979187011719,
        592.7481689453125,
        399.3814392089844,
        607.9874267578125,
        399.1600036621094,
        622.5599975585938,
        399.287353515625,
        636.2764892578125,
        399.8172912597656,
        648.9478759765625,
        400.8034973144531,
        660.385009765625,
        402.2998352050781,
        670.398681640625,
        404.3600158691406,
        678.7999267578125,
        407.0377502441406,
        685.399658203125,
        410.3868713378906,
        690.0086669921875,
        414.4611206054688,
        692.437744140625,
        419.3142700195313,
        692.4979248046875,
        425,
        690,
        431.9559326171875,
        684.6681518554688,
        440.4808349609375,
        676.5036010742188,
        450.4205932617188,
        665.7330932617188,
        461.6210327148438,
        652.5830078125,
        473.9280090332031,
        637.280029296875,
        487.1872863769531,
        620.050537109375,
        501.2446594238281,
        601.1212768554688,
        515.946044921875,
        580.71875,
        531.13720703125,
        559.0693969726563,
        546.6640014648438,
        536.4000244140625,
        562.3721923828125,
        512.9368896484375,
        578.1077270507813,
        488.9068603515625,
        593.71630859375,
        464.5363159179688,
        609.0437622070313,
        440.0518798828125,
        623.9359741210938,
        415.6799926757813,
        638.23876953125,
        391.6473388671875,
        651.7979736328125,
        368.1804809570313,
        664.4593505859375,
        345.5059204101563,
        676.0687255859375,
        323.8502502441406,
        686.471923828125,
        303.4400024414063,
        695.514892578125,
        284.5018005371094,
        703.0433959960938,
        267.2620544433594,
        708.9031982421875,
        251.9474792480469,
        712.9401245117188,
        238.7846374511719,
        715,
        228,
        715.1982421875,
        219.0757293701172,
        713.8192749023438,
        211.3032836914063,
        710.9628295898438,
        204.6234283447266,
        706.728515625,
        198.9767456054688,
        701.2160034179688,
        194.3040008544922,
        694.52490234375,
        190.5457916259766,
        686.7549438476563,
        187.642822265625,
        678.0057373046875,
        185.5357360839844,
        668.3768310546875,
        184.1652526855469,
        657.968017578125,
        183.4720001220703,
        646.87890625,
        183.3966674804688,
        635.2090454101563,
        183.8799438476563,
        623.05810546875,
        184.8624572753906,
        610.5260009765625,
        186.2849273681641,
        597.7119140625,
        188.0880126953125,
        584.7160034179688,
        190.2123565673828,
        571.637451171875,
        192.5986633300781,
        558.5762329101563,
        195.1875915527344,
        545.6318359375,
        197.9198150634766,
        532.9039916992188,
        200.7359924316406,
        520.4923095703125,
        203.5768127441406,
        508.4963989257813,
        206.3829650878906,
        497.0158996582031,
        209.0950927734375,
        486.1506042480469,
        211.6538848876953,
        476,
        214,
        466.0330810546875,
        216.533935546875,
        455.6854858398438,
        219.6620178222656,
        445.0069580078125,
        223.33349609375,
        434.0472717285156,
        227.4977416992188,
        422.8559875488281,
        232.10400390625,
        411.4830322265625,
        237.1016387939453,
        399.9779968261719,
        242.43994140625,
        388.3906860351563,
        248.0682067871094,
        376.7706909179688,
        253.9358215332031,
        365.16796875,
        259.9920043945313,
        353.6321105957031,
        266.1860961914063,
        342.2128295898438,
        272.4674682617188,
        330.9599609375,
        278.7853393554688,
        319.923095703125,
        285.0890808105469,
        309.1519775390625,
        291.3280029296875,
        298.6964721679688,
        297.4513854980469,
        288.6061401367188,
        303.4085693359375,
        278.9307861328125,
        309.1488647460938,
        269.7201843261719,
        314.62158203125,
        261.0240173339844,
        319.7760009765625,
        252.8919677734375,
        324.5614929199219,
        245.3738098144531,
        328.9273071289063,
        238.5192718505859,
        332.8228149414063,
        232.3781127929688,
        336.1972351074219,
        227,
        339
    };

    //triangulation happens here
    delaunator::Delaunator d(coords);
}

this gets stuck in delaunator::Delaunator::legalize(unsigned long).
Running with -fsanitize=integer yields some unsigned overflow, maybe that could be a cause ?

[jcelerier]

tested on both clang 8 and gcc 8, at -O0 as well as -O3

[mourner]

Could be related to mapbox/delaunator#44 which got fixed on the JS side.

[prapin]

I can confirm that infinite loops happen quite often in my automatic map process tool, that performs thousands and thousands of Delauney triangulations.
I applied above patch from soerendd (f55ced6), and now the library seem to be completely stable.

[esilvia]

Thanks for the tip @prapin . I just contributed PR for that patch if they want to integrate it to save someone some effort in the future.

[miloszmaki]

I confirm the fix works, please merge the PR by @esilvia

[mourner]

You might have more luck with https://github.com/abellgithub/delaunator-cpp, which is a more actively maintained port — this one seems to have been abandoned.