comparison: src/ringFinder.cc
src/ringFinder.cc
- changeset 842
- e1c9010eb9e8
- parent 840
- d077dd19bf9a
- child 844
- 11587d419d2f
equal
deleted
inserted
replaced
| 841:1243abd47381 | 842:e1c9010eb9e8 |
|---|---|
| 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 "miscallenous.h" | |
| 21 | |
| 22 RingFinder g_RingFinder; | |
| 23 | |
| 24 RingFinder::RingFinder() {} | |
| 25 | |
| 26 // ============================================================================= | |
| 27 // | |
| 28 bool RingFinder::findRingsRecursor (double r0, double r1, Solution& currentSolution) | |
| 29 { | |
| 30 // Don't recurse too deep. | |
| 31 if (m_stack >= 5) | |
| 32 return false; | |
| 33 | |
| 34 // Find the scale and number of a ring between r1 and r0. | |
| 35 assert (r1 >= r0); | |
| 36 double scale = r1 - r0; | |
| 37 double num = r0 / scale; | |
| 38 | |
| 39 // If the ring number is integral, we have found a fitting ring to r0 -> r1! | |
| 40 if (isInteger (num)) | |
| 41 { | |
| 42 Component cmp; | |
| 43 cmp.scale = scale; | |
| 44 cmp.num = (int) round (num); | |
| 45 currentSolution.addComponent (cmp); | |
| 46 | |
| 47 // If we're still at the first recursion, this is the only | |
| 48 // ring and there's nothing left to do. Guess we found the winner. | |
| 49 if (m_stack == 0) | |
| 50 { | |
| 51 m_solutions.push_back (currentSolution); | |
| 52 return true; | |
| 53 } | |
| 54 } | |
| 55 else | |
| 56 { | |
| 57 // Try find solutions by splitting the ring in various positions. | |
| 58 if (isZero (r1 - r0)) | |
| 59 return false; | |
| 60 | |
| 61 double interval; | |
| 62 | |
| 63 // Determine interval. The smaller delta between radii, the more precise | |
| 64 // interval should be used. We can't really use a 0.5 increment when | |
| 65 // calculating rings to 10 -> 105... that would take ages to process! | |
| 66 if (r1 - r0 < 0.5) | |
| 67 interval = 0.1; | |
| 68 else if (r1 - r0 < 10) | |
| 69 interval = 0.5; | |
| 70 else if (r1 - r0 < 50) | |
| 71 interval = 1; | |
| 72 else | |
| 73 interval = 5; | |
| 74 | |
| 75 // Now go through possible splits and try find rings for both segments. | |
| 76 for (double r = r0 + interval; r < r1; r += interval) | |
| 77 { | |
| 78 Solution sol = currentSolution; | |
| 79 | |
| 80 m_stack++; | |
| 81 bool res = findRingsRecursor (r0, r, sol) and findRingsRecursor (r, r1, sol); | |
| 82 m_stack--; | |
| 83 | |
| 84 if (res) | |
| 85 { | |
| 86 // We succeeded in finding radii for this segment. If the stack is 0, this | |
| 87 // is the first recursion to this function. Thus there are no more ring segments | |
| 88 // to process and we can add the solution. | |
| 89 // | |
| 90 // If not, when this function ends, it will be called again with more arguments. | |
| 91 // Accept the solution to this segment by setting currentSolution to sol, and | |
| 92 // return true to continue processing. | |
| 93 if (m_stack == 0) | |
| 94 m_solutions.push_back (sol); | |
| 95 else | |
| 96 { | |
| 97 currentSolution = sol; | |
| 98 return true; | |
| 99 } | |
| 100 } | |
| 101 } | |
| 102 | |
| 103 return false; | |
| 104 } | |
| 105 | |
| 106 return true; | |
| 107 } | |
| 108 | |
| 109 // | |
| 110 // This is the main algorithm of the ring finder. It tries to use math | |
| 111 // to find the one ring between r0 and r1. If it fails (the ring number | |
| 112 // is non-integral), it finds an intermediate radius (ceil of the ring | |
| 113 // number times scale) and splits the radius at this point, calling this | |
| 114 // function again to try find the rings between r0 - r and r - r1. | |
| 115 // | |
| 116 // This does not always yield into usable results. If at some point r == | |
| 117 // r0 or r == r1, there is no hope of finding the rings, at least with | |
| 118 // this algorithm, as it would fall into an infinite recursion. | |
| 119 // | |
| 120 bool RingFinder::findRings (double r0, double r1) | |
| 121 { | |
| 122 m_solutions.clear(); | |
| 123 Solution sol; | |
| 124 | |
| 125 // If we're dealing with fractional radii, try upscale them into integral | |
| 126 // ones. This should yield in more reliable and more optimized results. | |
| 127 // For instance, using r0=1.5, r1=3.5 causes the algorithm to fail but | |
| 128 // r0=3, r1=7 (scaled up by 2) yields a 2-component solution. We can then | |
| 129 // downscale the radii back by dividing the scale fields of the solution | |
| 130 // components. | |
| 131 double scale = 1.0; | |
| 132 | |
| 133 if (not isZero (scale = r0 - floor (r0)) or not isZero (scale = r1 - floor (r1))) | |
| 134 { | |
| 135 double r0f = r0 / scale; | |
| 136 double r1f = r1 / scale; | |
| 137 | |
| 138 if (qFuzzyCompare (floor (r0f), r0f) and qFuzzyCompare (floor (r1f), r1f)) | |
| 139 { | |
| 140 r0 = r0f; | |
| 141 r1 = r1f; | |
| 142 } | |
| 143 } | |
| 144 else | |
| 145 { | |
| 146 scale = 1.0; | |
| 147 } | |
| 148 | |
| 149 // Recurse in and try find solutions. | |
| 150 findRingsRecursor (r0, r1, sol); | |
| 151 | |
| 152 // If we had upscaled our radii, downscale back now. | |
| 153 if (scale != 1.0) | |
| 154 { | |
| 155 for (Solution& sol : m_solutions) | |
| 156 sol.scaleComponents (scale); | |
| 157 } | |
| 158 | |
| 159 // Compare the solutions and find the best one. The solution class has an operator> | |
| 160 // overload to compare two solutions. | |
| 161 m_bestSolution = null; | |
| 162 | |
| 163 for (Solution const& sol : m_solutions) | |
| 164 { | |
| 165 if (m_bestSolution == null or sol.isSuperiorTo (m_bestSolution)) | |
| 166 m_bestSolution = / | |
| 167 } | |
| 168 | |
| 169 return (m_bestSolution != null); | |
| 170 } | |
| 171 | |
| 172 // | |
| 173 // Compares this solution with @other and determines which | |
| 174 // one is superior. | |
| 175 // | |
| 176 // A solution is considered superior if solution has less | |
| 177 // components than the other one. If both solution have an | |
| 178 // equal amount components, the solution with a lesser maximum | |
| 179 // ring number is found superior, as such solutions should | |
| 180 // yield less new primitives and cleaner definitions. | |
| 181 // | |
| 182 // The solution which is found superior to every other solution | |
| 183 // will be the one returned by RingFinder::bestSolution(). | |
| 184 // | |
| 185 bool RingFinder::Solution::isSuperiorTo (const Solution* other) const | |
| 186 { | |
| 187 // If one solution has less components than the other one, it is definitely | |
| 188 // better. | |
| 189 if (getComponents().size() != other->getComponents().size()) | |
| 190 return getComponents().size() < other->getComponents().size(); | |
| 191 | |
| 192 // Calculate the maximum ring number. Since the solutions have equal | |
| 193 // ring counts, the solutions with lesser maximum rings should result | |
| 194 // in cleaner code and less new primitives, right? | |
| 195 int maxA = 0, | |
| 196 maxB = 0; | |
| 197 | |
| 198 for (int i = 0; i < getComponents().size(); ++i) | |
| 199 { | |
| 200 maxA = max (getComponents()[i].num, maxA); | |
| 201 maxB = max (other->getComponents()[i].num, maxB); | |
| 202 } | |
| 203 | |
| 204 if (maxA != maxB) | |
| 205 return maxA < maxB; | |
| 206 | |
| 207 // Solutions have equal rings and equal maximum ring numbers. Let's | |
| 208 // just say this one is better, at this point it does not matter which | |
| 209 // one is chosen. | |
| 210 return true; | |
| 211 } | |
| 212 | |
| 213 void RingFinder::Solution::scaleComponents (double scale) | |
| 214 { | |
| 215 for (Component& cmp : m_components) | |
| 216 cmp.scale *= scale; | |
| 217 } |
