GEOS  3.13.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 #pragma once
21 
22 #include <memory>
23 
24 #include <geos/triangulate/quadedge/Vertex.h>
25 #include <geos/geom/LineSegment.h>
26 
27 namespace geos {
28 namespace triangulate { //geos.triangulate
29 namespace quadedge { //geos.triangulate.quadedge
30 
31 
32 class GEOS_DLL QuadEdgeQuartet;
33 
53 class GEOS_DLL QuadEdge {
54  friend class QuadEdgeQuartet;
55 public:
64  static QuadEdge* makeEdge(const Vertex& o, const Vertex & d, std::deque<QuadEdgeQuartet> & edges);
65 
75  static QuadEdge* connect(QuadEdge& a, QuadEdge& b, std::deque<QuadEdgeQuartet> & edges);
76 
91  static void splice(QuadEdge& a, QuadEdge& b);
92 
98  static void swap(QuadEdge& e);
99 
100 private:
102  Vertex vertex; // The vertex that this edge represents
103  QuadEdge* next; // A reference to a connected edge
104 
105  int8_t num; // the position of the QuadEdge in the quartet (0-3)
106 
107  bool isAlive;
108  bool visited;
109 
114  explicit QuadEdge(int8_t _num) :
115  next(nullptr),
116  num(_num),
117  isAlive(true),
118  visited(false) {
119  }
120 
121 public:
132 
144  void remove();
145 
151  inline bool
152  isLive() const
153  {
154  return isAlive;
155  }
156 
157  inline bool
158  isVisited() const
159  {
160  return visited;
161  }
162 
163  inline void
164  setVisited(bool v) {
165  visited = v;
166  }
167 
173  inline void
174  setNext(QuadEdge* p_next)
175  {
176  this->next = p_next;
177  }
178 
179  /***************************************************************************
180  * QuadEdge Algebra
181  ***************************************************************************
182  */
183 
189  inline const QuadEdge&
190  rot() const
191  {
192  return (num < 3) ? *(this + 1) : *(this - 3);
193  }
194 
195  inline QuadEdge&
196  rot()
197  {
198  return (num < 3) ? *(this + 1) : *(this - 3);
199  }
200 
206  inline const QuadEdge&
207  invRot() const
208  {
209  return (num > 0) ? *(this - 1) : *(this + 3);
210  }
211 
212  inline QuadEdge&
213  invRot()
214  {
215  return (num > 0) ? *(this - 1) : *(this + 3);
216  }
217 
223  inline const QuadEdge&
224  sym() const
225  {
226  return (num < 2) ? *(this + 2) : *(this - 2);
227  }
228 
229  inline QuadEdge&
230  sym()
231  {
232  return (num < 2) ? *(this + 2) : *(this - 2);
233  }
234 
240  inline const QuadEdge&
241  oNext() const
242  {
243  return *next;
244  }
245 
246  inline QuadEdge&
247  oNext()
248  {
249  return *next;
250  }
251 
257  inline const QuadEdge&
258  oPrev() const
259  {
260  return rot().oNext().rot();
261  }
262 
263  inline QuadEdge&
264  oPrev()
265  {
266  return rot().oNext().rot();
267  }
268 
274  inline const QuadEdge&
275  dNext() const
276  {
277  return sym().oNext().sym();
278  }
279 
285  inline const QuadEdge&
286  dPrev() const
287  {
288  return invRot().oNext().invRot();
289  }
290 
291  inline QuadEdge&
292  dPrev()
293  {
294  return invRot().oNext().invRot();
295  }
296 
302  inline const QuadEdge&
303  lNext() const
304  {
305  return invRot().oNext().rot();
306  }
307 
308  inline QuadEdge&
309  lNext()
310  {
311  return invRot().oNext().rot();
312  }
313 
319  inline const QuadEdge&
320  lPrev() const
321  {
322  return oNext().sym();
323  }
324 
325  inline QuadEdge&
326  lPrev()
327  {
328  return oNext().sym();
329  }
330 
336  inline const QuadEdge&
337  rNext() const
338  {
339  return rot().oNext().invRot();
340  }
341 
347  inline const QuadEdge&
348  rPrev() const
349  {
350  return sym().oNext();
351  }
352 
353  /***********************************************************************************************
354  * Data Access
355  **********************************************************************************************/
361  inline void
362  setOrig(const Vertex& o)
363  {
364  vertex = o;
365  }
366 
372  inline void
373  setDest(const Vertex& d)
374  {
375  sym().setOrig(d);
376  }
377 
383  const Vertex&
384  orig() const
385  {
386  return vertex;
387  }
388 
394  const Vertex&
395  dest() const
396  {
397  return sym().orig();
398  }
399 
405  inline double
406  getLength() const
407  {
408  return orig().getCoordinate().distance(dest().getCoordinate());
409  }
410 
418  bool equalsNonOriented(const QuadEdge& qe) const;
419 
427  bool equalsOriented(const QuadEdge& qe) const;
428 
435  std::unique_ptr<geom::LineSegment> toLineSegment() const;
436 };
437 
438 GEOS_DLL std::ostream& operator<< (std::ostream& os, const QuadEdge* e);
439 
440 } //namespace geos.triangulate.quadedge
441 } //namespace geos.triangulate
442 } //namespace geos
443 
A class that represents the edge data structure which implements the quadedge algebra.
Definition: QuadEdge.h:53
const QuadEdge & invRot() const
Gets the dual of this edge, directed from its left to its right.
Definition: QuadEdge.h:207
const QuadEdge & lPrev() const
Gets the CCW edge around the left face before this edge.
Definition: QuadEdge.h:320
void setOrig(const Vertex &o)
Sets the vertex for this edge's origin.
Definition: QuadEdge.h:362
const QuadEdge & dPrev() const
Gets the next CW edge around (into) the destination of this edge.
Definition: QuadEdge.h:286
const QuadEdge & oNext() const
Gets the next CCW edge around the origin of this edge.
Definition: QuadEdge.h:241
bool equalsOriented(const QuadEdge &qe) const
Tests if this quadedge and another have the same line segment geometry with the same orientation.
void setDest(const Vertex &d)
Sets the vertex for this edge's destination.
Definition: QuadEdge.h:373
const QuadEdge & rot() const
Gets the dual of this edge, directed from its right to its left.
Definition: QuadEdge.h:190
static QuadEdge * makeEdge(const Vertex &o, const Vertex &d, std::deque< QuadEdgeQuartet > &edges)
Creates a new QuadEdge quartet from Vertex o to Vertex d.
static void swap(QuadEdge &e)
Turns an edge counterclockwise inside its enclosing quadrilateral.
const QuadEdge & getPrimary()
Gets the primary edge of this quadedge and its sym.
std::unique_ptr< geom::LineSegment > toLineSegment() const
Creates a geom::LineSegment representing the geometry of this edge.
const QuadEdge & rPrev() const
Gets the edge around the right face ccw before this edge.
Definition: QuadEdge.h:348
const Vertex & dest() const
Gets the vertex for the edge's destination.
Definition: QuadEdge.h:395
const QuadEdge & rNext() const
Gets the edge around the right face ccw following this edge.
Definition: QuadEdge.h:337
void remove()
Marks this quadedge as being deleted.
const QuadEdge & sym() const
Gets the edge from the destination to the origin of this edge.
Definition: QuadEdge.h:224
const QuadEdge & oPrev() const
Gets the next CW edge around (from) the origin of this edge.
Definition: QuadEdge.h:258
bool isLive() const
Tests whether this edge has been deleted.
Definition: QuadEdge.h:152
static void splice(QuadEdge &a, QuadEdge &b)
Splices two edges together or apart.
static QuadEdge * connect(QuadEdge &a, QuadEdge &b, std::deque< QuadEdgeQuartet > &edges)
Creates a new QuadEdge connecting the destination of a to the origin of b, in such a way that all thr...
const QuadEdge & lNext() const
Gets the CCW edge around the left face following this edge.
Definition: QuadEdge.h:303
double getLength() const
Gets the length of the geometry of this quadedge.
Definition: QuadEdge.h:406
const QuadEdge & dNext() const
Gets the next CCW edge around (into) the destination of this edge.
Definition: QuadEdge.h:275
const Vertex & orig() const
Gets the vertex for the edge's origin.
Definition: QuadEdge.h:384
bool equalsNonOriented(const QuadEdge &qe) const
Tests if this quadedge and another have the same line segment geometry, regardless of orientation.
void setNext(QuadEdge *p_next)
Sets the connected edge.
Definition: QuadEdge.h:174
Models a site (node) in a QuadEdgeSubdivision.
Definition: Vertex.h:60
Basic namespace for all GEOS functionalities.
Definition: Angle.h:25