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()

static 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

◆ 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 oNext(), and 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(), and oNext().

◆ 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

◆ 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 rNext().

◆ 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 oNext(), and rot().

◆ 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 sym().

◆ makeEdge()

static 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 dNext(), dPrev(), lNext(), oPrev(), rNext(), and rPrev().

◆ 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 oNext(), and rot().

◆ orig()

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

inline

Gets the vertex for the edge's origin.

Returns: the origin vertex

◆ 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 invRot(), and oNext().

◆ 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 lNext(), and oPrev().

◆ 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 oNext().

◆ setDest()

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

inline

Sets the vertex for this edge's destination.

Parameters

d	the destination vertex

◆ 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()

static 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()

static 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 dNext(), and lPrev().

◆ 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

Public Member Functions

Static Public Member Functions

Friends

Detailed Description

Member Function Documentation

◆ connect()

◆ dest()

◆ dNext()

◆ dPrev()

◆ equalsNonOriented()

◆ equalsOriented()

◆ getLength()

◆ getPrimary()

◆ invRot()

◆ isLive()

◆ lNext()

◆ lPrev()

◆ makeEdge()

◆ oNext()

◆ oPrev()

◆ orig()

◆ remove()

◆ rNext()

◆ rot()

◆ rPrev()

◆ setDest()

◆ setNext()

◆ setOrig()

◆ splice()

◆ swap()

◆ sym()

◆ toLineSegment()