algorithm.h

Go to the documentation of this file.

#ifndef ALGORITHM_H
#define ALGORITHM_H

#include <data/types.h>
#include <poly/types.h>
#include <poly/triangulation.h>
#include <freespace.h>
#include <fs_path.h>
#include <structure.h>
#include <graph_m4ri.h>
#include <boost/smart_ptr.hpp>
#include <boost/unordered_map.hpp>
#include <set>
#include <shortest_paths.h>
#include <data/numeric.h>
#include <tbb/concurrent_unordered_map.h>

class TriangulationTestSuite;

namespace frechet { namespace poly {

class PolygonUtilities;
class PolygonWorkerJob;
class Algorithm : public QObject {
    //  Qt wiring:
    Q_OBJECT
signals:
    void statusChanged();
    void pathUpdated(bool valid);
    void optimisationResult(double epsilon);

public slots:
    void resetStatus(bool stopping=false);

public:
    enum Status : int8_t {
        RUNNING = -2,   

        RUNNING_DECIDE_POLY=-8,     
        RUNNING_OPT_POLY=-7,        
        RUNNING_APPROX_POLY=-6,     
        RUNNING_DECIDE_CURVE=-5,    
        RUNNING_OPT_CURVE=-4,       
        RUNNING_APPROX_CURVE=-3,    

        YES=0,  
        NO,     

        NOT_SET_UP,
        SET_UP,
        P_EMPTY,
        Q_EMPTY,
        P_NOT_CLOSED,
        Q_NOT_CLOSED,
        P_NOT_SIMPLE,
        Q_NOT_SIMPLE,
        P_NOT_COUNTER_CLOCKWISE,
        Q_NOT_COUNTER_CLOCKWISE,
        P_CONVEX,
        Q_CONVEX,
    };

    typedef frechet::reach::Graph::ptr GraphPtr;

protected:
#ifdef QT_DEBUG
    friend class ::TriangulationTestSuite;
#endif
    enum Status _status;
    enum Status initial_status;

    struct CurveData {
        Curve curve;
        Partition partition;
        Segments _c_diagonals;
        Polygon _d_points;
        Triangulation triangulation;
        Triangulation* display_triangulation;
        Polygon reflex;
        PolygonUtilities* utils;

        CurveData();
        ~CurveData();

        int n() const { return curve.size()-1; }
        int l() const { return _d_points.size(); }
        int k() const { return _c_diagonals.size(); }
        int d(int i) const {
            i = (i + l()) % l();
            return _d_points[i];
        }
        int partitions() const { return partition.size(); }

        int calculate_c_diagonals(Segments& result);
        int calculate_d_points();
    } *P, *Q;

    FreeSpace::ptr fs;

    //typedef boost::unordered_map<int,GraphPtr> GraphMap;
    typedef tbb::concurrent_unordered_map<int,GraphPtr> PlacementMap;
    typedef std::vector<reach::Placements> PlacementVector;

    PlacementVector _placements;
    PlacementMap _validPlacements;

    reach::GraphModel::ptr graphModel;
    
    typedef tbb::concurrent_unordered_map<int, reach::Graph::ptr> GraphMap;

    GraphMap CRG_map;

    GraphPtr getValidPlacements(int di, int dj);
    GraphPtr calculate_RG(int i);
    int mapKey(int di, int dj);

    FreeSpace::ptr local_fs;

    typedef std::vector<double> CriticalValueList;
    CriticalValueList criticalValues;

public:
    typedef boost::shared_ptr<Algorithm> ptr;

    Algorithm();
    virtual ~Algorithm();

    Status status() const { return _status; }

    bool canDecidePoly() const      { return _status==SET_UP; }
    bool canOptimisePoly() const    { return _status==SET_UP || _status==YES || _status==NO; }
    bool canOptimiseCurve() const   { return _status==SET_UP || _status==YES || _status==NO || _status>=P_NOT_CLOSED; }

    const Segments& c_diagonals() const;

    bool is_c_diagonal(int di, int dj) const;
    bool is_c_diagonal(Segment s) const;

    Triangulation& PTriangulation() { return P->triangulation; }
    Triangulation& QTriangulation() { return Q->triangulation; }
    Triangulation& displayPTriangulation() { return *P->display_triangulation; }

    const Curve& Pcurve() const { return P->curve; }
    const Curve& Qcurve() const { return Q->curve; }

    PolygonUtilities* polygonUtilities(bool primary) {
        return (primary ? P:Q)->utils;
    }

    Status setup(Curve& aP, Curve& aQ, bool fixOrientation=false);

    bool decompose(bool optimal);
    void swap();
    virtual void triangulate();

    /*
     *  update with new epsilon & free-space
     *  @return true if there is a solution
     *
     *  return feasible path
     */
    //typedef ResultPtr (*decideFunction) (FreeSpace::ptr, reach::FSPath::ptr, double, bool);
    GraphPtr decidePolygon( FreeSpace::ptr fs,
                            reach::FSPath::ptr path,
                            double epsilon,
                            bool update_status);

    double optimisePolygon( reach::FSPath::ptr path,
                            double approximation=0.0);

    reach::Pointer decideCurve( FreeSpace::ptr fs,
                                reach::FSPath::ptr path,
                                double ignored,
                                bool update_status);

    double optimiseCurve(double approximation=0.0);

    static double pickIntervalPoint(const Interval& j, int m=INT_MAX);

//    static int findFeasibleStart(GraphPtr G);

protected:
    virtual void calculateValidPlacements(double epsilon)=0;
    virtual void calculateReachabilityGraphs()=0;

    virtual GraphPtr findFeasiblePath()=0;

    GraphPtr createValidPlacementGraph(int di, int dj);
    void calculateValidPlacements(
            poly::PolygonShortestPathsFS& spt,
            double epsilon, int di, int dj);

    Triangulation::Edge diagonalEdge(int i) const;

    int l() const { return P->l(); }
    int k() const { return P->k(); }
    int d(int i) const { return P->d(i); }

    int partitions() const { return P->partitions(); }

    void calculatePlacements(int i, frechet::reach::Placements& result);

    virtual reach::Graph::ptr CRG(int i, int j, Triangulation::Edge e = Triangulation::Edge())=0;
    virtual reach::Graph::ptr create_RG(int i)=0;
    virtual reach::Graph::ptr create_CRG(int i, int j, Triangulation::Edge e)=0;

    virtual reach::Graph::ptr MERGE_inner(const reach::Graph::ptr  A, const reach::Graph::ptr  B)=0;
    virtual reach::Graph::ptr MERGE_outer(const reach::Graph::ptr  A, const reach::Graph::ptr  B)=0;
    virtual void COMBINE(reach::Graph::ptr  A, int di, int dj)=0;

    Status setStatus(Status);
    Status setInitialStatus(Status);
    virtual void cleanup();

    void updatePath(reach::FSPath::ptr path, GraphPtr result, double epsilon);
    void updatePath(reach::FSPath::ptr path, reach::Pointer startPointer, double epsilon);
public:
    void collectCriticalValues(bool a, bool b, bool c, bool d);
    virtual CriticalValueList& currentCriticalValueList();

protected:
    void collectCriticalValues_a();
    void collectCriticalValues_b(const Point& p, const Curve& Q);
    void collectCriticalValues_c(const QLineF& pseg, const Curve& Q);
    void collectCriticalValues_d(const QLineF& diagonal);
    //  TODO only i

    virtual void collectCriticalValue(const accurate_float& x);

    virtual void collectCriticalValues_b(const Curve& P, const Curve& Q)=0;
    virtual void collectCriticalValues_c(const Curve& P, const Curve& Q)=0;
    virtual void collectCriticalValues_d()=0;
    virtual void combineCriticalValues()=0;
    void removeDuplicates(CriticalValueList& vector);

    template<typename R>
    int binarySearch(const std::vector<double>& values, int lo, int hi,
            R (Algorithm::* decideFunction) (FreeSpace::ptr, reach::FSPath::ptr, double, bool),
            R& result);

    template<typename R>
    double intervalSearch(
            double lower_bound, double upper_bound, double precision,
            R (Algorithm::* decideFunction) (FreeSpace::ptr, reach::FSPath::ptr, double, bool),
            R& result);

    template<typename Float>
    static Float bisector_distance(
            const Float& p1x, const Float& p1y,
            const Float& p2x, const Float& p2y,
            const Float& q1x, const Float& q1y,
            const Float& q2x, const Float& q2y,
            const Float& tolerance);

    template<typename Float>
    static Float segment_distance(const QLineF& segment, const Point& q1);

    template<typename Float>
    static Float bisector_distance(
            const Point& q1, const Point& q2,
            const QLineF& segment,
            Float tolerance=0.0);

    friend class frechet::poly::PolygonWorkerJob;
    volatile bool* cancelFlag;
    void testCancelFlag();
};


Algorithm::ptr newPolyAlgorithm(bool topo);

} } //  namespace frechet::poly
#endif // ALGORITHM_H