geos::edgegraph::HalfEdge Class Reference

`#include <HalfEdge.h>`

Inheritance diagram for geos::edgegraph::HalfEdge:

## Public Member Functions

| HalfEdge (const geom::CoordinateXYZM &p_orig)
void | link (HalfEdge *p_sym)
const geom::CoordinateXYZM & | orig () const
const geom::CoordinateXYZM & | dest () const
double | directionX () const
double | directionY () const
HalfEdge * | sym () const
HalfEdge * | next () const
HalfEdge * | prev () const
HalfEdge * | oNext () const
void | setNext (HalfEdge *e)
HalfEdge * | find (const geom::CoordinateXY &dest)
bool | equals (const geom::CoordinateXY &p0, const geom::CoordinateXY &p1) const
void | insert (HalfEdge *eAdd)
bool | isEdgesSorted () const
int | compareAngularDirection (const HalfEdge *e) const
int | compareTo (const HalfEdge *e) const
int | degree ()
HalfEdge * | prevNode ()

## Static Public Member Functions

static HalfEdge * | create (const geom::CoordinateXYZM &p0, const geom::CoordinateXYZM &p1)
static void | toStringNode (const HalfEdge *he, std::ostream &os)

## Protected Member Functions

virtual const geom::CoordinateXYZM & | directionPt () const

## Friends

std::ostream & | operator<< (std::ostream &os, const HalfEdge &el)

## Detailed Description

Represents a directed component of an edge in an `EdgeGraph`. HalfEdges link vertices whose locations are defined by `geom::Coordinate`s. HalfEdges start at an origin vertex, and terminate at a destination vertex. HalfEdges always occur in symmetric pairs, with the `sym()` method giving access to the oppositely-oriented component. HalfEdges and the methods on them form an edge algebra, which can be used to traverse and query the topology of the graph formed by the edges.

To support graphs where the edges are sequences of coordinates each edge may also have a direction point supplied. This is used to determine the ordering of the edges around the origin. HalfEdges with the same origin are ordered so that the ring of edges formed by them is oriented CCW.

By design HalfEdges carry minimal information about the actual usage of the graph they represent. They can be subclassed to carry more information if required.

HalfEdges form a complete and consistent data structure by themselves, but an `EdgeGraph` is useful to allow retrieving edges by vertex and edge location, as well as ensuring edges are created and linked appropriately.

Author
  Martin Davis

## Constructor & Destructor Documentation

## HalfEdge()

geos::edgegraph::HalfEdge::HalfEdge | ( | const geom::CoordinateXYZM & | p_orig | ) |

inline

Creates a half-edge originating from a given coordinate.

Parameters

  p_orig | the origin coordinate

Referenced by compareAngularDirection(), create(), find(), insert(), link(), next(), oNext(), prev(), prevNode(), setNext(), and sym().

## Member Function Documentation

## compareAngularDirection()

int geos::edgegraph::HalfEdge::compareAngularDirection | ( | const HalfEdge * | e | ) | const

Implements the total order relation:

The angle of edge a is greater than the angle of edge b, where the angle of an edge is the angle made by the first segment of the edge with the positive x-axis

When applied to a list of edges originating at the same point, this produces a CCW ordering of the edges around the point.

Using the obvious algorithm of computing the angle is not robust, since the angle calculation is susceptible to roundoff error. A robust algorithm is:

- First, compare the quadrants the edge vectors lie in. If the quadrants are different, it is trivial to determine which edge has a greater angle.
- if the vectors lie in the same quadrant, the geom::Orientation::index() function can be used to determine the relative orientation of the vectors.

References compareAngularDirection(), and HalfEdge().

Referenced by compareAngularDirection().

## create()

HalfEdge * geos::edgegraph::HalfEdge::create | ( | const geom::CoordinateXYZM & | p0,
|  | const geom::CoordinateXYZM & | p1 )

static

Creates a HalfEdge pair, using the HalfEdge type of the graph subclass.

Parameters

  p0 | a vertex coordinate
  p1 | a vertex coordinate

Returns
  the HalfEdge with origin at p0

References HalfEdge().

## degree()

int geos::edgegraph::HalfEdge::degree | ( |  | ) |

Computes the degree of the origin vertex. The degree is the number of edges originating from the vertex.

Returns
  the degree of the origin vertex

## dest()

const geom::CoordinateXYZM & geos::edgegraph::HalfEdge::dest | ( |  | ) | const

inline

Gets the destination coordinate of this edge.

Returns
  the destination coordinate

Referenced by directionPt(), and find().

## directionPt()

virtual const geom::CoordinateXYZM & geos::edgegraph::HalfEdge::directionPt | ( |  | ) | const

inline protected virtual

Gets the direction point of this edge. In the base case this is the dest coordinate of the edge. Subclasses may override to allow a HalfEdge to represent an edge with more than two coordinates.

Returns
  the direction point for the edge

Reimplemented in geos::operation::overlayng::OverlayEdge.

References dest().

Referenced by directionX(), and directionY().

## directionX()

double geos::edgegraph::HalfEdge::directionX | ( |  | ) | const

inline

The X component of the direction vector.

Returns
  the X component of the direction vector

References directionPt().

## directionY()

double geos::edgegraph::HalfEdge::directionY | ( |  | ) | const

inline

The Y component of the direction vector.

Returns
  the Y component of the direction vector

References directionPt().

## equals()

bool geos::edgegraph::HalfEdge::equals | ( | const geom::CoordinateXY & | p0,
|  | const geom::CoordinateXY & | p1 ) const

Tests whether this edge has the given orig and dest vertices.

Parameters

  p0 | the origin vertex to test
  p1 | the destination vertex to test

Returns
  true if the vertices are equal to the ones of this edge

## find()

HalfEdge * geos::edgegraph::HalfEdge::find | ( | const geom::CoordinateXY & | dest | ) |

Finds the edge starting at the origin of this edge with the given dest vertex, if any.

Parameters

  dest | the dest vertex to search for

Returns
  the edge with the required dest vertex, if it exists, or null

References dest(), and HalfEdge().

## insert()

void geos::edgegraph::HalfEdge::insert | ( | HalfEdge * | eAdd | ) |

Inserts an edge into the ring of edges around the origin vertex of this edge, ensuring that the edges remain ordered CCW. The inserted edge must have the same origin as this edge.

Parameters

  eAdd | the edge to insert

References HalfEdge().

## isEdgesSorted()

bool geos::edgegraph::HalfEdge::isEdgesSorted | ( |  | ) | const

Tests whether the edges around the origin are sorted correctly. Note that edges must be strictly increasing, which implies no two edges can have the same direction point.

Returns
  true if the origin edges are sorted correctly

## link()

void geos::edgegraph::HalfEdge::link | ( | HalfEdge * | p_sym | ) |

Links this edge with its sym (opposite) edge. This must be done for each pair of edges created.

Parameters

  p_sym | the sym edge to link.

References HalfEdge().

## next()

HalfEdge * geos::edgegraph::HalfEdge::next | ( |  | ) | const

inline

Gets the next edge CCW around the destination vertex of this edge, with the dest vertex as its origin. If the vertex has degree 1 then this is the sym edge.

Returns
  the next edge

References HalfEdge().

## oNext()

HalfEdge * geos::edgegraph::HalfEdge::oNext | ( |  | ) | const

inline

Gets the next edge CCW around the origin of this edge, with the same origin.

e.oNext() is equal to e.sym().next()

Returns
  the next edge around the origin

References HalfEdge().

## orig()

const geom::CoordinateXYZM & geos::edgegraph::HalfEdge::orig | ( |  | ) | const

inline

Gets the origin coordinate of this edge.

Returns
  the origin coordinate

## prev()

HalfEdge * geos::edgegraph::HalfEdge::prev | ( |  | ) | const

Gets the edge previous to this one (with dest being the same as this orig).

It is always true that e.next().prev() == e

Note that this requires a scan of the origin edges, so may not be efficient for some uses.

Returns
  the previous edge to this one

References HalfEdge().

## prevNode()

HalfEdge * geos::edgegraph::HalfEdge::prevNode | ( |  | ) |

Finds the first node previous to this edge, if any. A node has degree <> 2. If no such node exists (i.e. the edge is part of a ring) then null is returned.

Returns
  an edge originating at the node prior to this edge, if any, or null if no node exists

References HalfEdge().

## setNext()

void geos::edgegraph::HalfEdge::setNext | ( | HalfEdge * | e | ) |

inline

Sets the next edge CCW around the destination vertex of this edge.

Parameters

  e | the next edge

References HalfEdge().

## sym()

HalfEdge * geos::edgegraph::HalfEdge::sym | ( |  | ) | const

inline

Gets the symmetric pair edge of this edge.

Returns
  the symmetric pair edge

References HalfEdge().

Referenced by geos::operation::overlayng::OverlayEdge::addCoordinates().

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

- HalfEdge.h