comparison: src/misc/RingFinder.h
src/misc/RingFinder.h
- 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 #pragma once | |
| 20 | |
| 21 #include "../Main.h" | |
| 22 | |
| 23 //! | |
| 24 //! \brief Provides an algorithm for finding solutions of rings between given radii. | |
| 25 //! | |
| 26 //! The RingFinder is a class which implements a ring finding algorithm. It is passed | |
| 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 //! | |
| 32 class RingFinder | |
| 33 { | |
| 34 public: | |
| 35 //! A single component in a solution | |
| 36 struct Component | |
| 37 { | |
| 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 | |
| 119 private: | |
| 120 QVector<Solution> m_solutions; | |
| 121 const Solution* m_bestSolution; | |
| 122 int m_stack; | |
| 123 | |
| 124 //! Helper function for \c findRings | |
| 125 bool findRingsRecursor (double r0, double r1, Solution& currentSolution); | |
| 126 }; | |
| 127 | |
| 128 extern RingFinder g_RingFinder; | |
| 129 |
