# Subtle bugs in Fortune's algorithm implementation

I am in the middle of a process of implementation of Fortune's algorithm for a Voronoi diagram generating on a plane. Here the last C++ debug version. Very rarely I catch (visually) such a bugs:

Debugging process of a geometrical algorithms considered very complex by me. I even don't know which runtime checks (assert-ions) should I add to catch this bugs on the fly.

The question is addressed to those who have tried to implement Fortune's algorithm. I sure, if one faced similar bugs in his implementation somewhere in the middle of a way, then one may remember how to avoid it.

What is the source of the bug? What is the main corner cases (except rectangle mesh, concentric points, etc) can I face?

• Maybe there are another stackexhange places, where this question would be more appropriate to ask? Nov 6 '16 at 8:51
• This is on topic here. The only thing I would suggest is explaining what you have already tried, and your current understanding of why this is incorrect. Sometimes describing what is wrong can give a clue about what is causing it. Describing what you have already tried is required on any Stack Exchange site though - it isn't a reason to move the question. Nov 6 '16 at 10:39
• Are you using floating point numbers? Nov 7 '16 at 1:00
• @DanielMGessel Yes. Nov 7 '16 at 2:04
• If switching from 32 bit floats to 64 bit floats makes the errors rarer, that's an strong indication that you're running into rounding problems - I haven't done much computational geometry in a while, but my recollection was that exact results were often critical. Nov 7 '16 at 6:18