Class HalfEdge
- Direct Known Subclasses:
MarkHalfEdge
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 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.
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.
-
Field Summary
Fields -
Constructor Summary
ConstructorsConstructorDescriptionHalfEdge
(Coordinate orig) Creates an edge originating from a given coordinate. -
Method Summary
Modifier and TypeMethodDescriptionint
Implements the total order relation:int
Compares edges which originate at the same vertex based on the angle they make at their origin vertex with the positive X-axis.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.double
deltaX()
The X component of the distance between the orig and dest vertices.double
deltaY()
The Y component of the distance between the orig and dest vertices.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.find
(Coordinate dest) Finds the edge starting at the origin of this edge with the given dest vertex, if any.protected void
static HalfEdge
Initialize a symmetric pair of halfedges.void
Inserts an edge into the ring of edges around the origin vertex of this edge.private void
Insert an edge with the same origin after this one.next()
Gets the next edge CCW around the destination vertex of this edge.oNext()
orig()
Gets the origin coordinate of this edge.prev()
Returns the edge previous to this one (with dest being the same as this orig).prevNode()
Finds the first node previous to this edge, if any.void
private void
Sets the sym edge.sym()
Gets the symmetric pair edge of this edge.toString()
Computes a string representation of a HalfEdge.
-
Field Details
-
orig
-
sym
-
next
-
-
Constructor Details
-
HalfEdge
Creates an edge originating from a given coordinate.- Parameters:
orig
- the origin coordinate
-
-
Method Details
-
create
Creates a HalfEdge pair representing an edge between two vertices located at coordinates p0 and p1.- Parameters:
p0
- a vertex coordinatep1
- a vertex coordinate- Returns:
- the HalfEdge with origin at p0
-
init
Initialize a symmetric pair of halfedges. Intended for use byEdgeGraph
subclasses. The edges are initialized to have each other as thesym
edge, and to havenext
pointers which point to edge other. This effectively creates a graph containing a single edge.- Parameters:
e0
- a halfedgee1
- a symmetric halfedge- Returns:
- the initialized edge e0
-
init
-
orig
Gets the origin coordinate of this edge.- Returns:
- the origin coordinate
-
dest
Gets the destination coordinate of this edge.- Returns:
- the destination coordinate
-
sym
Gets the symmetric pair edge of this edge.- Returns:
- the symmetric pair edge
-
setSym
Sets the sym edge.- Parameters:
e
- the sym edge to set
-
next
Gets the next edge CCW around the destination vertex of this edge. If the vertex has degree 1 then this is the sym edge.- Returns:
- the next edge
-
prev
Returns the edge previous to this one (with dest being the same as this orig).- Returns:
- the previous edge to this one
-
setNext
-
oNext
-
find
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
-
equals
Tests whether this edge has the given orig and dest vertices.- Parameters:
p0
- the origin vertex to testp1
- the destination vertex to test- Returns:
- true if the vertices are equal to the ones of this edge
-
insert
Inserts an edge into the ring of edges around the origin vertex of this edge. The inserted edge must have the same origin as this edge.- Parameters:
e
- the edge to insert
-
insertAfter
Insert an edge with the same origin after this one. Assumes that the inserted edge is in the correct position around the ring.- Parameters:
e
- the edge to insert (with same origin)
-
compareTo
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. -
compareAngularDirection
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
invalid reference
Orientation#computeOrientation(Coordinate, Coordinate, Coordinate)
-
deltaX
public double deltaX()The X component of the distance between the orig and dest vertices.- Returns:
- the X component of the edge length
-
deltaY
public double deltaY()The Y component of the distance between the orig and dest vertices.- Returns:
- the Y component of the edge length
-
toString
Computes a string representation of a HalfEdge. -
degree
public int 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
-
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.- Returns:
- an edge originating at the node prior to this edge, if any, or null if no node exists
-