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?

  • $\begingroup$ Maybe there are another stackexhange places, where this question would be more appropriate to ask? $\endgroup$ Nov 6 '16 at 8:51
  • $\begingroup$ 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. $\endgroup$
    – trichoplax
    Nov 6 '16 at 10:39
  • $\begingroup$ Are you using floating point numbers? $\endgroup$ Nov 7 '16 at 1:00
  • $\begingroup$ @DanielMGessel Yes. $\endgroup$ Nov 7 '16 at 2:04
  • $\begingroup$ 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. $\endgroup$ Nov 7 '16 at 6:18

This commit contains the fix of the bug.

In short, it is wrong to disable event for second edge, during event checking, when first edge may be truncated sooner then stated by its current associated event.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.