comparison: src/misc/ringFinder.cc
src/misc/ringFinder.cc
- changeset 655
- b376645315ab
- child 811
- 27ccc8eca322
equal
deleted
inserted
replaced
| 654:a74f2ff353b8 | 655:b376645315ab |
|---|---|
| 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 // ============================================================================= | |
| 25 // | |
| 26 bool RingFinder::findRingsRecursor (double r0, double r1, Solution& currentSolution) | |
| 27 { | |
| 28 // Don't recurse too deep. | |
| 29 if (m_stack >= 5) | |
| 30 return false; | |
| 31 | |
| 32 // Find the scale and number of a ring between r1 and r0. | |
| 33 assert (r1 >= r0); | |
| 34 double scale = r1 - r0; | |
| 35 double num = r0 / scale; | |
| 36 | |
| 37 // If the ring number is integral, we have found a fitting ring to r0 -> r1! | |
| 38 if (isInteger (num)) | |
| 39 { | |
| 40 Component cmp; | |
| 41 cmp.scale = scale; | |
| 42 cmp.num = (int) round (num); | |
| 43 currentSolution.addComponent (cmp); | |
| 44 | |
| 45 // If we're still at the first recursion, this is the only | |
| 46 // ring and there's nothing left to do. Guess we found the winner. | |
| 47 if (m_stack == 0) | |
| 48 { | |
| 49 m_solutions.push_back (currentSolution); | |
| 50 return true; | |
| 51 } | |
| 52 } | |
| 53 else | |
| 54 { | |
| 55 // Try find solutions by splitting the ring in various positions. | |
| 56 if (isZero (r1 - r0)) | |
| 57 return false; | |
| 58 | |
| 59 double interval; | |
| 60 | |
| 61 // Determine interval. The smaller delta between radii, the more precise | |
| 62 // interval should be used. We can't really use a 0.5 increment when | |
| 63 // calculating rings to 10 -> 105... that would take ages to process! | |
| 64 if (r1 - r0 < 0.5) | |
| 65 interval = 0.1; | |
| 66 else if (r1 - r0 < 10) | |
| 67 interval = 0.5; | |
| 68 else if (r1 - r0 < 50) | |
| 69 interval = 1; | |
| 70 else | |
| 71 interval = 5; | |
| 72 | |
| 73 // Now go through possible splits and try find rings for both segments. | |
| 74 for (double r = r0 + interval; r < r1; r += interval) | |
| 75 { | |
| 76 Solution sol = currentSolution; | |
| 77 | |
| 78 m_stack++; | |
| 79 bool res = findRingsRecursor (r0, r, sol) && findRingsRecursor (r, r1, sol); | |
| 80 m_stack--; | |
| 81 | |
| 82 if (res) | |
| 83 { | |
| 84 // We succeeded in finding radii for this segment. If the stack is 0, this | |
| 85 // is the first recursion to this function. Thus there are no more ring segments | |
| 86 // to process and we can add the solution. | |
| 87 // | |
| 88 // If not, when this function ends, it will be called again with more arguments. | |
| 89 // Accept the solution to this segment by setting currentSolution to sol, and | |
| 90 // return true to continue processing. | |
| 91 if (m_stack == 0) | |
| 92 m_solutions.push_back (sol); | |
| 93 else | |
| 94 { | |
| 95 currentSolution = sol; | |
| 96 return true; | |
| 97 } | |
| 98 } | |
| 99 } | |
| 100 | |
| 101 return false; | |
| 102 } | |
| 103 | |
| 104 return true; | |
| 105 } | |
| 106 | |
| 107 // ============================================================================= | |
| 108 // Main function. Call this with r0 and r1. If this returns true, use bestSolution | |
| 109 // for the solution that was presented. | |
| 110 // | |
| 111 bool RingFinder::findRings (double r0, double r1) | |
| 112 { | |
| 113 m_solutions.clear(); | |
| 114 Solution sol; | |
| 115 | |
| 116 // Recurse in and try find solutions. | |
| 117 findRingsRecursor (r0, r1, sol); | |
| 118 | |
| 119 // Compare the solutions and find the best one. The solution class has an operator> | |
| 120 // overload to compare two solutions. | |
| 121 m_bestSolution = null; | |
| 122 | |
| 123 for (QVector<Solution>::iterator solp = m_solutions.begin(); solp != m_solutions.end(); ++solp) | |
| 124 { | |
| 125 const Solution& sol = *solp; | |
| 126 | |
| 127 if (m_bestSolution == null || sol.isSuperiorTo (m_bestSolution)) | |
| 128 m_bestSolution = / | |
| 129 } | |
| 130 | |
| 131 return (m_bestSolution != null); | |
| 132 } | |
| 133 | |
| 134 // ============================================================================= | |
| 135 // | |
| 136 bool RingFinder::Solution::isSuperiorTo (const Solution* other) const | |
| 137 { | |
| 138 // If this solution has less components than the other one, this one | |
| 139 // is definitely better. | |
| 140 if (getComponents().size() < other->getComponents().size()) | |
| 141 return true; | |
| 142 | |
| 143 // vice versa | |
| 144 if (other->getComponents().size() < getComponents().size()) | |
| 145 return false; | |
| 146 | |
| 147 // Calculate the maximum ring number. Since the solutions have equal | |
| 148 // ring counts, the solutions with lesser maximum rings should result | |
| 149 // in cleaner code and less new primitives, right? | |
| 150 int maxA = 0, | |
| 151 maxB = 0; | |
| 152 | |
| 153 for (int i = 0; i < getComponents().size(); ++i) | |
| 154 { | |
| 155 maxA = max (getComponents()[i].num, maxA); | |
| 156 maxB = max (other->getComponents()[i].num, maxB); | |
| 157 } | |
| 158 | |
| 159 if (maxA < maxB) | |
| 160 return true; | |
| 161 | |
| 162 if (maxB < maxA) | |
| 163 return false; | |
| 164 | |
| 165 // Solutions have equal rings and equal maximum ring numbers. Let's | |
| 166 // just say this one is better, at this point it does not matter which | |
| 167 // one is chosen. | |
| 168 return true; | |
| 169 } |
