Delaunator
2D Delaunay Triangulation in C++ with Python wrapper.
 All Classes Namespaces Functions
triangulation.h
1 #ifndef DELAUNATOR_TRIANGULATION_H_INCLUDED
2 #define DELAUNATOR_TRIANGULATION_H_INCLUDED
3 
4 
5 
6 /*
7  * LIBRARIES
8  */
9 // LOCAL MODULES
10 #include "commons.h"
11 #include "geometry.h"
12 #include "vertex.h"
13 #include "face.h"
14 #include "edge.h"
15 #include "iterators.h"
16 
17 
18 
19 /*
20  * DEFINES
21  */
22 
23 
24 
25 /*
26  * PREDECLARATIONS
27  */
37 enum VertexFinderMode {
38  VERTEX_FINDER_MODE_RANDOM,
39  VERTEX_FINDER_MODE_FIRST,
40  VERTEX_FINDER_MODE_MIDDLE,
41  VERTEX_FINDER_MODE_LAST
42 };
43 
44 
45 
46 /*
47  * For some explanations on quad-edge implementation :
48  * http://totologic.blogspot.fr/2013/11/core-quad-edge-implementation-explained.html
49 */
50 
51 
52 
53 
54 
61 class Triangulation {
62  public:
63  // INTERNAL CLASS TYPES
64  // define type for pointer to function that looking for initial Edge
65  typedef Edge* (Triangulation::*finderInitialEdge_mode)() const;
66 
67  // CONSTRUCTOR
68  Triangulation(const float, const float,
69  const float, const float, const VertexFinderMode = VERTEX_FINDER_MODE_LAST);
70  ~Triangulation();
71  // PUBLIC METHODS
72  Vertex* addVertexAt(Coordinates, Edge* = NULL);
73  Vertex* addVertexAt(float x, float y, Edge* e = NULL)
74  { return this->addVertexAt(Coordinates(x, y), e); }
75  Vertex* vertexAt(float, float, float=EPSILON) const;
76  Vertex* vertexAt(Coordinates c, float p=EPSILON) const { return this->vertexAt(c.x(), c.y(), p); }
77  Vertex* moveVertex(Vertex* v, Coordinates c) { return this->moveVertex(v, c.x(), c.y()); }
78  Vertex* moveVertex(Vertex* v, float x, float y);
79  Vertex* moveVertexTo(Vertex* v, Coordinates c);
80  void delVertex(Vertex* v);
81  void mergeVertex(Vertex* v, Vertex* v_destroyed);
82 #ifdef DEBUG // some tests with assertions
83  void DEBUG_tests() const;
84 #endif
85  // ACCESSORS
86  unsigned int getIndexOf(Vertex*) const;
87  std::vector<Edge*> getEdges() const { return this->edges; }
88  unsigned int getVerticeCount() const { return this->vertices.size(); }
89  float getXmin() const { return this->xmin; }
90  float getXmax() const { return this->xmax; }
91  float getYmin() const { return this->ymin; }
92  float getYmax() const { return this->ymax; }
93  float epsilon() const { return EPSILON; }
94  VertexFinderMode getFinderMode() const;
95  void setFinderMode(VertexFinderMode);
96 
97  // PREDICATS
98  bool haveVertex(Vertex*) const;
99  bool collideAt(Coordinates) const;
100 #ifdef DEBUG
101  bool opt_isdebug() const { return true; }
102 #else
103  bool opt_isdebug() const { return false; }
104 #endif
105 #ifdef FOLLOW_SEARCH
106  bool opt_follow_search() const { return true; }
107 #else
108  bool opt_follow_search() const { return false; }
109 #endif
110 
111 
112  // ITERATORS
113  IteratorVertexToNeighbourVertices getNeighbors(Vertex*);
114  // edges necessary for user
115  IteratorOnEdges iterEdges() { return IteratorOnEdges(&this->edges); }
116  IteratorOnEdges_read iterEdges_read() const
117  { return IteratorOnEdges_read(&this->edges); }
118  // all edges, including the externals ones
119  IteratorOnAllEdges iterAllEdges() { return IteratorOnAllEdges(&this->edges); }
120  IteratorOnAllEdges_read iterAllEdges_read() const
121  { return IteratorOnAllEdges_read(&this->edges); }
122  // faces that are visible to user
123  IteratorOnFaces iterFaces() { return IteratorOnFaces(&this->faces); }
124  IteratorOnFaces_read iterFaces_read() const
125  { return IteratorOnFaces_read(&this->faces); }
126  // all faces, including the unvisible ones
127  IteratorOnAllFaces iterAllFaces() { return IteratorOnAllFaces(&this->faces); }
128  IteratorOnAllFaces_read iterAllFaces_read() const
129  { return IteratorOnAllFaces_read(&this->faces); }
130  // vertices placed by user
131  IteratorOnVertices iterVertices() { return IteratorOnVertices(&this->vertices); }
132  IteratorOnVertices_read iterVertices_read() const
133  { return IteratorOnVertices_read(&this->vertices); }
134  // all vertices, including the 4 used for create and maintain the mesh
135  IteratorOnAllVertices iterAllVertices() { return IteratorOnAllVertices(&this->vertices); }
136  IteratorOnAllVertices_read iterAllVertices_read() const
137  { return IteratorOnAllVertices_read(&this->vertices); }
138 
139 
140 
141 
142 // PRIVATE
143  private:
144  // ATTRIBUTES
145  float xmin, xmax, ymin, ymax;
146  std::vector<Vertex*> vertices;
147  std::vector<Edge*> edges;
148  std::vector<Face*> faces;
149  finderInitialEdge_mode finderInitialEdge = NULL; // pointer to func that looking for initial Edge
150  // PRIVATE METHODS
151  Face* findContainerOf(Coordinates, Edge* = NULL) const;
152  // methods for choose initial Edges. The effectively used is pointed by finderInitialEdge.
153  Edge* finderInitial_random() const { return this->edges[randN(this->edges.size())]; }
154  Edge* finderInitial_middle() const { return this->edges[randN(this->edges.size()/2)]; }
155  Edge* finderInitial_first () const { return this->edges[0]; }
156  Edge* finderInitial_last () const { return this->edges[this->edges.size()-1]; }
157 #ifdef DEBUG
158  bool applyDelaunayCondition(Face*, unsigned int ttl = 0);
159 #else
160  bool applyDelaunayCondition(Face*);
161 #endif
162  void operateFlip(Edge*);
163  // Methods for manipulate lists of components
164  inline void removeVertexFromVertices(Vertex* v) {
165  for(std::vector<Vertex*>::iterator it = this->vertices.begin();
166  it != this->vertices.end(); it++) {
167  if((*it) == v) {
168  this->vertices.erase(it);
169  delete v;
170  it = this->vertices.end()-1;
171  }
172  }
173  }
174  inline void removeEdgeFromEdges(Edge* e) {
175  for(std::vector<Edge*>::iterator it = this->edges.begin();
176  it != this->edges.end(); it++) {
177  if((*it) == e) {
178  this->edges.erase(it);
179  delete e;
180  it = this->edges.end()-1;
181  }
182  }
183  }
184  inline void removeFaceFromFaces(Face* f) {
185  for(std::vector<Face*>::iterator it = this->faces.begin();
186  it != this->faces.end(); it++) {
187  if((*it) == f) {
188  this->faces.erase(it);
189  delete f;
190  it = this->faces.end()-1;
191  }
192  }
193  }
194  /*
195  * Replace given vertex coords by given values.
196  */
197  inline void moveVertex_pure(Vertex* v, Coordinates new_p) {
198  // Move the vertex
199  v->setX(new_p.x());
200  v->setY(new_p.y());
201  // Apply Delaunay Condition
202  std::vector<Face*> nei_faces;
203  Edge* edge = v->getEdge();
204  do {
205  nei_faces.push_back(edge->leftFace());
206  edge = edge->rotLeftEdge();
207  } while(edge != v->getEdge());
208 
209  for(Face* f : nei_faces) {
210 #ifdef DEBUG
211  assert(f != NULL);
212 #endif
213  this->applyDelaunayCondition(f);
214  }
215  }
216 };
217 
218 
219 
220 #endif
Generated on Sat Nov 1 2014 15:41:46 for Delaunator by   doxygen 1.8.1.2