shortest_paths.h

Go to the documentation of this file.

#ifndef SHORTEST_PATHS_H
#define SHORTEST_PATHS_H

#include <data/types.h>
#include <triangulation.h>
#include <double_queue.h>
#include <graph_m4ri.h>

#ifdef QT_DEBUG
class TriangulationTestSuite;
#endif

namespace frechet { namespace poly {

class PolygonShortestPaths
{
public:
    typedef Triangulation::Vertex_handle Vertex_handle;
    typedef Triangulation::Face_handle Face_handle;
    typedef Triangulation::Face_circulator Face_circulator;
    typedef Triangulation::Edge Edge;
    typedef DoubleEndedQueue<Vertex_handle> Funnel;

protected:
    Triangulation& tri;
    Funnel funnel;

public:
    PolygonShortestPaths(Triangulation& atri);

    Triangulation& triangulation() const { return tri; }

    void findShortestPaths(Vertex_handle start_point);

    Curve find1ShortestPath(double p1, double p2);

    virtual void shortestPath() {}
    virtual void undo() {}

    void assertFunnel() const;
    const Funnel& getFunnel() const { return funnel; }

protected:
    void search(Vertex_handle start_point, Face_handle f);
    void search(Edge e);

    virtual bool updateSPSegment(Vertex_handle prev, Vertex_handle v);

    int findTangent(Vertex_handle v) const;
    int findTangentLeft(int t1, int t2, Vertex_handle v) const;
    int findTangentRight(int t1, int t2, Vertex_handle v) const;
    bool isTangent(int t, Vertex_handle v) const;

public:
    template<typename Float>
    static int halfplaneTest(Vertex_handle a, Vertex_handle b, Vertex_handle p);
};

class PolygonShortestPathsFS : public PolygonShortestPaths
{
private:
    const frechet::reach::Placement* source;
    QLineF d;
    double epsilon;
    frechet::reach::Graph::ptr validPlacements;

public:
    PolygonShortestPathsFS(Triangulation& atri);

    void findShortestPaths(Vertex_handle start_point,
                            const frechet::reach::Placement* asource,
                            QLineF d, double epsilon,
                            frechet::reach::Graph::ptr validPlacements);

protected:
    void initReachability(Vertex_handle v);
    void propagateReachability(Vertex_handle v);

    virtual bool updateSPSegment(Vertex_handle prev, Vertex_handle v) override;

public:
#ifdef QT_DEBUG
    friend class ::TriangulationTestSuite;
#endif    
    typedef void (*assert_hook1) (PolygonShortestPathsFS*, Vertex_handle v, bool reachable);
    typedef void (*assert_hook2) (PolygonShortestPathsFS*, const frechet::reach::Placement*, const frechet::reach::Placement*);
    static assert_hook1 after_target_found;
    static assert_hook2 after_placement_added;
};

} }     //  namespace frechet::poly


template<typename Float>
int frechet::poly::PolygonShortestPaths::halfplaneTest(Vertex_handle a, Vertex_handle b, Vertex_handle p)
{
    //  for extra vertexes on a polygon edges, we can detect colinearity from their offset
    double x1 = floor(a->offset);
    double x2 = lower_floor(b->offset);
    if ((x1==x2) && (p->offset >= x1) && (p->offset <= (x1+1)))
        return 0;
    //  otherwise: calculate from geometry
    Float ax = a->x();
    Float ay = a->y();
    Float bx = b->x();
    Float by = b->y();
    Float px = p->x();
    Float py = p->y();

    Float A = (py-ay) * (bx-ax);
    Float B = (px-ax) * (by-ay);
    if (A < B) return -1;
    if (A > B) return +1;
    return 0;
}

#endif // SHORTEST_PATHS_H