Infinite loop in Voronoi::closeCells

[eaterofpies]

I'm not entirely sure what caused the infinite loop. I just tried to create a 400x200 image with about 1000 random cells in it and it got stuck.

The infinite loop appears to happen when the cell nearly closes then for some reason expands to going round the corners of the full image so it never closes.

Looking at the code the equalsWithEpsilon etc functions don't actually use self::EPSILON they use 1e-9 instead.

replacing 1e-9 with self::EPSILON seems to prevent the infinite loop though I don't understand the code well enough to know if this is the correct fix for the issue.

[eaterofpies]

Set of points that caused the issue for me
179,73
269,129
203,126
374,135
372,4
103,90
268,141
358,187
141,40
90,41
192,124
83,34
164,190
264,137
304,2
373,177
39,172
113,113
249,53
186,162
252,11
115,160
310,183
146,20
193,196
275,91
188,149
16,116
164,16
124,108
335,19
318,5
249,49
157,164
2,57
247,13
76,46
183,95
298,123
209,162
155,125
369,12
378,114
387,185
389,25
286,155
15,3
49,126
293,107
16,84
214,181
50,87
120,47
101,123
366,81
213,53
156,114
285,143
121,159
71,187
379,4
70,134
384,182
323,151
147,24
13,197
334,129
169,172
285,28
2,7
140,162
348,70
151,13
130,92
8,131
241,158
5,177
101,198
79,44
177,166
365,195
58,142
233,36
156,49
337,1
214,155
54,148
154,159
351,45
363,57
76,132
116,44
190,91
232,44
255,45
68,129
264,196
250,87
395,85
9,168
159,100
247,40
308,50
163,92
1,150
243,76
176,1
331,116
106,66
128,175
2,123
84,123
270,192
120,20
268,106
224,129
28,76
131,132
292,158
169,193
248,121
208,181
70,98
398,79
66,46
322,36
57,34
361,126
145,28
10,76
225,120
350,152
41,101
394,102
289,168
105,176
267,194
31,191
305,144
81,66
367,29
259,194
396,185
277,158
305,93
110,93
118,148
99,2
50,65
387,42
95,58
312,57
255,26
237,146
144,183
288,74
194,120
2,77
98,160
393,9
124,79
57,192
76,152
62,92
10,21
135,179
314,160
38,163
103,113
396,130
298,94
360,198
345,3
363,179
260,4
373,180
128,180
367,178
166,102
23,37
214,196
396,34
133,115
164,147
267,4
42,169
104,58
41,196
91,19
121,32
195,49
199,45
4,52
331,197
42,79
197,147
336,124
364,47
272,141
33,162
290,73
58,26
378,63
229,15
24,181
95,88
2,171
117,71
176,146
165,142
307,100
44,162
156,17
14,39
95,105
181,23
205,148
173,176
169,131
285,130
268,164
218,63
321,21
394,15
108,165
344,89
119,88
393,127
334,117
391,15
164,149
22,93
265,180
135,149
108,4
301,38
145,128
152,26
151,190
147,166
224,44
346,122
167,128
134,172
185,45
235,65
385,180
254,159
172,11
316,35
275,142
286,131
103,111
228,173
365,96
327,54
237,57
377,115
147,83
85,69
226,15
370,74
379,173
165,156
181,47
237,35
21,151
78,20
382,71
189,132
38,139
306,173
185,77
85,95
139,159
47,115
226,42
146,39
147,198
142,156
306,98
326,105
234,75
272,137
393,153
391,174
315,101
263,43
4,197
267,190
313,31
115,102
115,117
222,50
124,52
348,75
257,34
295,88
169,71
88,147
2,120
30,184
233,196
104,30
354,163
366,73
233,42
382,78
289,183
363,179
171,99
115,184
78,7
312,165
335,120
247,46
9,58
165,82
30,3
56,137
7,8
229,181
279,165
86,182
121,91
358,117
308,60
187,169
250,68
320,12
396,128
320,11
240,69
26,45
94,179
226,44
375,83
49,124
172,70
247,64
175,173
389,37
162,91
34,52
252,136
257,4
51,146
118,87
191,158
126,92
99,160
215,132
351,37
44,130
271,197
190,42
138,108
218,192
184,46
24,140
366,188
101,124
198,105
30,43
309,187
236,64
67,10
356,57
265,50
253,116
67,99
122,131
99,21
214,110
354,121
303,41
369,101
245,130
251,187
85,130
26,132
325,90
88,82
375,173
104,151
110,12
60,131
172,135
246,28
301,27
209,105
1,128
15,49
92,47
6,89
64,31
37,156
388,123
363,147
152,165
324,25
63,104
376,94
298,107
125,188
148,180
108,48
284,126
157,177
38,13
301,23
55,192
360,132
185,56
246,63
312,195
86,14
168,152
93,119
35,47
137,136
258,176
328,90
167,62
322,144
3,124
280,137
280,88
340,126
227,115
237,10
186,68
357,76
39,38
279,144
199,23
140,52
179,143
98,40
24,55
270,46
206,15
227,149
166,121
360,36
224,39
337,103
126,150
92,133
49,164
60,116
253,163
283,100
208,153
298,64
48,185
188,38
369,78
65,84
162,169
204,86
228,122
259,46
45,161
121,186
364,135
61,28
307,107
139,53
102,197
184,112
53,148
252,13
211,196
38,120
44,111
366,198
372,181
237,173
201,117
68,58
261,67
301,156
390,28
223,17
26,12
32,70
164,69
29,133
368,123
81,196
395,87
358,90
266,107
380,108
198,114
91,191
18,123
311,168
255,28
218,76
22,189
155,174
178,123
263,69
380,84
56,90
198,134
153,30
345,13
10,136
394,126
126,80
54,146
8,97
154,190
193,147
73,139
350,46
216,4
232,138
342,146
352,10
261,177
24,69
75,98
249,171
279,22
248,38
260,134
377,161
261,141
139,86
226,125
206,109
211,79
35,115
104,73
5,59
386,124
370,62
281,31
114,98
134,64
349,170
271,188
12,45
289,23
166,31
19,18
228,18
197,134
306,29
271,191
206,109
68,185
339,163
376,163
306,30
9,116
117,67
192,126
397,41
48,88
146,29
396,97
207,177
244,10
329,106
149,27
244,21
248,92
221,64
1,56
393,8
35,86
253,2
57,54
304,167
68,71
96,86
232,53
185,3

[Innominandum]

I had this before as well, and it was because of the Lloyd Relaxation that I did, which rearranges the points a bit. The calculation that did that ended up using decimals instead of integers for the points, which ended up causing the same problems. If you are doing a similar thing, make sure that the coordinates of the points are both integer numbers when they enter the voronoi calculation.

[sroze]

Well, I'll try it this afternoon and come back to you in few hours!

[sroze]

@eaterofpies You're right, using self::EPSILON each case and replacing with 1e-9 make it working. Fixed in 7bfdbdf. I also added a PHPUnit test for that issue in test/ directory.