search

artem-ogre / CDT

Constrained Delaunay Triangulation (C++)
https://artem-ogre.github.io/CDT/
Mozilla Public License 2.0
1.09k stars 136 forks source link

conformToEdges Infinite loop #120

Closed cookielive closed 1 year ago

cookielive commented 1 year ago

Enter an infinite loop using conformaToEdges

27 32 -115711.398438 129619.171875 -115711.320312 129619.031250 -115711.281250 129618.976562 -115711.250000 129618.914062 -115725.527903 129610.414945 -115725.527903 129610.414945 -115725.748633 129610.283552 -115725.765625 129610.273438 -115725.984375 129610.140625 -115740.664062 129601.398438 -115774.648438 129581.164062 -115726.742188 129644.765625 -115696.226562 129593.867188 -115773.859375 129581.296875 -115774.039062 129581.265625 -115775.125000 129580.531250 -115822.007812 129518.289062 -115823.062500 129516.890625 -115823.398438 129517.453125 -115838.437500 129542.492188 -115838.476562 129542.546875 -115838.515625 129542.609375 -115838.593750 129542.742188 -115853.960938 129568.320312 -115775.609375 129580.585938 -115775.195312 129580.656250 -115775.015625 129580.679688 0 1 1 2 2 3 3 4 2 4 2 5 5 6 6 7 7 8 8 9 9 10 10 11 0 11 5 8 4 5 4 8 12 13 13 14 3 14 3 12 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 15 26

artem-ogre commented 1 year ago

Thank you for opening the issue @cookielive

Your input points have duplicates. Duplicates are not supported in CDT (see "Pre-conditions" in README.md). Duplicates can be detected with CDT::FindDuplicates and fixed with CDT::RemoveDuplicatesAndRemapEdges.

Please let me know if I overlooked something and the issue needs to be re-opened.

artem-ogre commented 1 year ago

By the way, thank you for providing the input in a form that was so easy to use. :)

cookielive commented 1 year ago

Points with index 4 and 5 are of double type, and the actual values are respectively

-115725.52790301839 129610.41494477216

-115725.52790301993 129610.41494477124

This is also the point that remains after using RemoveDuplicates. The constructor is CDT:: Triangulation\<double>cdt, but it enters an infinite loop. Perhaps RemoveDuplicates should filter this situation

Thank you for opening the issue @cookielive

Your input points have duplicates. Duplicates are not supported in CDT (see "Pre-conditions" in README.md). Duplicates can be detected with CDT::FindDuplicates and fixed with CDT::RemoveDuplicatesAndRemapEdges.

Please let me know if I overlooked something and the issue needs to be re-opened.

artem-ogre commented 1 year ago

RemoveDuplicatesAndRemapEdges fixed the original input you provided. If that's not the actual data you use, please provide exact input which uses double precision.

cookielive commented 1 year ago

Thank you for your reply. Let me check the accuracy of the original data again