com.revolsys.jts.edgegraph

Class HalfEdge

java.lang.Object

com.revolsys.jts.edgegraph.HalfEdge

Direct Known Subclasses:

MarkHalfEdge

public class HalfEdge
extends Object

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

Author:

Martin Davis

Constructor Summary

Constructors

Constructor and Description
HalfEdge(Point orig) Creates an edge originating from a given coordinate.

Method Summary

Methods

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 X-axis.
static HalfEdge	create(Point p0, Point 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.
Point	dest() Gets the destination coordinate of this edge.
boolean	equals(Point p0, Point p1) Tests whether this edge has the given orig and dest vertices.
HalfEdge	find(Point dest) Finds the edge starting at the origin of this edge with the given dest vertex, if any.
protected void	init(HalfEdge e)
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()
Point	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.
String	toString() Computes a string representation of a HalfEdge.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

HalfEdge

public HalfEdge(Point orig)

Creates an edge originating from a given coordinate.

Parameters:

orig - the origin coordinate

Method Detail

create

public static HalfEdge create(Point p0,
              Point p1)

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

Parameters:

p0 - a vertex coordinate

p1 - a vertex coordinate

Returns:

the HalfEdge with origin at p0

init

public static HalfEdge init(HalfEdge e0,
            HalfEdge e1)

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.

Parameters:

e0 - a halfedge

e1 - a symmetric halfedge

Returns:

the initialized edge e0

compareAngularDirection

public int compareAngularDirection(HalfEdge e)

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 CGAlgorithms#computeOrientation(Point, Point, Point) function can be used to determine the relative orientation of the vectors.

compareTo

public 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 X-axis. This allows sorting edges around their origin vertex in CCW order.

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

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

dest

public Point dest()

Gets the destination coordinate of this edge.

Returns:

the destination coordinate

equals

public boolean equals(Point p0,
             Point p1)

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

public HalfEdge find(Point 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

init

protected void init(HalfEdge e)

insert

public void insert(HalfEdge e)

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

next

public HalfEdge 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

oNext

public HalfEdge oNext()

orig

public Point orig()

Gets the origin coordinate of this edge.

Returns:

the origin coordinate

prev

public HalfEdge prev()

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

Returns:

the previous edge to this one

prevNode

public HalfEdge 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

setNext

public void setNext(HalfEdge e)

sym

public HalfEdge sym()

Gets the symmetric pair edge of this edge.

Returns:

the symmetric pair edge

toString

public String toString()

Computes a string representation of a HalfEdge.

Overrides:

toString in class Object

Returns:

a string representation