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