Fréchet View  1.6.0
A Tool for Exploring Fréchet Distance Algorithms
triangulation.h
Go to the documentation of this file.
1 #ifndef TRIANGULATION_H
2 #define TRIANGULATION_H
3 
4 #include <data/types.h>
5 #include <poly/types.h>
6 #include <graph_m4ri.h>
7 #include <vector>
8 
10 # define CGAL_HEADER_ONLY 1
11 # define CGAL_NO_GMP 1
13 #include <CGAL/Triangulation_data_structure_2.h>
14 
15 namespace frechet { namespace poly {
16 
17 using namespace data;
18 
23 struct DummyTDS {
24  typedef int Face_handle;
25  typedef int Vertex_handle;
26 };
27 
39 template <class TDS=DummyTDS>
41  public Point,
42  public CGAL::Triangulation_ds_vertex_base_2<TDS>
43 {
44 public:
48  template <class TDS2>
49  struct Rebind_TDS { typedef Vertex_base<TDS2> Other; };
50 
54  Vertex_base();
60  Vertex_base(const Point& p, int i);
67  Vertex_base(const Point& p, int i, double offset);
71  ~Vertex_base();
72 
77  void setPoint(const Point& p);
81  void clearTarget() { target=nullptr; }
82 
88  Vertex_base& setData(const Vertex_base& that);
97  Vertex_base& setData(const Point& p, int pindex, int dindex, double offset);
98 
100  int pindex;
102  int dindex;
105  double offset;
106 
117  Vertex_base* prev;
129  Interval L,B,R;
134  Interval LR,BR,RR;
142  QLineF treeEdge() const {
143  if (!prev)
144  return QLineF();
145  else
146  return QLineF(*prev,*this);
147  }
148 
154  bool assertEquals(const Vertex_base& that);
155 };
156 
157 
186 {
187 private:
193  typedef CGAL::Triangulation_data_structure_2<
195  CGAL::Triangulation_ds_face_base_2<> >
197 
199  int poly_n;
203  typedef std::vector<TDS::Vertex_handle> VertexMap;
205  typedef std::map<Segment,TDS::Edge> NeighborMap;
208 
210  TDS::Vertex_handle south_pole;
211 
212 public:
216  typedef TDS::Vertex_handle Vertex_handle;
218  typedef TDS::Face_handle Face_handle;
221  typedef TDS::Edge Edge;
223  typedef TDS::Face_circulator Face_circulator;
224 
226  typedef std::pair<Vertex_handle,Vertex_handle> VertexPair;
228  typedef std::pair<Edge,Edge> EdgePair;
230  typedef std::pair<Face_handle,Face_handle> FacePair;
231 
238  class Edge_iterator: public TDS::Edge_iterator
239  {
240  // Edge = std::pair<Face_handle,int>
241  public:
246  Edge_iterator(TDS::Edge_iterator i);
247 
249  Vertex_handle vertex1() const;
251  Vertex_handle vertex2() const;
252 
254  QLineF line() const;
256  Segment segment() const;
257 
260  bool is_outer_edge() const;
262  bool is_polygon_edge() const;
264  bool is_diagonal() const;
265  };
267  typedef std::pair<Edge_iterator,Edge_iterator> Edge_range;
268 
269 public:
274  Triangulation(int capacity=-1);
279  Triangulation(const Triangulation& that);
283  ~Triangulation();
284 
289  void setPolygonSize(int n);
290 
295  int size() const;
299  void resize(int sz);
300 
305  int countVertexes() const { return (int)tds.number_of_vertices(); }
309  int countFaces() const { return (int)tds.number_of_faces(); }
310 
315  Vertex_handle operator[] (int i);
320  const Vertex_handle operator[] (int i) const;
321 
323  Edge_iterator edges_begin() const { return Edge_iterator(tds.edges_begin()); }
325  Edge_iterator edges_end() const { return Edge_iterator(tds.edges_end()); }
327  Edge_range edges() const { return Edge_range(edges_begin(),edges_end()); }
328 
330  TDS::Vertex_iterator vertices_begin() const { return tds.vertices_begin(); }
332  TDS::Vertex_iterator vertices_end() const { return tds.vertices_end(); }
333 
335  FacePair adjacentFaces(Segment s) const;
336 
339  EdgePair adjacentEdges(Edge e) const;
346  EdgePair adjacentEdges(Edge e, int i1, int i2) const;
347 
354  void mirror(Edge& e) const;
359  void mirror(EdgePair& e2) const;
360 
367  Face_circulator incidentFaces(Vertex_handle v) const;
374  Vertex_handle oppositeVertex(Edge e) const;
381  int thirdVertex(int a, int b) const;
382 
389  Edge edge(int i, int j) const;
394  VertexPair incidentVertexes(Edge e) const;
395 
397  typedef std::pair<Vertex_handle,Vertex_handle> TwoVertices;
402  TwoVertices adjacentVertices(Segment s) const;
408  TwoVertices adjacentVertices(int v) const;
409 
416  Vertex_handle createVertex(const Point& p, int i);
417 
422  static Segment segment(Edge e);
427  static Vertex_handle vertex1(Edge e);
432  static Vertex_handle vertex2(Edge e);
433 
443  void createFace(int a, int b, int c);
444 
449  void complement();
453  bool isComplete() const { return neighbors.empty() && tds.is_valid(); }
454 
463  static bool is_south_pole(Vertex_handle v);
468  static bool is_outer_face(Face_handle f);
473  static bool is_inner_face(Face_handle f) ;
478  static bool is_outer_edge(Edge e);
483  static bool is_polygon_edge(Edge e);
488  static bool is_diagonal(Edge e);
489 
494  bool is_ccw_face(Face_handle f);
495 
508  Vertex_handle insertVertexOnEdge(double x);
514  void removeVertexFromEdge(int index);
515 
520  void addTargetVertices(const frechet::reach::Placements& p);
526  Vertex_handle addTargetVertex(const frechet::reach::Placement* p);
533  Vertex_handle addVertex(double w);
537  void clearTargets();
542  void clearPredecessors();
543 
551  bool assertEquals(const Triangulation& that) const;
552 
553 private:
560  void addVertex(Vertex_handle v, double x, Point p);
567  void linkNeighbors(Segment s, Edge e);
575  static Vertex_handle third_vertex(Face_handle f, Vertex_handle v1, Vertex_handle v2);
582  Vertex_handle third_vertex(Face_handle f, Segment s);
583 };
584 
589 std::ostream& operator<< (std::ostream& out, const Triangulation& tri);
590 std::ostream& operator<< (std::ostream& out, const Triangulation::Vertex_handle& v);
591 std::ostream& operator<< (std::ostream& out, const Triangulation::Face_handle& f);
592 std::ostream& operator<< (std::ostream& out, const Triangulation::Edge& e);
593 std::ostream& operator<< (std::ostream& out, const Triangulation::Edge_iterator& e);
596 /*
597  * Some template implementations
598  * */
599 
600 template <class TDS>
602  Point::operator=(p);
603 }
604 
605 template <class TDS>
607  // copy _except_ TDS
608  Point::operator=(that);
609  this->pindex = that.pindex;
610  this->dindex = that.dindex;
611  this->offset = that.offset;
612 
613  this->prev = that.prev;
614  this->target = that.target;
615  this->L=that.L;
616  this->B=that.B;
617  this->R=that.R;
618 
619  this->LR=that.LR;
620  this->BR=that.BR;
621  this->RR=that.RR;
622  return *this;
623 }
624 
625 template <class TDS>
626 Vertex_base<TDS>& Vertex_base<TDS>::setData(const Point& p, int pindex, int dindex, double offset) {
627  Point::operator=(p);
628  this->pindex = pindex;
629  this->dindex = dindex;
630  this->offset = offset;
631 
632  this->prev = nullptr;
633  this->target = nullptr;
634  this->L.clear();
635  this->B.clear();
636  this->R.clear();
637 
638  this->LR.clear();
639  this->BR.clear();
640  this->RR.clear();
641  return *this;
642 }
643 
644 
645 } }
646 
647 #endif // TRIANGULATION_H
TDS::Vertex_iterator vertices_end() const
Represents a polygon line segment from node i to j.
Definition: types.h:39
Dummy class acting as a default for template arguments (required by CGAL::Triangulation_data_structur...
Definition: triangulation.h:23
NeighborMap neighbors
Keeps track of diagonals and their neighborhood during construction.
std::vector< frechet::reach::Placement > Placements
a list of Placement objects
Definition: graph_model.h:144
std::pair< Vertex_handle, Vertex_handle > VertexPair
a pair of vertexes
std::map< Segment, TDS::Edge > NeighborMap
void setPoint(const Point &p)
assign a point in the plane
global definitions for all algorithms.
TDS::Vertex_iterator vertices_begin() const
TDS::Edge Edge
an edge of the triangulation either an edge of the polygon, or a diagonal, or an articial "outer" edg...
Edge_range edges() const
TDS::Face_handle Face_handle
handle to a triangulation face (handles are managed by TDS base class)
int dindex
Index of diagonal vertex (points into CurveData::d_points); invalid for other points.
Vertex_base & setData(const Vertex_base &that)
copy properties of derived class (anything but base class info)
int pindex
Index of polygon vertex (if this object refers to a polygon vertex; invalid for extra points)
std::pair< Edge_iterator, Edge_iterator > Edge_range
a range of edges
Interval LR
Reachable Free-Space intervals LR,BR,RR (usually part of an FSPath object)
Interval L
Free-Space intervals L,B,R (usually part of a FreeSpace object) L,B,R is calculated from [Guibas-star...
QPointF Point
a point in the plane; with double floating point precision. This type is heavily used throughout all ...
Definition: types.h:14
bool assertEquals(const mzd_t *M, const gpuword *G, int padded_rows)
const frechet::reach::Placement * target
base class for vertexes in a Triangulation Data Structure.
Definition: triangulation.h:40
template re-bind to resolve cyclic dependcies
Definition: triangulation.h:49
std::pair< Face_handle, Face_handle > FacePair
a pair of faces
std::pair< Edge, Edge > EdgePair
a pair of edges
Edge_iterator edges_end() const
Edge_iterator edges_begin() const
std::pair< Vertex_handle, Vertex_handle > TwoVertices
a pair of vertex handles
placement of a diagonal point in free-space diagram When calculating valid placements in [buchin06]
Definition: graph_model.h:132
TDS tds
CGAL Triangulation Data Structure.
CGAL::Triangulation_data_structure_2< Vertex_base<>, CGAL::Triangulation_ds_face_base_2<> > TDS
Triangulation Data Structure. Instantiates CGAL::Triangulation_data_structure_2 with our customized V...
void clearTarget()
reset target info (used by PolygonShortestPaths algorithm)
Definition: triangulation.h:81
TDS::Face_circulator Face_circulator
a circulating iterator
TDS::Vertex_handle south_pole
a special vertex that completes the TDS structure
Vertex_base< TDS > Vertex
a vertex of the triangulation
Wrapper for CGAL::Triangulation_Data_Structure https://doc.cgal.org/latest/TDS_2/index....
TDS::Vertex_handle Vertex_handle
handle to a vertex (handles are managed by TDS base class)
static bool is_diagonal(int a, int b, int n)
Definition: poly_utils.cpp:221
an interval of two double values.
Definition: interval.h:31
std::vector< TDS::Vertex_handle > VertexMap
Keeps track of Vertex handles.
edge iterator. Traverses all edges of the triangulation. Derives from TDS::Edge_iterator and supplies...
std::ostream & operator<<(std::ostream &out, const frechet::poly::CgalPolygon &poly)
print operator (for debugging)
Definition: poly_utils.cpp:338
int poly_n
polygon size, number of vertexes in polyong