diff -r 09150d027e8c -r d79083b9f74d src/misc/RingFinder.h --- a/src/misc/RingFinder.h Wed Mar 12 16:21:49 2014 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,129 +0,0 @@ -/* - * LDForge: LDraw parts authoring CAD - * Copyright (C) 2013, 2014 Santeri Piippo - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation, either version 3 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program. If not, see . - */ - -#pragma once - -#include "../Main.h" - -//! -//! \brief Provides an algorithm for finding solutions of rings between given radii. -//! -//! The RingFinder is a class which implements a ring finding algorithm. It is passed -//! two radii and it tries to find solutions of rings that would fill the given space. -//! -//! \note It is not fool-proof and does not always yield a solution, never assume -//! \note that one is a available as none is guaranteed. -//! -class RingFinder -{ - public: - //! A single component in a solution - struct Component - { - int num; - double scale; - }; - - //! A solution whose components would fill the desired ring space. - class Solution - { - public: - //! \returns components of this solution - inline const QVector& getComponents() const - { - return m_components; - } - - //! Add a component to this solution - inline void addComponent (const Component& a) - { - m_components.push_back (a); - } - - //! \brief Compare solutions. - //! - //! Compares this solution with \c other and determines which - //! one is superior. - //! - //! A solution is considered superior if solution has less - //! components than the other one. If both solution have an - //! equal amount components, the solution with a lesser maximum - //! ring number is found superior, as such solutions should - //! yield less new primitives and cleaner definitions. - //! - //! The solution which is found superior to every other solution - //! will be the one returned by \c RingFinder::bestSolution(). - //! - //! \param other the solution to check against - //! \returns whether this solution is considered superior - //! \returns to \c other. - //! - bool isSuperiorTo (const Solution* other) const; - - private: - QVector m_components; - }; - - //! Constructs a ring finder. - RingFinder() {} - - //! \brief Tries to find rings between \c r0 and \c r1. - //! - //! This is the main algorithm of the ring finder. It tries to use math - //! to find the one ring between r0 and r1. If it fails (the ring number - //! is non-integral), it finds an intermediate radius (ceil of the ring - //! number times scale) and splits the radius at this point, calling this - //! function again to try find the rings between r0 - r and r - r1. - //! - //! This does not always yield into usable results. If at some point r == - //! r0 or r == r1, there is no hope of finding the rings, at least with - //! this algorithm, as it would fall into an infinite recursion. - //! - //! \param r0 the lower radius of the ring space - //! \param r1 the higher radius of the ring space - //! \returns whether it was possible to find a solution for the given - //! \returns ring space. - //! - bool findRings (double r0, double r1); - - //! \returns the solution that was considered best. Returns \c null - //! \returns if no suitable solution was found. - //! \see \c RingFinder::Solution::isSuperiorTo() - inline const Solution* bestSolution() - { - return m_bestSolution; - } - - //! \returns all found solutions. The list is empty if no solutions - //! \returns were found. - inline const QVector& allSolutions() const - { - return m_solutions; - } - - private: - QVector m_solutions; - const Solution* m_bestSolution; - int m_stack; - - //! Helper function for \c findRings - bool findRingsRecursor (double r0, double r1, Solution& currentSolution); -}; - -extern RingFinder g_RingFinder; -