comparison: src/misc/ringFinder.h
src/misc/ringFinder.h
- changeset 811
- 27ccc8eca322
- parent 655
- b376645315ab
- child 812
- b7e0d08becac
equal
deleted
inserted
replaced
| 810:04e05381ad32 | 811:27ccc8eca322 |
|---|---|
| 15 * You should have received a copy of the GNU General Public License | 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/>. | 16 * along with this program. If not, see <http://www.gnu.org/licenses/>. |
| 17 */ | 17 */ |
| 18 | 18 |
| 19 #pragma once | 19 #pragma once |
| 20 | |
| 21 #include "../main.h" | 20 #include "../main.h" |
| 22 | 21 |
| 23 //! | 22 // |
| 24 //! \brief Provides an algorithm for finding solutions of rings between given radii. | 23 // Implements a ring finding algorithm. It is passed two radii and it tries to |
| 25 //! | 24 // find solutions of rings that would fill the given space. |
| 26 //! The RingFinder is a class which implements a ring finding algorithm. It is passed | 25 // |
| 27 //! two radii and it tries to find solutions of rings that would fill the given space. | 26 // Note: it is not fool-proof and does not always yield a solution. |
| 28 //! | 27 // |
| 29 //! \note It is not fool-proof and does not always yield a solution, never assume | |
| 30 //! \note that one is a available as none is guaranteed. | |
| 31 //! | |
| 32 class RingFinder | 28 class RingFinder |
| 33 { | 29 { |
| 30 public: | |
| 31 // A single component in a solution | |
| 32 struct Component | |
| 33 { | |
| 34 int num; | |
| 35 double scale; | |
| 36 }; | |
| 37 | |
| 38 // A solution whose components fill the desired ring space. | |
| 39 class Solution | |
| 40 { | |
| 34 public: | 41 public: |
| 35 //! A single component in a solution | 42 inline void addComponent (const Component& a); |
| 36 struct Component | 43 inline const QVector<Component>& getComponents() const; |
| 37 { | 44 bool isSuperiorTo (const Solution* other) const; |
| 38 int num; | |
| 39 double scale; | |
| 40 }; | |
| 41 | |
| 42 //! A solution whose components would fill the desired ring space. | |
| 43 class Solution | |
| 44 { | |
| 45 public: | |
| 46 //! \returns components of this solution | |
| 47 inline const QVector<Component>& getComponents() const | |
| 48 { | |
| 49 return m_components; | |
| 50 } | |
| 51 | |
| 52 //! Add a component to this solution | |
| 53 inline void addComponent (const Component& a) | |
| 54 { | |
| 55 m_components.push_back (a); | |
| 56 } | |
| 57 | |
| 58 //! \brief Compare solutions. | |
| 59 //! | |
| 60 //! Compares this solution with \c other and determines which | |
| 61 //! one is superior. | |
| 62 //! | |
| 63 //! A solution is considered superior if solution has less | |
| 64 //! components than the other one. If both solution have an | |
| 65 //! equal amount components, the solution with a lesser maximum | |
| 66 //! ring number is found superior, as such solutions should | |
| 67 //! yield less new primitives and cleaner definitions. | |
| 68 //! | |
| 69 //! The solution which is found superior to every other solution | |
| 70 //! will be the one returned by \c RingFinder::bestSolution(). | |
| 71 //! | |
| 72 //! \param other the solution to check against | |
| 73 //! \returns whether this solution is considered superior | |
| 74 //! \returns to \c other. | |
| 75 //! | |
| 76 bool isSuperiorTo (const Solution* other) const; | |
| 77 | |
| 78 private: | |
| 79 QVector<Component> m_components; | |
| 80 }; | |
| 81 | |
| 82 //! Constructs a ring finder. | |
| 83 RingFinder() {} | |
| 84 | |
| 85 //! \brief Tries to find rings between \c r0 and \c r1. | |
| 86 //! | |
| 87 //! This is the main algorithm of the ring finder. It tries to use math | |
| 88 //! to find the one ring between r0 and r1. If it fails (the ring number | |
| 89 //! is non-integral), it finds an intermediate radius (ceil of the ring | |
| 90 //! number times scale) and splits the radius at this point, calling this | |
| 91 //! function again to try find the rings between r0 - r and r - r1. | |
| 92 //! | |
| 93 //! This does not always yield into usable results. If at some point r == | |
| 94 //! r0 or r == r1, there is no hope of finding the rings, at least with | |
| 95 //! this algorithm, as it would fall into an infinite recursion. | |
| 96 //! | |
| 97 //! \param r0 the lower radius of the ring space | |
| 98 //! \param r1 the higher radius of the ring space | |
| 99 //! \returns whether it was possible to find a solution for the given | |
| 100 //! \returns ring space. | |
| 101 //! | |
| 102 bool findRings (double r0, double r1); | |
| 103 | |
| 104 //! \returns the solution that was considered best. Returns \c null | |
| 105 //! \returns if no suitable solution was found. | |
| 106 //! \see \c RingFinder::Solution::isSuperiorTo() | |
| 107 inline const Solution* bestSolution() | |
| 108 { | |
| 109 return m_bestSolution; | |
| 110 } | |
| 111 | |
| 112 //! \returns all found solutions. The list is empty if no solutions | |
| 113 //! \returns were found. | |
| 114 inline const QVector<Solution>& allSolutions() const | |
| 115 { | |
| 116 return m_solutions; | |
| 117 } | |
| 118 | 45 |
| 119 private: | 46 private: |
| 120 QVector<Solution> m_solutions; | 47 QVector<Component> m_components; |
| 121 const Solution* m_bestSolution; | 48 }; |
| 122 int m_stack; | |
| 123 | 49 |
| 124 //! Helper function for \c findRings | 50 RingFinder(); |
| 125 bool findRingsRecursor (double r0, double r1, Solution& currentSolution); | 51 |
| 52 inline const QVector<Solution>& allSolutions() const; | |
| 53 inline const Solution* bestSolution() const; | |
| 54 bool findRings (double r0, double r1); | |
| 55 | |
| 56 private: | |
| 57 QVector<Solution> m_solutions; | |
| 58 const Solution* m_bestSolution; | |
| 59 int m_stack; | |
| 60 | |
| 61 bool findRingsRecursor (double r0, double r1, Solution& currentSolution); | |
| 126 }; | 62 }; |
| 127 | 63 |
| 64 // | |
| 65 // Gets the components of a solution | |
| 66 // | |
| 67 inline const QVector<RingFinder::Component>& RingFinder::Solution::getComponents() const | |
| 68 { | |
| 69 return m_components; | |
| 70 } | |
| 71 | |
| 72 // | |
| 73 // Adds a component to a solution | |
| 74 // | |
| 75 inline void RingFinder::Solution::addComponent (const Component& a) | |
| 76 { | |
| 77 m_components.push_back (a); | |
| 78 } | |
| 79 | |
| 80 // | |
| 81 // Returns the solution that was considered best. Returns null | |
| 82 // if there isn't any suitable solution. | |
| 83 // | |
| 84 inline const RingFinder::Solution* RingFinder::bestSolution() const | |
| 85 { | |
| 86 return m_bestSolution; | |
| 87 } | |
| 88 | |
| 89 // | |
| 90 // Returns all found solutions. | |
| 91 // | |
| 92 inline const QVector<RingFinder::Solution>& RingFinder::allSolutions() const | |
| 93 { | |
| 94 return m_solutions; | |
| 95 } | |
| 96 | |
| 128 extern RingFinder g_RingFinder; | 97 extern RingFinder g_RingFinder; |
| 129 |
