Class HalfEdge

Represents a directed component of an edge in an EdgeGraph. HalfEdges link vertices whose locations are defined by Coordinates. 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.

Inheritance

object

HalfEdge

MarkHalfEdge

Implements

IComparable<HalfEdge>

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.MemberwiseClone()

object.ReferenceEquals(object, object)

Namespace: NetTopologySuite.EdgeGraph

Assembly: NetTopologySuite.dll

Syntax

public class HalfEdge : IComparable<HalfEdge>

Constructors

HalfEdge(Coordinate)

Creates an edge originating from a given coordinate.

Declaration

public HalfEdge(Coordinate orig)

Parameters

Type	Name	Description
Coordinate	orig	the origin coordinate

Properties

DeltaX

The X component of the distance between the orig and dest vertices.

Declaration

[Obsolete("Use DirectionX")]
public double DeltaX { get; }

Property Value

Type	Description
double

DeltaY

The Y component of the distance between the orig and dest vertices.

Declaration

[Obsolete("Use DirectionY")]
public double DeltaY { get; }

Property Value

Type	Description
double

Dest

Gets the destination coordinate of this edge.

Declaration

public Coordinate Dest { get; }

Property Value

Type	Description
Coordinate

DirectionPt

Gets a value indicating 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.

Declaration

protected virtual Coordinate DirectionPt { get; }

Property Value

Type	Description
Coordinate	The direction point for the edge

IsEdgesSorted

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.

Declaration

public bool IsEdgesSorted { get; }

Property Value

Type	Description
bool	true if the origin edges are sorted correctly

Next

Gets the next edge CCW around the destination vertex of this edge. If the destination vertex has degree 1 then this is the Sym edge.

Declaration

public HalfEdge Next { get; }

Property Value

Type	Description
HalfEdge	The next outgoing edge CCW around the destination vertex

ONext

Gets the next edge CCW around the origin of this edge, with the same origin.
If the origin vertex has degree 1 then this is the edge itself.

e.ONext is equal to e.Sym.Next()

Declaration

public HalfEdge ONext { get; }

Property Value

Type	Description
HalfEdge	The next edge around the origin

Orig

Gets the origin coordinate of this edge.

Declaration

public Coordinate Orig { get; }

Property Value

Type	Description
Coordinate

Prev

Gets the previous edge CW around the origin vertex of this edge, with that vertex being its destination.

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.

Declaration

public HalfEdge Prev { get; }

Property Value

Type	Description
HalfEdge	The previous edge CW around the origin vertex

Sym

Gets or sets the symmetric (opposite) edge of this edge.

Declaration

public HalfEdge Sym { get; }

Property Value

Type	Description
HalfEdge

Methods

CompareAngularDirection(HalfEdge)

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 round off error.

Declaration

public int CompareAngularDirection(HalfEdge e)

Parameters

Type	Name	Description
HalfEdge	e

Returns

Type	Description
int

Remarks

A robust algorithm is:

1. compare the quadrants the edge vectors lie in. If the quadrants are different, it is trivial to determine which edge has a greater angle.
2. If the vectors lie in the same quadrant, the Index(Coordinate, Coordinate, Coordinate) function can be used to determine the relative orientation of the vectors.

CompareTo(HalfEdge)

Compares edges which originate at the same vertex based on the angle they make at their origin vertex with the positive X-axis. This allows sorting edges around their origin vertex in CCW order.

Declaration

public int CompareTo(HalfEdge e)

Parameters

Type	Name	Description
HalfEdge	e

Returns

Type	Description
int

Create(Coordinate, Coordinate)

Creates a HalfEdge pair representing an edge between two vertices located at coordinates p0 and p1.

Declaration

public static HalfEdge Create(Coordinate p0, Coordinate p1)

Parameters

Type	Name	Description
Coordinate	p0	a vertex coordinate
Coordinate	p1	a vertex coordinate

Returns

Type	Description
HalfEdge	the HalfEdge with origin at p0

Degree()

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

Declaration

public int Degree()

Returns

Type	Description
int	the degree of the origin vertex

Equals(Coordinate, Coordinate)

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

Declaration

public bool Equals(Coordinate p0, Coordinate p1)

Parameters

Type	Name	Description
Coordinate	p0	the origin vertex to test
Coordinate	p1	the destination vertex to test

Returns

Type	Description
bool	true if the vertices are equal to the ones of this edge

Find(Coordinate)

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

Declaration

public HalfEdge Find(Coordinate dest)

Parameters

Type	Name	Description
Coordinate	dest	the dest vertex to search for

Returns

Type	Description
HalfEdge	the edge with the required dest vertex, if it exists, or null

Init(HalfEdge)

Initializes this edge with e as Sym edge.

Declaration

[Obsolete("Use Link")]
protected virtual void Init(HalfEdge e)

Parameters

Type	Name	Description
HalfEdge	e	A symmetric half edge.

Init(HalfEdge, HalfEdge)

Initialize a symmetric pair of halfedges. Intended for use by EdgeGraph subclasses.

The edges are initialized to have each other as the Sym edge, and to have Next pointers which point to edge other. This effectively creates a graph containing a single edge.

Declaration

[Obsolete]
public static HalfEdge Init(HalfEdge e0, HalfEdge e1)

Parameters

Type	Name	Description
HalfEdge	e0	A halfedge
HalfEdge	e1	A symmetric halfedge

Returns

Type	Description
HalfEdge	The initialized edge e0

Insert(HalfEdge)

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.

Declaration

public void Insert(HalfEdge eAdd)

Parameters

Type	Name	Description
HalfEdge	eAdd	the edge to insert

Link(HalfEdge)

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

Declaration

public virtual void Link(HalfEdge sym)

Parameters

Type	Name	Description
HalfEdge	sym	The sym edge to link.

PrevNode()

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

Declaration

public HalfEdge PrevNode()

Returns

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

ToString()

Computes a string representation of a HalfEdge.

Declaration

public override string ToString()

Returns

Type	Description
string

Overrides

object.ToString()

ToStringNode()

Provides a string representation of the edges around the origin node of this edge.

Declaration

public string ToStringNode()

Returns

Type	Description
string	A string showing the edges around the origin

Remarks

Uses the subclass representation for each edge.

Implements

IComparable<T>