artem-ogre / CDT

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

Fix supertriangle calculation for tiny bounding boxes #175

Closed artem-ogre closed 6 months ago

artem-ogre commented 6 months ago

Input to reproduce the issue (txt-file):

3 3
45802.2779561576462583616375923 169208.540894783218391239643097
45802.2779561576317064464092255 169208.540894783218391239643097
45802.2779561576462583616375923 169208.540894783247495070099831
0 1
1 2
0 2

Because of the rounding errors when calculating super-triangle vertex positions the resulting super-triangle does not contain all the vertices. As the result triangulation fails at inserting vertices with the exception:

terminate called after throwing an instance of 'std::runtime_error'
  what():  No triangle was found at position

Make sure radius is big enough.