5

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:

bug

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?

Pikalek
  • 377
  • 1
  • 13
Tomilov Anatoliy
  • 241
  • 1
  • 8
  • Maybe there are another stackexhange places, where this question would be more appropriate to ask? – Tomilov Anatoliy Nov 06 '16 at 08: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. – trichoplax is on Codidact now Nov 06 '16 at 10:39
  • Are you using floating point numbers? –  Nov 07 '16 at 01:00
  • @DanielMGessel Yes. – Tomilov Anatoliy Nov 07 '16 at 02: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 07 '16 at 06:18
  • Just adding to @DanielMGessel 's comment, many years ago I wrote a general polygon triangulation algorithm (i.e. it handled self-intersections) and until I replaced the float representations with exact rational maths it was a nightmare trying to track down/fix bugs. – Simon F Nov 07 '16 at 10:00

1 Answers1

2

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.

Tomilov Anatoliy
  • 241
  • 1
  • 8