public class HalfEdge extends Object
EdgeGraph
.
HalfEdges link vertices whose locations are defined by 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 oppositelyoriented 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.
Constructor and Description 

HalfEdge(Coordinate orig)
Creates a halfedge originating from a given coordinate.

Modifier and Type  Method and Description 

int 
compareAngularDirection(HalfEdge e)
Implements the total order relation:

int 
compareTo(Object obj)
Compares edges which originate at the same vertex
based on the angle they make at their origin vertex with the positive Xaxis.

static HalfEdge 
create(Coordinate p0,
Coordinate p1)
Creates a HalfEdge pair representing an edge
between two vertices located at coordinates p0 and p1.

int 
degree()
Computes the degree of the origin vertex.

Coordinate 
dest()
Gets the destination coordinate of this edge.

boolean 
equals(Coordinate p0,
Coordinate p1)
Tests whether this edge has the given orig and dest vertices.

HalfEdge 
find(Coordinate dest)
Finds the edge starting at the origin of this edge
with the given dest vertex,
if any.

void 
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.

boolean 
isEdgesSorted()
Tests whether the edges around the origin
are sorted correctly.

void 
link(HalfEdge sym)
Links this edge with its sym (opposite) edge.

HalfEdge 
next()
Gets the next edge CCW around the
destination vertex of this edge,
with the dest vertex as its origin.

HalfEdge 
oNext()
Gets the next edge CCW around the origin of this edge,
with the same origin.

Coordinate 
orig()
Gets the origin coordinate of this edge.

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

HalfEdge 
prevNode()
Finds the first node previous to this edge, if any.

void 
setNext(HalfEdge e)
Sets the next edge CCW around the destination vertex of this edge.

HalfEdge 
sym()
Gets the symmetric pair edge of this edge.

String 
toString()
Computes a string representation of a HalfEdge.

String 
toStringNode() 
public HalfEdge(Coordinate orig)
orig
 the origin coordinatepublic static HalfEdge create(Coordinate p0, Coordinate p1)
p0
 a vertex coordinatep1
 a vertex coordinatepublic void link(HalfEdge sym)
e
 the sym edge to link.public Coordinate orig()
public Coordinate dest()
public HalfEdge sym()
public HalfEdge next()
public HalfEdge prev()
public HalfEdge oNext()
public void setNext(HalfEdge e)
e
 the next edgepublic HalfEdge find(Coordinate dest)
dest
 the dest vertex to search forpublic boolean equals(Coordinate p0, Coordinate p1)
p0
 the origin vertex to testp1
 the destination vertex to testpublic void insert(HalfEdge eAdd)
eAdd
 the edge to insertpublic boolean isEdgesSorted()
public int compareTo(Object obj)
public int compareAngularDirection(HalfEdge e)
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 xaxis
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:
Orientation.index(Coordinate, Coordinate, Coordinate)
function
can be used to determine the relative orientation of the vectors.
public String toString()
public String toStringNode()
public int degree()
public HalfEdge prevNode()
Copyright © 2020. All rights reserved.