Issue Details
The Triangulation_3 is wrong when the input points are on a hexagonal Bravais lattice. (Not only the hexagonal, this is only a showcase). The Triangulation_3 contains degenerate cells, but they are not detected as degenerate. It seems that the hexagonal symmetry of the Bravais lattice cannot be handled by Triangulation_3.
The example code identifies the the Voronoi cell containing the origin, and it counts the vertices and facets of this cell. It does so by iteration over the Delaunay Triangulation_3. Triangulation_3 leads to wrong counts:
It finds the count:
6 Voronoi facets (equiv. Delaunay edges) and
8 Voronoi vertices (equiv. Delaunay cells).
The right count would be:
8 Voronoi facets (equiv. Delaunay edges) and
12 Voronoi vertices (equiv. Delaunay cells).
The miscount even happens when using exact numbers with sqrt(3) extension.
There is even a second problem when using floating-point numbers (double): At runtime an assertion fails when calculating the circumcenter of a Delaunay cell (which is a Voronoi vertex point). This line in the source code causes the assertion to fail:
Point cc = circumcenter_constructor(p0, p1, p2, p3);
The runtime error message is:
terminate called after throwing an instance of 'CGAL::Assertion_exception'
what(): CGAL ERROR: assertion violation!
Expr: ! CGAL_NTS is_zero(den)
File: [...]/Cartesian_kernel/include/CGAL/constructions/kernel_ftC3.h
Line: 552
Notice that the same code gives the right answer and works with exact and with inexact numbers when using the regular triangulation instead.
Source Code
facecentredcubic_exact.cpp
facecentredcubic_inexact.cpp
hexagonal_exact.cpp
hexagonal_inexact.cpp
Example files:
facecentredcubic_exact --> runs and gives the right result
facecentredcubic_inexact --> runs and gives the right result
hexagonal_exact --> runs but gives a wrong result
hexagonal_inexact --> does not run
Environment
- Operating system: Linux 64 bits
- Compiler: c++ (Debian 14.2.0-19) 14.2.0
- Release or debug mode: Debug mode
- Specific flags used (if any):
- CGAL version: 6.2 from git, HEAD is at 21c5343
- Boost version: (n/a)
- Other libraries versions if used (Eigen, TBB, etc.): (n/a)
Issue Details
The Triangulation_3 is wrong when the input points are on a hexagonal Bravais lattice. (Not only the hexagonal, this is only a showcase). The Triangulation_3 contains degenerate cells, but they are not detected as degenerate. It seems that the hexagonal symmetry of the Bravais lattice cannot be handled by Triangulation_3.
The example code identifies the the Voronoi cell containing the origin, and it counts the vertices and facets of this cell. It does so by iteration over the Delaunay Triangulation_3. Triangulation_3 leads to wrong counts:
It finds the count:
6 Voronoi facets (equiv. Delaunay edges) and
8 Voronoi vertices (equiv. Delaunay cells).
The right count would be:
8 Voronoi facets (equiv. Delaunay edges) and
12 Voronoi vertices (equiv. Delaunay cells).
The miscount even happens when using exact numbers with sqrt(3) extension.
There is even a second problem when using floating-point numbers (double): At runtime an assertion fails when calculating the circumcenter of a Delaunay cell (which is a Voronoi vertex point). This line in the source code causes the assertion to fail:
Point cc = circumcenter_constructor(p0, p1, p2, p3);
The runtime error message is:
terminate called after throwing an instance of 'CGAL::Assertion_exception'
what(): CGAL ERROR: assertion violation!
Expr: ! CGAL_NTS is_zero(den)
File: [...]/Cartesian_kernel/include/CGAL/constructions/kernel_ftC3.h
Line: 552
Notice that the same code gives the right answer and works with exact and with inexact numbers when using the regular triangulation instead.
Source Code
facecentredcubic_exact.cpp
facecentredcubic_inexact.cpp
hexagonal_exact.cpp
hexagonal_inexact.cpp
Example files:
facecentredcubic_exact --> runs and gives the right result
facecentredcubic_inexact --> runs and gives the right result
hexagonal_exact --> runs but gives a wrong result
hexagonal_inexact --> does not run
Environment