GEOS  3.9.0dev
QuadEdge.h
1 /**********************************************************************
2  *
3  * GEOS - Geometry Engine Open Source
4  * http://geos.osgeo.org
5  *
6  * Copyright (C) 2012 Excensus LLC.
7  * Copyright (C) 2019 Daniel Baston
8  *
9  * This is free software; you can redistribute and/or modify it under
10  * the terms of the GNU Lesser General Licence as published
11  * by the Free Software Foundation.
12  * See the COPYING file for more information.
13  *
14  **********************************************************************
15  *
16  * Last port: triangulate/quadedge/QuadEdge.java r524
17  *
18  **********************************************************************/
19 
20 #ifndef GEOS_TRIANGULATE_QUADEDGE_QUADEDGE_H
21 #define GEOS_TRIANGULATE_QUADEDGE_QUADEDGE_H
22 
23 #include <memory>
24 
25 #include <geos/triangulate/quadedge/Vertex.h>
26 #include <geos/geom/LineSegment.h>
27 
28 namespace geos {
29 namespace triangulate { //geos.triangulate
30 namespace quadedge { //geos.triangulate.quadedge
31 
32 
33 class GEOS_DLL QuadEdgeQuartet;
34 
54 class GEOS_DLL QuadEdge {
55  friend class QuadEdgeQuartet;
56 public:
65  static QuadEdge* makeEdge(const Vertex& o, const Vertex & d, std::deque<QuadEdgeQuartet> & edges);
66 
76  static QuadEdge* connect(QuadEdge& a, QuadEdge& b, std::deque<QuadEdgeQuartet> & edges);
77 
92  static void splice(QuadEdge& a, QuadEdge& b);
93 
99  static void swap(QuadEdge& e);
100 
101 private:
103  Vertex vertex; // The vertex that this edge represents
104  QuadEdge* next; // A reference to a connected edge
105 
106  int8_t num; // the position of the QuadEdge in the quartet (0-3)
107 
108  bool isAlive;
109  bool visited;
110 
115  explicit QuadEdge(int8_t _num) :
116  next(nullptr),
117  num(_num),
118  isAlive(true),
119  visited(false) {
120  }
121 
122 public:
132  const QuadEdge& getPrimary();
133 
145  void remove();
146 
152  inline bool
153  isLive() const
154  {
155  return isAlive;
156  }
157 
158  inline bool
159  isVisited() const
160  {
161  return visited;
162  }
163 
164  inline void
165  setVisited(bool v) {
166  visited = v;
167  }
168 
174  inline void
175  setNext(QuadEdge* p_next)
176  {
177  this->next = p_next;
178  }
179 
180  /***************************************************************************
181  * QuadEdge Algebra
182  ***************************************************************************
183  */
184 
190  inline const QuadEdge&
191  rot() const
192  {
193  return (num < 3) ? *(this + 1) : *(this - 3);
194  }
195 
196  inline QuadEdge&
197  rot()
198  {
199  return (num < 3) ? *(this + 1) : *(this - 3);
200  }
201 
207  inline const QuadEdge&
208  invRot() const
209  {
210  return (num > 0) ? *(this - 1) : *(this + 3);
211  }
212 
213  inline QuadEdge&
214  invRot()
215  {
216  return (num > 0) ? *(this - 1) : *(this + 3);
217  }
218 
224  inline const QuadEdge&
225  sym() const
226  {
227  return (num < 2) ? *(this + 2) : *(this - 2);
228  }
229 
230  inline QuadEdge&
231  sym()
232  {
233  return (num < 2) ? *(this + 2) : *(this - 2);
234  }
235 
241  inline const QuadEdge&
242  oNext() const
243  {
244  return *next;
245  }
246 
247  inline QuadEdge&
248  oNext()
249  {
250  return *next;
251  }
252 
258  inline const QuadEdge&
259  oPrev() const
260  {
261  return rot().oNext().rot();
262  }
263 
264  inline QuadEdge&
265  oPrev()
266  {
267  return rot().oNext().rot();
268  }
269 
275  inline const QuadEdge&
276  dNext() const
277  {
278  return sym().oNext().sym();
279  }
280 
286  inline const QuadEdge&
287  dPrev() const
288  {
289  return invRot().oNext().invRot();
290  }
291 
292  inline QuadEdge&
293  dPrev()
294  {
295  return invRot().oNext().invRot();
296  }
297 
303  inline const QuadEdge&
304  lNext() const
305  {
306  return invRot().oNext().rot();
307  }
308 
309  inline QuadEdge&
310  lNext()
311  {
312  return invRot().oNext().rot();
313  }
314 
320  inline const QuadEdge&
321  lPrev() const
322  {
323  return oNext().sym();
324  }
325 
326  inline QuadEdge&
327  lPrev()
328  {
329  return oNext().sym();
330  }
331 
337  inline const QuadEdge&
338  rNext() const
339  {
340  return rot().oNext().invRot();
341  }
342 
348  inline const QuadEdge&
349  rPrev() const
350  {
351  return sym().oNext();
352  }
353 
354  /***********************************************************************************************
355  * Data Access
356  **********************************************************************************************/
362  inline void
363  setOrig(const Vertex& o)
364  {
365  vertex = o;
366  }
367 
373  inline void
374  setDest(const Vertex& d)
375  {
376  sym().setOrig(d);
377  }
378 
384  const Vertex&
385  orig() const
386  {
387  return vertex;
388  }
389 
395  const Vertex&
396  dest() const
397  {
398  return sym().orig();
399  }
400 
406  inline double
407  getLength() const
408  {
409  return orig().getCoordinate().distance(dest().getCoordinate());
410  }
411 
419  bool equalsNonOriented(const QuadEdge& qe) const;
420 
428  bool equalsOriented(const QuadEdge& qe) const;
429 
436  std::unique_ptr<geom::LineSegment> toLineSegment() const;
437 };
438 
439 
440 } //namespace geos.triangulate.quadedge
441 } //namespace geos.triangulate
442 } //namespace geos
443 
444 #endif //GEOS_TRIANGULATE_QUADEDGE_QUADEDGE_H
445 
void setNext(QuadEdge *p_next)
Sets the connected edge.
Definition: QuadEdge.h:175
void setOrig(const Vertex &o)
Sets the vertex for this edge's origin.
Definition: QuadEdge.h:363
Models a site (node) in a QuadEdgeSubdivision.
Definition: Vertex.h:60
const QuadEdge & dPrev() const
Gets the next CW edge around (into) the destination of this edge.
Definition: QuadEdge.h:287
const QuadEdge & sym() const
Gets the edge from the destination to the origin of this edge.
Definition: QuadEdge.h:225
const Vertex & orig() const
Gets the vertex for the edge's origin.
Definition: QuadEdge.h:385
const QuadEdge & rot() const
Gets the dual of this edge, directed from its right to its left.
Definition: QuadEdge.h:191
const QuadEdge & rNext() const
Gets the edge around the right face ccw following this edge.
Definition: QuadEdge.h:338
const QuadEdge & lNext() const
Gets the CCW edge around the left face following this edge.
Definition: QuadEdge.h:304
const QuadEdge & oNext() const
Gets the next CCW edge around the origin of this edge.
Definition: QuadEdge.h:242
bool isLive() const
Tests whether this edge has been deleted.
Definition: QuadEdge.h:153
Basic namespace for all GEOS functionalities.
Definition: IndexedNestedRingTester.h:26
const QuadEdge & invRot() const
Gets the dual of this edge, directed from its left to its right.
Definition: QuadEdge.h:208
void setDest(const Vertex &d)
Sets the vertex for this edge's destination.
Definition: QuadEdge.h:374
const QuadEdge & oPrev() const
Gets the next CW edge around (from) the origin of this edge.
Definition: QuadEdge.h:259
double getLength() const
Gets the length of the geometry of this quadedge.
Definition: QuadEdge.h:407
const Vertex & dest() const
Gets the vertex for the edge's destination.
Definition: QuadEdge.h:396
A class that represents the edge data structure which implements the quadedge algebra.
Definition: QuadEdge.h:54
const QuadEdge & lPrev() const
Gets the CCW edge around the left face before this edge.
Definition: QuadEdge.h:321
const QuadEdge & dNext() const
Gets the next CCW edge around (into) the destination of this edge.
Definition: QuadEdge.h:276
const QuadEdge & rPrev() const
Gets the edge around the right face ccw before this edge.
Definition: QuadEdge.h:349