triangulation.h

Go to the documentation of this file.

#ifndef TRIANGULATION_H
#define TRIANGULATION_H

#include <data/types.h>
#include <poly/types.h>
#include <graph_m4ri.h>
#include <vector>

# define CGAL_HEADER_ONLY 1
# define CGAL_NO_GMP 1
#include <CGAL/Triangulation_data_structure_2.h>

namespace frechet { namespace poly {

using namespace data;

struct DummyTDS {
    typedef int  Face_handle;
    typedef int  Vertex_handle;
};

template <class TDS=DummyTDS>
class Vertex_base:
        public Point,
        public CGAL::Triangulation_ds_vertex_base_2<TDS>
{
public:
    template <class TDS2>
    struct Rebind_TDS { typedef Vertex_base<TDS2> Other; };

    Vertex_base();
    Vertex_base(const Point& p, int i);
    Vertex_base(const Point& p, int i, double offset);
    ~Vertex_base();

    void setPoint(const Point& p);
    void clearTarget() { target=nullptr; }

    Vertex_base& setData(const Vertex_base& that);
    Vertex_base& setData(const Point& p, int pindex, int dindex, double offset);

    int pindex;
    int dindex;
    double offset;

    Vertex_base* prev;
    const frechet::reach::Placement* target;
    Interval L,B,R;
    Interval LR,BR,RR;
    QLineF treeEdge() const {
        if (!prev)
            return QLineF();
        else
            return QLineF(*prev,*this);
    }

    bool assertEquals(const Vertex_base& that);
};


class Triangulation
{
private:
    typedef CGAL::Triangulation_data_structure_2<
                    Vertex_base<>,
                    CGAL::Triangulation_ds_face_base_2<> >
            TDS;

    int poly_n;
    TDS tds;
    typedef std::vector<TDS::Vertex_handle> VertexMap;
    VertexMap vertices;    
    typedef std::map<Segment,TDS::Edge> NeighborMap;
    NeighborMap neighbors;

    TDS::Vertex_handle south_pole;

public:
    typedef Vertex_base<TDS> Vertex;
    typedef TDS::Vertex_handle Vertex_handle;
    typedef TDS::Face_handle Face_handle;
    typedef TDS::Edge Edge;
    typedef TDS::Face_circulator Face_circulator;

    typedef std::pair<Vertex_handle,Vertex_handle> VertexPair;
    typedef std::pair<Edge,Edge> EdgePair;
    typedef std::pair<Face_handle,Face_handle>  FacePair;

    class Edge_iterator: public TDS::Edge_iterator
    {
        //  Edge = std::pair<Face_handle,int>
    public:
        Edge_iterator(TDS::Edge_iterator i);

        Vertex_handle vertex1() const;
        Vertex_handle vertex2() const;

        QLineF line() const;
        Segment segment() const;

        bool is_outer_edge() const;
        bool is_polygon_edge() const;
        bool is_diagonal() const;
    };
    typedef std::pair<Edge_iterator,Edge_iterator> Edge_range;

public:
    Triangulation(int capacity=-1);
    Triangulation(const Triangulation& that);
    ~Triangulation();

    void setPolygonSize(int n);

    int size() const;
    void resize(int sz);

    int countVertexes() const { return (int)tds.number_of_vertices(); }
    int countFaces() const { return (int)tds.number_of_faces(); }

    Vertex_handle operator[] (int i);
    const Vertex_handle operator[] (int i) const;

    Edge_iterator   edges_begin() const     { return Edge_iterator(tds.edges_begin()); }
    Edge_iterator   edges_end() const       { return Edge_iterator(tds.edges_end()); }
    Edge_range      edges() const           { return Edge_range(edges_begin(),edges_end()); }

    TDS::Vertex_iterator vertices_begin() const     { return tds.vertices_begin(); }
    TDS::Vertex_iterator vertices_end() const       { return tds.vertices_end(); }

    FacePair adjacentFaces(Segment s) const;

    EdgePair adjacentEdges(Edge e) const;
    EdgePair adjacentEdges(Edge e, int i1, int i2) const;

    void mirror(Edge& e) const;
    void mirror(EdgePair& e2) const;

    Face_circulator incidentFaces(Vertex_handle v) const;
    Vertex_handle oppositeVertex(Edge e) const;
    int thirdVertex(int a, int b) const;

    Edge edge(int i, int j) const;
    VertexPair incidentVertexes(Edge e) const;

    typedef std::pair<Vertex_handle,Vertex_handle>  TwoVertices;
    TwoVertices adjacentVertices(Segment s) const;
    TwoVertices adjacentVertices(int v) const;

    Vertex_handle createVertex(const Point& p, int i);

    static Segment segment(Edge e);
    static Vertex_handle vertex1(Edge e);
    static Vertex_handle vertex2(Edge e);

    void createFace(int a, int b, int c);

    void complement();
    bool isComplete() const { return neighbors.empty() && tds.is_valid(); }

    static bool is_south_pole(Vertex_handle v);
    static bool is_outer_face(Face_handle f);
    static bool is_inner_face(Face_handle f) ;
    static bool is_outer_edge(Edge e);
    static bool is_polygon_edge(Edge e);
    static bool is_diagonal(Edge e);

    bool is_ccw_face(Face_handle f);

    Vertex_handle insertVertexOnEdge(double x);
    void removeVertexFromEdge(int index);

    void addTargetVertices(const frechet::reach::Placements& p);
    Vertex_handle addTargetVertex(const frechet::reach::Placement* p);
    Vertex_handle addVertex(double w);
    void clearTargets();    
    void clearPredecessors();

    bool assertEquals(const Triangulation& that) const;

private:
    void addVertex(Vertex_handle v, double x, Point p);
    void linkNeighbors(Segment s, Edge e);
    static Vertex_handle third_vertex(Face_handle f, Vertex_handle v1, Vertex_handle v2);
    Vertex_handle third_vertex(Face_handle f, Segment s);
};

std::ostream& operator<< (std::ostream& out, const Triangulation& tri);
std::ostream& operator<< (std::ostream& out, const Triangulation::Vertex_handle& v);
std::ostream& operator<< (std::ostream& out, const Triangulation::Face_handle& f);
std::ostream& operator<< (std::ostream& out, const Triangulation::Edge& e);
std::ostream& operator<< (std::ostream& out, const Triangulation::Edge_iterator& e);
/*
 * Some template implementations
 * */

template <class TDS>
void Vertex_base<TDS>::setPoint(const Point& p) {
    Point::operator=(p);
}

template <class TDS>
Vertex_base<TDS>& Vertex_base<TDS>::setData(const Vertex_base& that) {
    //  copy _except_ TDS
    Point::operator=(that);
    this->pindex = that.pindex;
    this->dindex = that.dindex;
    this->offset = that.offset;

    this->prev = that.prev;
    this->target = that.target;
    this->L=that.L;
    this->B=that.B;
    this->R=that.R;

    this->LR=that.LR;
    this->BR=that.BR;
    this->RR=that.RR;
    return *this;
}

template <class TDS>
Vertex_base<TDS>& Vertex_base<TDS>::setData(const Point& p, int pindex, int dindex, double offset) {
    Point::operator=(p);
    this->pindex = pindex;
    this->dindex = dindex;
    this->offset = offset;

    this->prev = nullptr;
    this->target = nullptr;
    this->L.clear();
    this->B.clear();
    this->R.clear();

    this->LR.clear();
    this->BR.clear();
    this->RR.clear();
    return *this;
}


} }

#endif // TRIANGULATION_H