Mercurial > ldforge / file comparison

comparison: src/misc/RingFinder.cc

src/misc/RingFinder.cc

changeset 706
d79083b9f74d
parent 705
09150d027e8c
parent 655
b376645315ab
child 707
c89b58ba266b
equal deleted inserted replaced
705:09150d027e8c 706:d79083b9f74d
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 //
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 = &sol;
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 }

Mercurial Repository: ldforge

mercurial