GEOS 3.9.1
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
28namespace geos {
29namespace triangulate { //geos.triangulate
30namespace quadedge { //geos.triangulate.quadedge
31
32
33class GEOS_DLL QuadEdgeQuartet;
34
54class GEOS_DLL QuadEdge {
55 friend class QuadEdgeQuartet;
56public:
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
101private:
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
122public:
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
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
439GEOS_DLL std::ostream& operator<< (std::ostream& os, const QuadEdge* e);
440
441} //namespace geos.triangulate.quadedge
442} //namespace geos.triangulate
443} //namespace geos
444
445#endif //GEOS_TRIANGULATE_QUADEDGE_QUADEDGE_H
A class that represents the edge data structure which implements the quadedge algebra.
Definition: QuadEdge.h:54
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.
void setOrig(const Vertex &o)
Sets the vertex for this edge's origin.
Definition: QuadEdge.h:363
bool equalsOriented(const QuadEdge &qe) const
Tests if this quadedge and another have the same line segment geometry with the same orientation.
static QuadEdge * makeEdge(const Vertex &o, const Vertex &d, std::deque< QuadEdgeQuartet > &edges)
Creates a new QuadEdge quartet from Vertex o to Vertex d.
void setDest(const Vertex &d)
Sets the vertex for this edge's destination.
Definition: QuadEdge.h:374
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 & dNext() const
Gets the next CCW edge around (into) the destination of this edge.
Definition: QuadEdge.h:276
static void swap(QuadEdge &e)
Turns an edge counterclockwise inside its enclosing quadrilateral.
const QuadEdge & dPrev() const
Gets the next CW edge around (into) the destination of this edge.
Definition: QuadEdge.h:287
const QuadEdge & rot() const
Gets the dual of this edge, directed from its right to its left.
Definition: QuadEdge.h:191
const QuadEdge & oPrev() const
Gets the next CW edge around (from) the origin of this edge.
Definition: QuadEdge.h:259
const QuadEdge & rNext() const
Gets the edge around the right face ccw following this edge.
Definition: QuadEdge.h:338
void remove()
Marks this quadedge as being deleted.
const QuadEdge & rPrev() const
Gets the edge around the right face ccw before this edge.
Definition: QuadEdge.h:349
bool isLive() const
Tests whether this edge has been deleted.
Definition: QuadEdge.h:153
const Vertex & orig() const
Gets the vertex for the edge's origin.
Definition: QuadEdge.h:385
static void splice(QuadEdge &a, QuadEdge &b)
Splices two edges together or apart.
double getLength() const
Gets the length of the geometry of this quadedge.
Definition: QuadEdge.h:407
const QuadEdge & sym() const
Gets the edge from the destination to the origin of this edge.
Definition: QuadEdge.h:225
bool equalsNonOriented(const QuadEdge &qe) const
Tests if this quadedge and another have the same line segment geometry, regardless of orientation.
const Vertex & dest() const
Gets the vertex for the edge's destination.
Definition: QuadEdge.h:396
const QuadEdge & lPrev() const
Gets the CCW edge around the left face before this edge.
Definition: QuadEdge.h:321
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
void setNext(QuadEdge *p_next)
Sets the connected edge.
Definition: QuadEdge.h:175
const QuadEdge & invRot() const
Gets the dual of this edge, directed from its left to its right.
Definition: QuadEdge.h:208
Models a site (node) in a QuadEdgeSubdivision.
Definition: Vertex.h:60
Basic namespace for all GEOS functionalities.
Definition: IndexedNestedRingTester.h:26