geos::triangulate::quadedge::QuadEdge Class Reference

A class that represents the edge data structure which implements the quadedge algebra. More...

`#include <QuadEdge.h>`

## Public Member Functions

const QuadEdge & | getPrimary ()
| Gets the primary edge of this quadedge and its sym.
void | remove ()
| Marks this quadedge as being deleted.
bool | isLive () const
| Tests whether this edge has been deleted.
bool | isVisited () const
void | setVisited (bool v)
void | setNext (QuadEdge *p_next)
| Sets the connected edge.
const QuadEdge & | rot () const
| Gets the dual of this edge, directed from its right to its left.
QuadEdge & | rot ()
const QuadEdge & | invRot () const
| Gets the dual of this edge, directed from its left to its right.
QuadEdge & | invRot ()
const QuadEdge & | sym () const
| Gets the edge from the destination to the origin of this edge.
QuadEdge & | sym ()
const QuadEdge & | oNext () const
| Gets the next CCW edge around the origin of this edge.
QuadEdge & | oNext ()
const QuadEdge & | oPrev () const
| Gets the next CW edge around (from) the origin of this edge.
QuadEdge & | oPrev ()
const QuadEdge & | dNext () const
| Gets the next CCW edge around (into) the destination of this edge.
const QuadEdge & | dPrev () const
| Gets the next CW edge around (into) the destination of this edge.
QuadEdge & | dPrev ()
const QuadEdge & | lNext () const
| Gets the CCW edge around the left face following this edge.
QuadEdge & | lNext ()
const QuadEdge & | lPrev () const
| Gets the CCW edge around the left face before this edge.
QuadEdge & | lPrev ()
const QuadEdge & | rNext () const
| Gets the edge around the right face ccw following this edge.
const QuadEdge & | rPrev () const
| Gets the edge around the right face ccw before this edge.
void | setOrig (const Vertex &o)
| Sets the vertex for this edge's origin.
void | setDest (const Vertex &d)
| Sets the vertex for this edge's destination.
const Vertex & | orig () const
| Gets the vertex for the edge's origin.
const Vertex & | dest () const
| Gets the vertex for the edge's destination.
double | getLength () const
| Gets the length of the geometry of this quadedge.
bool | equalsNonOriented (const QuadEdge &qe) const
| Tests if this quadedge and another have the same line segment geometry, regardless of orientation.
bool | equalsOriented (const QuadEdge &qe) const
| Tests if this quadedge and another have the same line segment geometry with the same orientation.
std::unique_ptr< geom::LineSegment > | toLineSegment () const
| Creates a `geom::LineSegment` representing the geometry of this edge.

## Static Public Member Functions

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 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 three have the same left face after the connection is complete.
static void | splice (QuadEdge &a, QuadEdge &b)
| Splices two edges together or apart.
static void | swap (QuadEdge &e)
| Turns an edge counterclockwise inside its enclosing quadrilateral.

## Friends

class | QuadEdgeQuartet

## Detailed Description

A class that represents the edge data structure which implements the quadedge algebra.

The quadedge algebra was described in a well-known paper by Guibas and Stolfi, "Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams", ACM Transactions on Graphics, 4(2), 1985, 75-123.

Each edge object is part of a QuadEdgeQuartet of 4 edges, linked via relative memory addresses. Quadedges in a subdivision are linked together via their next references. The linkage between the quadedge quartets determines the topology of the subdivision.

The edge class does not contain separate information for vertice or faces; a vertex is implicitly defined as a ring of edges (created using the next field).

Author
  JTS: David Skea
  JTS: Martin Davis
  Benjamin Campbell

## Member Function Documentation

## connect()

QuadEdge * geos::triangulate::quadedge::QuadEdge::connect | ( | QuadEdge & | a,
|  | QuadEdge & | b,
|  | std::deque< QuadEdgeQuartet > & | edges )

static

Creates a new QuadEdge connecting the destination of a to the origin of b, in such a way that all three have the same left face after the connection is complete.

Additionally, the data pointers of the new edge are set.

Returns
  the new QuadEdge*

## dest()

const Vertex & geos::triangulate::quadedge::QuadEdge::dest | ( |  | ) | const

inline

Gets the vertex for the edge's destination.

Returns
  the destination vertex

References sym().

Referenced by getLength().

## dNext()

const QuadEdge & geos::triangulate::quadedge::QuadEdge::dNext | ( |  | ) | const

inline

Gets the next CCW edge around (into) the destination of this edge.

Returns
  the next destination edge.

References sym().

## dPrev()

const QuadEdge & geos::triangulate::quadedge::QuadEdge::dPrev | ( |  | ) | const

inline

Gets the next CW edge around (into) the destination of this edge.

Returns
  the previous destination edge.

References invRot().

## equalsNonOriented()

bool geos::triangulate::quadedge::QuadEdge::equalsNonOriented | ( | const QuadEdge & | qe | ) | const

Tests if this quadedge and another have the same line segment geometry, regardless of orientation.

Parameters

  qe | a quadege

Returns
  true if the quadedges are based on the same line segment regardless of orientation

## equalsOriented()

bool geos::triangulate::quadedge::QuadEdge::equalsOriented | ( | const QuadEdge & | qe | ) | const

Tests if this quadedge and another have the same line segment geometry with the same orientation.

Parameters

  qe | a quadege

Returns
  true if the quadedges are based on the same line segment

## getLength()

double geos::triangulate::quadedge::QuadEdge::getLength | ( |  | ) | const

inline

Gets the length of the geometry of this quadedge.

Returns
  the length of the quadedge

References dest(), and orig().

## getPrimary()

const QuadEdge & geos::triangulate::quadedge::QuadEdge::getPrimary | ( |  | ) |

Gets the primary edge of this quadedge and its sym.

The primary edge is the one for which the origin and destination coordinates are ordered according to the standard geom::Coordinate ordering

Returns
  the primary quadedge

## invRot()

const QuadEdge & geos::triangulate::quadedge::QuadEdge::invRot | ( |  | ) | const

inline

Gets the dual of this edge, directed from its left to its right.

Returns
  the inverse rotated edge.

Referenced by dPrev(), and lNext().

## isLive()

bool geos::triangulate::quadedge::QuadEdge::isLive | ( |  | ) | const

inline

Tests whether this edge has been deleted.

Returns
  true if this edge has not been deleted.

## lNext()

const QuadEdge & geos::triangulate::quadedge::QuadEdge::lNext | ( |  | ) | const

inline

Gets the CCW edge around the left face following this edge.

Returns
  the next left face edge.

References invRot().

## lPrev()

const QuadEdge & geos::triangulate::quadedge::QuadEdge::lPrev | ( |  | ) | const

inline

Gets the CCW edge around the left face before this edge.

Returns
  the previous left face edge.

References oNext().

## makeEdge()

QuadEdge * geos::triangulate::quadedge::QuadEdge::makeEdge | ( | const Vertex & | o,
|  | const Vertex & | d,
|  | std::deque< QuadEdgeQuartet > & | edges )

static

Creates a new QuadEdge quartet from `Vertex` o to `Vertex` d.

Parameters

  o | the origin Vertex
  d | the destination Vertex
  edges | a container in which to store the newly created quartet

Returns
  the new QuadEdge*,

## oNext()

const QuadEdge & geos::triangulate::quadedge::QuadEdge::oNext | ( |  | ) | const

inline

Gets the next CCW edge around the origin of this edge.

Returns
  the next linked edge.

Referenced by lPrev().

## oPrev()

const QuadEdge & geos::triangulate::quadedge::QuadEdge::oPrev | ( |  | ) | const

inline

Gets the next CW edge around (from) the origin of this edge.

Returns
  the previous edge.

References rot().

## orig()

const Vertex & geos::triangulate::quadedge::QuadEdge::orig | ( |  | ) | const

inline

Gets the vertex for the edge's origin.

Returns
  the origin vertex

Referenced by getLength().

## remove()

void geos::triangulate::quadedge::QuadEdge::remove | ( |  | ) |

Marks this quadedge as being deleted.

This does not free the memory used by this quadedge quartet, but indicates that this quadedge quartet no longer participates in a subdivision.

Note
  called "delete" in JTS

## rNext()

const QuadEdge & geos::triangulate::quadedge::QuadEdge::rNext | ( |  | ) | const

inline

Gets the edge around the right face ccw following this edge.

Returns
  the next right face edge.

References rot().

## rot()

const QuadEdge & geos::triangulate::quadedge::QuadEdge::rot | ( |  | ) | const

inline

Gets the dual of this edge, directed from its right to its left.

Returns
  the rotated edge

Referenced by oPrev(), and rNext().

## rPrev()

const QuadEdge & geos::triangulate::quadedge::QuadEdge::rPrev | ( |  | ) | const

inline

Gets the edge around the right face ccw before this edge.

Returns
  the previous right face edge.

References sym().

## setDest()

void geos::triangulate::quadedge::QuadEdge::setDest | ( | const Vertex & | d | ) |

inline

Sets the vertex for this edge's destination.

Parameters

  d | the destination vertex

References sym().

## setNext()

void geos::triangulate::quadedge::QuadEdge::setNext | ( | QuadEdge * | p_next | ) |

inline

Sets the connected edge.

Parameters

  p_next | edge

## setOrig()

void geos::triangulate::quadedge::QuadEdge::setOrig | ( | const Vertex & | o | ) |

inline

Sets the vertex for this edge's origin.

Parameters

  o | the origin vertex

## splice()

void geos::triangulate::quadedge::QuadEdge::splice | ( | QuadEdge & | a,
|  | QuadEdge & | b )

static

Splices two edges together or apart.

Splice affects the two edge rings around the origins of a and b, and, independently, the two edge rings around the left faces of a and b. In each case, (i) if the two rings are distinct, Splice will combine them into one, or (ii) if the two are the same ring, Splice will break it into two separate pieces. Thus, Splice can be used both to attach the two edges together, and to break them apart.

Parameters

  a | an edge to splice
  b | an edge to splice

## swap()

void geos::triangulate::quadedge::QuadEdge::swap | ( | QuadEdge & | e | ) |

static

Turns an edge counterclockwise inside its enclosing quadrilateral.

Parameters

  e | the quadedge to turn

## sym()

const QuadEdge & geos::triangulate::quadedge::QuadEdge::sym | ( |  | ) | const

inline

Gets the edge from the destination to the origin of this edge.

Returns
  the sym of the edge

Referenced by dest(), dNext(), rPrev(), and setDest().

## toLineSegment()

std::unique_ptr< geom::LineSegment > geos::triangulate::quadedge::QuadEdge::toLineSegment | ( |  | ) | const

Creates a `geom::LineSegment` representing the geometry of this edge.

Returns
  a LineSegment

The documentation for this class was generated from the following file:

- QuadEdge.h