MarkHalfEdge
public class HalfEdge
extends java.lang.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 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.
Constructor | Description |
---|---|
HalfEdge(Coordinate orig) |
Creates an edge originating from a given coordinate.
|
Modifier and Type | Method | Description |
---|---|---|
int |
compareAngularDirection(HalfEdge e) |
Implements the total order relation:
|
int |
compareTo(java.lang.Object obj) |
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.
|
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.
|
static HalfEdge |
init(HalfEdge e0,
HalfEdge e1) |
Initialize a symmetric pair of halfedges.
|
void |
insert(HalfEdge e) |
Inserts an edge
into the ring of edges around the origin vertex of this edge.
|
HalfEdge |
next() |
Gets the next edge CCW around the
destination vertex of this edge.
|
HalfEdge |
oNext() |
|
Coordinate |
orig() |
Gets the origin coordinate of this edge.
|
HalfEdge |
prev() |
Returns 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) |
|
HalfEdge |
sym() |
Gets the symmetric pair edge of this edge.
|
java.lang.String |
toString() |
Computes a string representation of a HalfEdge.
|
public HalfEdge(Coordinate orig)
orig
- the origin coordinatepublic static HalfEdge create(Coordinate p0, Coordinate p1)
p0
- a vertex coordinatep1
- a vertex coordinatepublic static HalfEdge init(HalfEdge e0, HalfEdge e1)
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.e0
- a halfedgee1
- a symmetric halfedgepublic Coordinate orig()
public Coordinate dest()
public HalfEdge sym()
public HalfEdge next()
public HalfEdge prev()
public void setNext(HalfEdge e)
public HalfEdge oNext()
public 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 e)
e
- the edge to insertpublic int compareTo(java.lang.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 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:
Orientation#computeOrientation(Coordinate, Coordinate, Coordinate)
function
can be used to determine the relative orientation of the vectors.
public double deltaX()
public double deltaY()
public java.lang.String toString()
toString
in class java.lang.Object
public int degree()
public HalfEdge prevNode()
Copyright © 2018. All rights reserved.