Segmentation fault on VoronoiDiagram::intersect()

[reagentoo]

Hi. I'm constantly getting an sig segv on my set of point coordinates. I hope this info can be useful to fix:

FortuneAlgorithm f_alg(my_points);
f_alg.construct();
f_alg.bound(Box{-0.05, -0.05, 1.05, 1.05}); 
VoronoiDiagram dia = f_alg.getDiagram();
dia.intersect(Box{0.0, 0.0, 1.0, 1.0});

Number of points: 77 It looks like something going wrong with on FortuneAlgorithm constructor. Because I see some wrong lines... The window of sf::RenderWindow without intersect():

Points list:

POINT: x = 0.969796 y = 0.10606
POINT: x = 0.416667 y = 0.141313
POINT: x = 0.802083 y = 0.141313
POINT: x = 0.270833 y = 0.178243
POINT: x = 0.65625 y = 0.178243
POINT: x = 0.885262 y = 0.188622
POINT: x = 0.4875 y = 0.188622
POINT: x = 0.0736904 y = 0.188622
POINT: x = 0.34375 y = 0.22322
POINT: x = 0.729167 y = 0.22322
POINT: x = 0.864583 y = 0.800998
POINT: x = 0.475 y = 0.800998
POINT: x = 0.0531662 y = 0.800998
POINT: x = 0.40625 y = 0.832136
POINT: x = 0.791667 y = 0.832136
POINT: x = 0.374547 y = 0.101487
POINT: x = 0.614583 y = 0.114762
POINT: x = 0.208333 y = 0.114762
POINT: x = 0.59375 y = 0.209381
POINT: x = 0.5 y = 0.237059
POINT: x = 0.625 y = 0.250898
POINT: x = 0.770833 y = 0.264737
POINT: x = 0.905786 y = 0.278576
POINT: x = 0.0942141 y = 0.278576
POINT: x = 0.239583 y = 0.292415
POINT: x = 0.385417 y = 0.306254
POINT: x = 0.5 y = 0.320093
POINT: x = 0.625 y = 0.333932
POINT: x = 0.770833 y = 0.347771
POINT: x = 0.916048 y = 0.36161
POINT: x = 0.104476 y = 0.36161
POINT: x = 0.25 y = 0.375449
POINT: x = 0.395833 y = 0.389288
POINT: x = 0.5125 y = 0.403127
POINT: x = 0.635417 y = 0.416966
POINT: x = 0.78125 y = 0.430805
POINT: x = 0.92631 y = 0.444644
POINT: x = 0.114738 y = 0.444644
POINT: x = 0.260417 y = 0.458483
POINT: x = 0.302083 y = 0.472322
POINT: x = 0.475 y = 0.486161
POINT: x = 0.708333 y = 0.5
POINT: x = 0.886446 y = 0.513839
POINT: x = 0.0603875 y = 0.513839
POINT: x = 0.239583 y = 0.527678
POINT: x = 0.3125 y = 0.541517
POINT: x = 0.45625 y = 0.555356
POINT: x = 0.635417 y = 0.569195
POINT: x = 0.78125 y = 0.583034
POINT: x = 0.92631 y = 0.596873
POINT: x = 0.114738 y = 0.596873
POINT: x = 0.260417 y = 0.610712
POINT: x = 0.395833 y = 0.624551
POINT: x = 0.5125 y = 0.63839
POINT: x = 0.645833 y = 0.652229
POINT: x = 0.791667 y = 0.666068
POINT: x = 0.936572 y = 0.679907
POINT: x = 0.125 y = 0.679907
POINT: x = 0.270833 y = 0.693746
POINT: x = 0.583333 y = 0.707585
POINT: x = 0.525 y = 0.721424
POINT: x = 0.666667 y = 0.735263
POINT: x = 0.8125 y = 0.749102
POINT: x = 0.936572 y = 0.762941
POINT: x = 0.125 y = 0.762941
POINT: x = 0.25 y = 0.77678
POINT: x = 0.364583 y = 0.783699
POINT: x = 0.475 y = 0.790619
POINT: x = 0.4375 y = 0.845411
POINT: x = 0.697917 y = 0.858686
POINT: x = 0.75 y = 0.871962
POINT: x = 0.770833 y = 0.885237
POINT: x = 0.325683 y = 0.898456
POINT: x = 0.729299 y = 0.10181
POINT: x = 0.805475 y = 0.897183
POINT: x = 0.781905 y = 0.102429
POINT: x = 0.883552 y = 0.871962

[reagentoo]

Reduced point set:

26 points:

POINT: x = 0.969796 y = 0.10606
POINT: x = 0.25 y = 0.167864
POINT: x = 0.50625 y = 0.188622
POINT: x = 0.677083 y = 0.216301
POINT: x = 0.114738 y = 0.800998
POINT: x = 0.113598 y = 0.885237
POINT: x = 0.446875 y = 0.209381
POINT: x = 0.0326425 y = 0.250898
POINT: x = 0.48125 y = 0.292415
POINT: x = 0.905786 y = 0.333932
POINT: x = 0.416667 y = 0.36161
POINT: x = 0.84375 y = 0.403127
POINT: x = 0.34375 y = 0.430805
POINT: x = 0.666667 y = 0.472322
POINT: x = 0.333333 y = 0.5
POINT: x = 0.739583 y = 0.541517
POINT: x = 0.322917 y = 0.569195
POINT: x = 0.75 y = 0.610712
POINT: x = 0.25 y = 0.63839
POINT: x = 0.677083 y = 0.679907
POINT: x = 0.8125 y = 0.707585
POINT: x = 0.614583 y = 0.749102
POINT: x = 0.0839522 y = 0.77678
POINT: x = 0.534375 y = 0.845411
POINT: x = 0.666667 y = 0.885237
POINT: x = 0.733409 y = 0.898152

[reagentoo]

The minimal case is next:

POINT: x = 0.1 y = 0.8
POINT: x = 0.6 y = 0.8
POINT: x = 0.3 y = 0.4
COUNT: 3

[pvigier]

Hi,

As mentioned in the README, this is a toy project with a simple and understandable implementation of the Fortune Algorithm. I wrote another library which is much more robust especially with edge cases with aligned points which is available here: https://github.com/pvigier/MyGAL.

Best, Pierre