Triangulation.h

Go to the documentation of this file.

/*
 *  Copyright (C) 2012 Josh Bialkowski (jbialk@mit.edu)
 *
 *  This file is part of mpblocks.
 *
 *  mpblocks 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.
 *
 *  mpblocks 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 mpblocks.  If not, see <http://www.gnu.org/licenses/>.
 */
#ifndef MPBLOCKS_CLARKSON93_DYNAMIC_TRIANGULATION_H_
#define MPBLOCKS_CLARKSON93_DYNAMIC_TRIANGULATION_H_

#include <mpblocks/clarkson93.h>
#include <set>
#include <queue>


namespace   mpblocks {
namespace clarkson93 {
namespace    dynamic {



template < class Traits >
class Triangulation
{
    public:
        // Typedefs
        // -----------------------------------------------------------------------
        static const unsigned int NDim   = Traits::NDim;

        typedef unsigned int                uint;
        typedef typename Traits::Scalar     Scalar;
        typedef typename Traits::Point      Point;
        typedef typename Traits::Simplex    Simplex;
        typedef typename Traits::PointRef   PointRef;
        typedef typename Traits::PointDeref PointDeref;
        typedef typename Traits::Setup      Setup;

        typedef Triangulation<Traits>   Triangulation_t;
        typedef Triangulation<Traits>   This_t;

        typedef HorizonRidge<Traits> HorizonRidge_t;
        typedef SimplexBase<Traits>  SimplexBase_t;

        typedef Stack<Simplex*,       SimplexBits> SimplexSet;
        typedef Stack<Simplex*>       SimplexStack;
        typedef Stack<HorizonRidge_t> HorizonSet;

        typedef typename Traits::template Factory<Simplex>         SimplexAlloc;
        typedef typename Traits::template Factory<HorizonRidge_t>  HorizonAlloc;
        typedef std::set<PointRef>                      PointSet;

        // priority queue stuff
        typedef Indexed<Scalar,Simplex*>    PQ_Key;
        typedef P_Queue<PQ_Key>             WalkQueue;

    public:
        // Data Members
        // -----------------------------------------------------------------------
        uint            m_ndim;        
        Simplex*        m_hullSimplex; 
        Simplex*        m_origin;      
        PointRef        m_antiOrigin;  
        PointDeref      m_deref;       

        WalkQueue       m_xv_walk;     
        SimplexSet      m_xv_walked; 

        SimplexSet      m_x_visible;   
        SimplexSet      m_xv_queue;    

        HorizonSet      m_ridges;      

        SimplexAlloc    m_sAlloc;   

    public:
        Triangulation();
        ~Triangulation();

        void setup( Setup& setup );

        template <class Iterator>
        void init(Iterator begin, Iterator end);


        void insert(const PointRef x, Simplex* S=0);

        void clear();

        SimplexAlloc& getAllocator(){ return m_sAlloc; }


        void find_x_visible(PointRef x, Simplex* S=0);

        // update each x-visible simplex by adding the point x as the peak
        // vertex, also create new simplices
        void alter_x_visible(PointRef x);
};



} // namespace dynamic
} // namespace clarkson93
} // namespace mpblocks














#endif // TRIANGULATION_H_