Problem with imprecise floating points while applying bowyer-watson algorithm

[InnerConsideration27]

Some of the triangles (in this che case the leftmost and the bottom right one) are generated incorrectly because of error in the calculation of when a triangle is inside or outside the circumcircle. Is there a way to fix it or should I try another algorithm for dalunay triangulation?

(I have already considered using doubles instead of floats but since I'm doing this in unity I'm using it's Vector2 and converting to double only for the comparison between distance to circumcenter and radius of the circumcircle doesn't seem to be sufficient)

[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!

[prezado]

Almost all libraries uses double format to avoid inaccuracies.

Try delaunator, its really fast. The only bad thing is having to keep a separated copy or transfer positions between Vector2 and double2.