Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Infinite loop with some input coordinates #16

Open
jcelerier opened this issue Apr 19, 2019 · 6 comments · May be fixed by #32
Open

Infinite loop with some input coordinates #16

jcelerier opened this issue Apr 19, 2019 · 6 comments · May be fixed by #32

Comments

@jcelerier
Copy link 

#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
Copy link
Author

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

@mourner
Copy link
Contributor

mourner commented Jun 19, 2019

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

soerendd pushed a commit to soerendd/delaunator-cpp that referenced this issue Aug 5, 2019
@soerenmuehlbauer
Backport from delaunator-js for
f55ced6 
mapbox/delaunator#44
mapbox/delaunator#33

solves

delfrrr#11
delfrrr#16
@soerendd soerendd mentioned this issue Aug 5, 2019
Open
@prapin
Copy link

prapin commented Sep 24, 2019

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 added a commit to esilvia/delaunator-cpp that referenced this issue Nov 4, 2020
@esilvia
Fixed issue-16
c928fc1 
Fixes delfrrr#16 to prevent infinite recursion when a triangle was previously deleted from hull_next.

Port of fix in original JavaScript mapbox/delaunator#44
@esilvia esilvia linked a pull request Nov 4, 2020 that will close this issue
Open
@esilvia
Copy link

esilvia commented Nov 4, 2020

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
Copy link

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

@mourner
Copy link
Contributor

mourner commented Oct 14, 2021

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Fixed issue-16 esilvia/delaunator-cpp
5 participants
@mourner @prapin @jcelerier @miloszmaki @esilvia