search

artem-ogre / CDT

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

Wrong super-triangle calculated for tiny bounding box #174

Closed artem-ogre closed 5 months ago

artem-ogre commented 5 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