comparison: src/misc/RingFinder.h
src/misc/RingFinder.h
- changeset 647
- b87941923eb4
- parent 641
- 425b169a82aa
- child 650
- db7146a87ae4
equal
deleted
inserted
replaced
| 646:1ccb092cebed | 647:b87941923eb4 |
|---|---|
| 18 | 18 |
| 19 #pragma once | 19 #pragma once |
| 20 | 20 |
| 21 #include "../Main.h" | 21 #include "../Main.h" |
| 22 | 22 |
| 23 // ============================================================================= | 23 //! |
| 24 // RingFinder | 24 //! @brief Provides an algorithm for finding solutions of rings between given radii. |
| 25 // | 25 //! |
| 26 // Provides an algorithm for finding a solution of rings between radii r0 and r1. | 26 //! The RingFinder is a class which implements a ring finding algorithm. It is passed |
| 27 // ============================================================================= | 27 //! two radii and it tries to find solutions of rings that would fill the given space. |
| 28 //! | |
| 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 //! | |
| 28 class RingFinder | 32 class RingFinder |
| 29 { | 33 { |
| 30 public: | 34 public: |
| 35 //! A single component in a solution | |
| 31 struct Component | 36 struct Component |
| 32 { | 37 { |
| 33 int num; | 38 int num; |
| 34 double scale; | 39 double scale; |
| 35 }; | 40 }; |
| 36 | 41 |
| 42 //! A solution whose components would fill the desired ring space. | |
| 37 class Solution | 43 class Solution |
| 38 { | 44 { |
| 39 public: | 45 public: |
| 40 // Components of this solution | 46 //! @returns components of this solution |
| 41 inline const QVector<Component>& getComponents() const | 47 inline const QVector<Component>& getComponents() const |
| 42 { | 48 { |
| 43 return m_components; | 49 return m_components; |
| 44 } | 50 } |
| 45 | 51 |
| 46 // Add a component to this solution | 52 //! Add a component to this solution |
| 47 inline void addComponent (const Component& a) | 53 inline void addComponent (const Component& a) |
| 48 { | 54 { |
| 49 m_components.push_back (a); | 55 m_components.push_back (a); |
| 50 } | 56 } |
| 51 | 57 |
| 52 // Compare solutions | 58 //! @brief Compare solutions. |
| 53 bool isBetterThan (const Solution* other) const; | 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; | |
| 54 | 77 |
| 55 private: | 78 private: |
| 56 QVector<Component> m_components; | 79 QVector<Component> m_components; |
| 57 }; | 80 }; |
| 58 | 81 |
| 82 //! Constructs a ring finder. | |
| 59 RingFinder() {} | 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 //! | |
| 60 bool findRings (double r0, double r1); | 102 bool findRings (double r0, double r1); |
| 61 | 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() | |
| 62 inline const Solution* bestSolution() | 107 inline const Solution* bestSolution() |
| 63 { | 108 { |
| 64 return m_bestSolution; | 109 return m_bestSolution; |
| 65 } | 110 } |
| 66 | 111 |
| 112 //! @returns all found solutions. The list is empty if no solutions | |
| 113 //! @returns were found. | |
| 67 inline const QVector<Solution>& allSolutions() const | 114 inline const QVector<Solution>& allSolutions() const |
| 68 { | 115 { |
| 69 return m_solutions; | 116 return m_solutions; |
| 70 } | |
| 71 | |
| 72 inline bool operator() (double r0, double r1) | |
| 73 { | |
| 74 return findRings (r0, r1); | |
| 75 } | 117 } |
| 76 | 118 |
| 77 private: | 119 private: |
| 78 QVector<Solution> m_solutions; | 120 QVector<Solution> m_solutions; |
| 79 const Solution* m_bestSolution; | 121 const Solution* m_bestSolution; |
| 80 int m_stack; | 122 int m_stack; |
| 81 | 123 |
| 124 //! Helper function for @c findRings | |
| 82 bool findRingsRecursor (double r0, double r1, Solution& currentSolution); | 125 bool findRingsRecursor (double r0, double r1, Solution& currentSolution); |
| 83 }; | 126 }; |
| 84 | 127 |
| 85 extern RingFinder g_RingFinder; | 128 extern RingFinder g_RingFinder; |
| 86 | 129 |
