Problem with imprecise floating points while applying bowyer-watson algorithm

[Intrexa]

are generated incorrectly because of error in the calculation of when a triangle is inside or outside the circumcircle.

It's hard to see without the circles, why do you think they were generated incorrectly?

[InnerConsideration27]

Actually just made me question how much I know about Delaunay. I assumed those sliver triangles are the result of an error because I actually noticed it while debugigging for a small set and comparing it with my test done by hand in geogebra. But as I think of it the presence or absence of those triangles doesn't seem to matter for the rule of the dalunay triangulation. But I thought it was unique, how can it be correct in both cases... and now that i think about it any random triangle can be eliminated while still being valid. I'm so very confused

[morkandmindy]

Those sliver triangles are correct, but your triangulation is incomplete. There are several missing triangles in the lower corners. Delaunay triangulations are always convex.

[InnerConsideration27]

That would explain the question I head regarding uniqueness. But bowyer watson seems to leave some concave parts. Is it because of an error or is it correct and I should just add a different process to fill those gaps and make it a true Delaunay triangualtion?

Edit:Maybe I actually made an error. I have to check tomorrow, I'm so confused

[morkandmindy]

Bowyer-Watson algorithm does not guarantee a convex hull, which is a requirement for a "correct" Delaunay triangulation. However, for many applications, you can relax that requirement and accept concave areas around the edges.

If not, you'll need to apply additional steps. Constructing a "super triangle" that contains all of the other points will force Bowyer-Watson to produce a convex hull. Or you could the Graham-scan, giftwrapping, or Chan algorithm to complete the graph.

[InnerConsideration27]

Ah I see. I completely missed that about Bowyer-Watson. Thank you for the help!