<p><a href="https://github.com/tomilov/sweepline/commit/ed730b9b34a9c8dfabbb89bf33ecd554ed78aa98#diff-5fd4f98b93359557447770c52fd3d651" rel="nofollow noreferrer">This commit</a> contains the fix of the bug.</p>

<p>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.</p>

CC BY-SA 3.0
2016-11-07T15:44:53.687Z
2016-11-07T15:54:20.837Z
2016-11-07T15:54:20.837Z
Tomilov Anatoliy
<p>I am in the middle of a process of implementation of Fortune's algorithm for a Voronoi diagram generating on a plane. <a href="https://github.com/tomilov/sweepline/blob/develop/sweepline.hpp" rel="nofollow noreferrer">Here</a> the last C++ debug version. Very rarely I catch (visually) such a bugs:</p>

<p><a href="https://i.sstatic.net/Q3f2j.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Q3f2j.png" alt="bug"></a></p>

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

<p>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.</p>

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

CC BY-SA 3.0
2016-11-06T08:51:54.730Z
Maybe there are another stackexhange places, where this question would be more appropriate to ask?
Tomilov Anatoliy
CC BY-SA 3.0
2016-11-06T10:39:58.827Z
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
CC BY-SA 3.0
2016-11-07T02:04:36.943Z
@DanielMGessel Yes.
Tomilov Anatoliy
CC BY-SA 3.0
2016-11-07T10:00:09.693Z
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
<computational-geometry><debugging>
Subtle bugs in Fortune's algorithm implementation
Tomilov Anatoliy
# Subtle bugs in Fortune's algorithm implementation

(Asked by: username_0 on 2016-11-06)

I am in the middle of a process of implementation of Fortune's algorithm for a Voronoi diagram generating on a plane. [Here](https://github.com/username_0/sweepline/blob/develop/sweepline.hpp) the last C++ debug version. Very rarely I catch (visually) such a bugs:

[![bug](https://i.sstatic.net/Q3f2j.png)](https://i.sstatic.net/Q3f2j.png)

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?

**Tags:** computational-geometry, debugging

> **Comments:**
> **username_0**: Maybe there are another stackexhange places, where this question would be more appropriate to ask?  
> **username_1**: 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.  
> **username_0**: @DanielMGessel Yes.  
> **username_2**: 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.  

---

## 1 answers

### Answer by username_0 on 2016-11-07. Score: 2

[This commit](https://github.com/username_0/sweepline/commit/ed730b9b34a9c8dfabbb89bf33ecd554ed78aa98#diff-5fd4f98b93359557447770c52fd3d651) 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.


---

