comparison: src/misc/ringFinder.cc
src/misc/ringFinder.cc
- changeset 667
- 31540c1f22ea
- parent 604
- 01bdac75994a
equal
deleted
inserted
replaced
| 666:c595cfb4791c | 667:31540c1f22ea |
|---|---|
| 1 /* | |
| 2 * LDForge: LDraw parts authoring CAD | |
| 3 * Copyright (C) 2013, 2014 Santeri Piippo | |
| 4 * | |
| 5 * This program is free software: you can redistribute it and/or modify | |
| 6 * it under the terms of the GNU General Public License as published by | |
| 7 * the Free Software Foundation, either version 3 of the License, or | |
| 8 * (at your option) any later version. | |
| 9 * | |
| 10 * This program is distributed in the hope that it will be useful, | |
| 11 * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
| 12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
| 13 * GNU General Public License for more details. | |
| 14 * | |
| 15 * You should have received a copy of the GNU General Public License | |
| 16 * along with this program. If not, see <http://www.gnu.org/licenses/>. | |
| 17 */ | |
| 18 | |
| 19 #include "ringFinder.h" | |
| 20 #include "../misc.h" | |
| 21 | |
| 22 RingFinder g_RingFinder; | |
| 23 | |
| 24 // ============================================================================= | |
| 25 // This is the main algorithm of the ring finder. It tries to use math to find | |
| 26 // the one ring between r0 and r1. If it fails (the ring number is non-integral), | |
| 27 // it finds an intermediate radius (ceil of the ring number times scale) and | |
| 28 // splits the radius at this point, calling this function again to try find the | |
| 29 // rings between r0 - r and r - r1. | |
| 30 // | |
| 31 // This does not always yield into usable results. If at some point r == r0 or | |
| 32 // r == r1, there is no hope of finding the rings, at least with this algorithm, | |
| 33 // as it would fall into an infinite recursion. | |
| 34 // ----------------------------------------------------------------------------- | |
| 35 bool RingFinder::findRingsRecursor (double r0, double r1, Solution& currentSolution) | |
| 36 { | |
| 37 // Don't recurse too deep. | |
| 38 if (m_stack >= 5) | |
| 39 return false; | |
| 40 | |
| 41 // Find the scale and number of a ring between r1 and r0. | |
| 42 assert (r1 >= r0); | |
| 43 double scale = r1 - r0; | |
| 44 double num = r0 / scale; | |
| 45 | |
| 46 // If the ring number is integral, we have found a fitting ring to r0 -> r1! | |
| 47 if (isInteger (num)) | |
| 48 { | |
| 49 Component cmp; | |
| 50 cmp.scale = scale; | |
| 51 cmp.num = (int) round (num); | |
| 52 currentSolution.addComponent (cmp); | |
| 53 | |
| 54 // If we're still at the first recursion, this is the only | |
| 55 // ring and there's nothing left to do. Guess we found the winner. | |
| 56 if (m_stack == 0) | |
| 57 { | |
| 58 m_solutions.push_back (currentSolution); | |
| 59 return true; | |
| 60 } | |
| 61 } | |
| 62 else | |
| 63 { | |
| 64 // Try find solutions by splitting the ring in various positions. | |
| 65 if (isZero (r1 - r0)) | |
| 66 return false; | |
| 67 | |
| 68 double interval; | |
| 69 | |
| 70 // Determine interval. The smaller delta between radii, the more precise | |
| 71 // interval should be used. We can't really use a 0.5 increment when | |
| 72 // calculating rings to 10 -> 105... that would take ages to process! | |
| 73 if (r1 - r0 < 0.5) | |
| 74 interval = 0.1; | |
| 75 else if (r1 - r0 < 10) | |
| 76 interval = 0.5; | |
| 77 else if (r1 - r0 < 50) | |
| 78 interval = 1; | |
| 79 else | |
| 80 interval = 5; | |
| 81 | |
| 82 // Now go through possible splits and try find rings for both segments. | |
| 83 for (double r = r0 + interval; r < r1; r += interval) | |
| 84 { | |
| 85 Solution sol = currentSolution; | |
| 86 | |
| 87 m_stack++; | |
| 88 bool res = findRingsRecursor (r0, r, sol) && findRingsRecursor (r, r1, sol); | |
| 89 m_stack--; | |
| 90 | |
| 91 if (res) | |
| 92 { | |
| 93 // We succeeded in finding radii for this segment. If the stack is 0, this | |
| 94 // is the first recursion to this function. Thus there are no more ring segments | |
| 95 // to process and we can add the solution. | |
| 96 // | |
| 97 // If not, when this function ends, it will be called again with more arguments. | |
| 98 // Accept the solution to this segment by setting currentSolution to sol, and | |
| 99 // return true to continue processing. | |
| 100 if (m_stack == 0) | |
| 101 m_solutions.push_back (sol); | |
| 102 else | |
| 103 { | |
| 104 currentSolution = sol; | |
| 105 return true; | |
| 106 } | |
| 107 } | |
| 108 } | |
| 109 | |
| 110 return false; | |
| 111 } | |
| 112 | |
| 113 return true; | |
| 114 } | |
| 115 | |
| 116 // ============================================================================= | |
| 117 // Main function. Call this with r0 and r1. If this returns true, use bestSolution | |
| 118 // for the solution that was presented. | |
| 119 // ----------------------------------------------------------------------------- | |
| 120 bool RingFinder::findRings (double r0, double r1) | |
| 121 { | |
| 122 m_solutions.clear(); | |
| 123 Solution sol; | |
| 124 | |
| 125 // Recurse in and try find solutions. | |
| 126 findRingsRecursor (r0, r1, sol); | |
| 127 | |
| 128 // Compare the solutions and find the best one. The solution class has an operator> | |
| 129 // overload to compare two solutions. | |
| 130 m_bestSolution = null; | |
| 131 | |
| 132 for (QVector<Solution>::iterator solp = m_solutions.begin(); solp != m_solutions.end(); ++solp) | |
| 133 { | |
| 134 const Solution& sol = *solp; | |
| 135 | |
| 136 if (m_bestSolution == null || sol.isBetterThan (m_bestSolution)) | |
| 137 m_bestSolution = / | |
| 138 } | |
| 139 | |
| 140 return (m_bestSolution != null); | |
| 141 } | |
| 142 | |
| 143 // ============================================================================= | |
| 144 // ----------------------------------------------------------------------------- | |
| 145 bool RingFinder::Solution::isBetterThan (const Solution* other) const | |
| 146 { | |
| 147 // If this solution has less components than the other one, this one | |
| 148 // is definitely better. | |
| 149 if (getComponents().size() < other->getComponents().size()) | |
| 150 return true; | |
| 151 | |
| 152 // vice versa | |
| 153 if (other->getComponents().size() < getComponents().size()) | |
| 154 return false; | |
| 155 | |
| 156 // Calculate the maximum ring number. Since the solutions have equal | |
| 157 // ring counts, the solutions with lesser maximum rings should result | |
| 158 // in cleaner code and less new primitives, right? | |
| 159 int maxA = 0, | |
| 160 maxB = 0; | |
| 161 | |
| 162 for (int i = 0; i < getComponents().size(); ++i) | |
| 163 { | |
| 164 maxA = max (getComponents()[i].num, maxA); | |
| 165 maxB = max (other->getComponents()[i].num, maxB); | |
| 166 } | |
| 167 | |
| 168 if (maxA < maxB) | |
| 169 return true; | |
| 170 | |
| 171 if (maxB < maxA) | |
| 172 return false; | |
| 173 | |
| 174 // Solutions have equal rings and equal maximum ring numbers. Let's | |
| 175 // just say this one is better, at this point it does not matter which | |
| 176 // one is chosen. | |
| 177 return true; | |
| 178 } |
