search

sroze / PHP-Voronoi-algorithm

Steven Fortune's algorithm in PHP
31 stars 15 forks source link

Infinite loop in Voronoi::closeCells #4

Closed eaterofpies closed 11 years ago

eaterofpies commented 11 years ago

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 commented 11 years ago

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 commented 11 years ago

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 commented 11 years ago

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

sroze commented 11 years ago

@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.