CDT: A case that failed in triangulation

I encountered some failed cases that said “Duplicate vertex detected: # is a duplicate of #”. After checking it, I found it’s because of the triangulation at the last iteration in my codes. There is a simple example below. It’s kind of like #166. I don’t know the reason, is it a bug or due to invalid points?

The vertices are

    0      0.000010000000      0.000010000000
    1      1.000000000000      0.000000000000
    2      0.999990000000      0.099990000000
    3      0.000000000000      0.100000000000
    4      0.500005000000      0.000005000000
    5      0.500000000000      0.050000000000
    6      0.499995000000      0.099995000000

The generated triangles are

    5    0    4
    0    5    3
    5    2    6
    2    3    6
    3    5    6
    2    5    1
    4    1    5

The triangle (2, 3, 6) is the red line, a flat triangle.

About this issue

Original URL
State: closed
Created 3 months ago
Comments: 20 (13 by maintainers)

Most upvoted comments

For the (2, 3, 6) case both predicates agree that points are collinear with O3. My guess is that if Ofast flag is removed, the triangulation will not contain flat triangles.

artem-ogre on Apr 2, 2024

you mean to print the double value with full precision?

fmt::print("({:d}, {:d}, {:d}): {}\n", v[0], v[1], v[2], v1);

output:

(6, 4, 7): 2.168404344971009e-19
(6, 7, 4): -2.168404344971009e-19
(7, 4, 6): -2.168404344971009e-19
another predicates: 2.168404344971009e-19
another predicates: -2.168404344971009e-19
another predicates: -2.168404344971009e-19
(1, 2, 3): -8.673617379884035e-19
(1, 3, 2): 4.336808689942018e-19
(3, 2, 1): 0
another predicates: -4.336808689942018e-19
another predicates: 4.336808689942018e-19
another predicates: 4.336808689942018e-19

pan3rock on Mar 29, 2024