comparison: src/misc.cc
src/misc.cc
- changeset 596
- 43c233e91447
- parent 590
- 7aec744ce97b
- child 600
- 209e3f1f7b2c
equal
deleted
inserted
replaced
| 595:b6b39c1721a1 | 596:43c233e91447 |
|---|---|
| 26 #include "document.h" | 26 #include "document.h" |
| 27 #include "ui_rotpoint.h" | 27 #include "ui_rotpoint.h" |
| 28 #include "moc_misc.cpp" | 28 #include "moc_misc.cpp" |
| 29 | 29 |
| 30 #include "misc/documentPointer.cc" | 30 #include "misc/documentPointer.cc" |
| 31 | 31 #include "misc/ringFinder.cc" |
| 32 RingFinder g_RingFinder; | |
| 33 | 32 |
| 34 // Prime number table. | 33 // Prime number table. |
| 35 const int g_primes[NUM_PRIMES] = | 34 const int g_primes[NUM_PRIMES] = |
| 36 { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, | 35 { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, |
| 37 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, | 36 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, |
| 274 | 273 |
| 275 return list.join (delim); | 274 return list.join (delim); |
| 276 } | 275 } |
| 277 | 276 |
| 278 // ============================================================================= | 277 // ============================================================================= |
| 279 // This is the main algorithm of the ring finder. It tries to use math to find | |
| 280 // the one ring between r0 and r1. If it fails (the ring number is non-integral), | |
| 281 // it finds an intermediate radius (ceil of the ring number times scale) and | |
| 282 // splits the radius at this point, calling this function again to try find the | |
| 283 // rings between r0 - r and r - r1. | |
| 284 // | |
| 285 // This does not always yield into usable results. If at some point r == r0 or | |
| 286 // r == r1, there is no hope of finding the rings, at least with this algorithm, | |
| 287 // as it would fall into an infinite recursion. | |
| 288 // ----------------------------------------------------------------------------- | |
| 289 bool RingFinder::findRingsRecursor (double r0, double r1, Solution& currentSolution) | |
| 290 { // Don't recurse too deep. | |
| 291 if (m_stack >= 5) | |
| 292 return false; | |
| 293 | |
| 294 // Find the scale and number of a ring between r1 and r0. | |
| 295 assert (r1 >= r0); | |
| 296 double scale = r1 - r0; | |
| 297 double num = r0 / scale; | |
| 298 | |
| 299 // If the ring number is integral, we have found a fitting ring to r0 -> r1! | |
| 300 if (isInteger (num)) | |
| 301 { Component cmp; | |
| 302 cmp.scale = scale; | |
| 303 cmp.num = (int) round (num); | |
| 304 currentSolution.addComponent (cmp); | |
| 305 | |
| 306 // If we're still at the first recursion, this is the only | |
| 307 // ring and there's nothing left to do. Guess we found the winner. | |
| 308 if (m_stack == 0) | |
| 309 { m_solutions.push_back (currentSolution); | |
| 310 return true; | |
| 311 } | |
| 312 } | |
| 313 else | |
| 314 { // Try find solutions by splitting the ring in various positions. | |
| 315 if (isZero (r1 - r0)) | |
| 316 return false; | |
| 317 | |
| 318 double interval; | |
| 319 | |
| 320 // Determine interval. The smaller delta between radii, the more precise | |
| 321 // interval should be used. We can't really use a 0.5 increment when | |
| 322 // calculating rings to 10 -> 105... that would take ages to process! | |
| 323 if (r1 - r0 < 0.5) | |
| 324 interval = 0.1; | |
| 325 else if (r1 - r0 < 10) | |
| 326 interval = 0.5; | |
| 327 else if (r1 - r0 < 50) | |
| 328 interval = 1; | |
| 329 else | |
| 330 interval = 5; | |
| 331 | |
| 332 // Now go through possible splits and try find rings for both segments. | |
| 333 for (double r = r0 + interval; r < r1; r += interval) | |
| 334 { Solution sol = currentSolution; | |
| 335 | |
| 336 m_stack++; | |
| 337 bool res = findRingsRecursor (r0, r, sol) && findRingsRecursor (r, r1, sol); | |
| 338 m_stack--; | |
| 339 | |
| 340 if (res) | |
| 341 { // We succeeded in finding radii for this segment. If the stack is 0, this | |
| 342 // is the first recursion to this function. Thus there are no more ring segments | |
| 343 // to process and we can add the solution. | |
| 344 // | |
| 345 // If not, when this function ends, it will be called again with more arguments. | |
| 346 // Accept the solution to this segment by setting currentSolution to sol, and | |
| 347 // return true to continue processing. | |
| 348 if (m_stack == 0) | |
| 349 m_solutions.push_back (sol); | |
| 350 else | |
| 351 { currentSolution = sol; | |
| 352 return true; | |
| 353 } | |
| 354 } | |
| 355 } | |
| 356 | |
| 357 return false; | |
| 358 } | |
| 359 | |
| 360 return true; | |
| 361 } | |
| 362 | |
| 363 // ============================================================================= | |
| 364 // Main function. Call this with r0 and r1. If this returns true, use bestSolution | |
| 365 // for the solution that was presented. | |
| 366 // ----------------------------------------------------------------------------- | |
| 367 bool RingFinder::findRings (double r0, double r1) | |
| 368 { m_solutions.clear(); | |
| 369 Solution sol; | |
| 370 | |
| 371 // Recurse in and try find solutions. | |
| 372 findRingsRecursor (r0, r1, sol); | |
| 373 | |
| 374 // Compare the solutions and find the best one. The solution class has an operator> | |
| 375 // overload to compare two solutions. | |
| 376 m_bestSolution = null; | |
| 377 | |
| 378 for (QVector<Solution>::iterator solp = m_solutions.begin(); solp != m_solutions.end(); ++solp) | |
| 379 { const Solution& sol = *solp; | |
| 380 | |
| 381 if (m_bestSolution == null || sol > *m_bestSolution) | |
| 382 m_bestSolution = / | |
| 383 } | |
| 384 | |
| 385 return (m_bestSolution != null); | |
| 386 } | |
| 387 | |
| 388 // ============================================================================= | |
| 389 // ----------------------------------------------------------------------------- | |
| 390 bool RingFinder::Solution::operator> (const RingFinder::Solution& other) const | |
| 391 { // If this solution has less components than the other one, this one | |
| 392 // is definitely better. | |
| 393 if (getComponents().size() < other.getComponents().size()) | |
| 394 return true; | |
| 395 | |
| 396 // vice versa | |
| 397 if (other.getComponents().size() < getComponents().size()) | |
| 398 return false; | |
| 399 | |
| 400 // Calculate the maximum ring number. Since the solutions have equal | |
| 401 // ring counts, the solutions with lesser maximum rings should result | |
| 402 // in cleaner code and less new primitives, right? | |
| 403 int maxA = 0, | |
| 404 maxB = 0; | |
| 405 | |
| 406 for (int i = 0; i < getComponents().size(); ++i) | |
| 407 { if (getComponents()[i].num > maxA) | |
| 408 maxA = getComponents()[i].num; | |
| 409 | |
| 410 if (other.getComponents()[i].num > maxB) | |
| 411 maxB = other.getComponents()[i].num; | |
| 412 } | |
| 413 | |
| 414 if (maxA < maxB) | |
| 415 return true; | |
| 416 | |
| 417 if (maxB < maxA) | |
| 418 return false; | |
| 419 | |
| 420 // Solutions have equal rings and equal maximum ring numbers. Let's | |
| 421 // just say this one is better, at this point it does not matter which | |
| 422 // one is chosen. | |
| 423 return true; | |
| 424 } | |
| 425 | |
| 426 // ============================================================================= | |
| 427 // ----------------------------------------------------------------------------- | 278 // ----------------------------------------------------------------------------- |
| 428 void roundToDecimals (double& a, int decimals) | 279 void roundToDecimals (double& a, int decimals) |
| 429 { assert (decimals >= 0 && decimals < (signed) (sizeof g_e10 / sizeof *g_e10)); | 280 { assert (decimals >= 0 && decimals < (signed) (sizeof g_e10 / sizeof *g_e10)); |
| 430 a = round (a * g_e10[decimals]) / g_e10[decimals]; | 281 a = round (a * g_e10[decimals]) / g_e10[decimals]; |
| 431 } | 282 } |
