edu.uci.ics.dillenco.simplegraph01
Class QEdge

java.lang.Object
  edu.uci.ics.dillenco.simplegraph01.QEdge

public class QEdge
extends Object

A QEdge represents a QuadEdge, in the sense of the Guibas-Stolfi quadedge structure.

Essentially a QEdge represent four half-edges, which may be thought of as rotations of one another. One of the half-edges is the canonical representative, e₀ The remaining three half-edges are e₀Rot¹, e₀Rot², and e₀Rot³.

Field Summary

int

permID

Constructor Summary

QEdge(Node node0, Node node1, Graph g)

Method Summary

String	charName(Graph g)
HalfEdge	getHalfEdge(int r) Return a HalfEdge representing the the half-edge e0Rotr.
Node	getHead(int r) Return the the head of the half-edge e0Rotr, which must be part of a directed edge.
HalfEdge	getNext(int r) Return a HalfEdge representing the next half edge having the same origin node as the HalfEdge e0Rotr.
(package private) QEdge	getNextQEdge()
Node	getOppNode(Node v) Returns the node opposite v along this QEdge.
Node	getOrigin(int r) Return the origin node of the HalfEdge e0Rotr.
(package private) int	getRotationIndex(Node v) Returns the rotation index of node v.
Node	getTail(int r) Return the the tail of the half-edge e0Rotr, which must be part of a directed edge.
boolean	isDirected(int r) Return whether the half-edge e0Rotr.
boolean	isHead(int r) Return whether the origin of the half-edge e0Rotr is the head of the edge containing this half-edge (i.e., whether this edge is directed toward the origin of the half-edge).
boolean	isTail(int r) Return whether the origin of the half-edge e0Rotr is the tail of the edge containing this half-edge (i.e., whether this edge is directed away from the origin of the half-edge).
(package private) void	linkBefore(int curRot, HalfEdge next) Link the half edge (this,curRot) before the specified half edge (nextQEdge,nextRot).
(package private) void	linkSolo(int curRot) Link the specified half edge to itself.
String	toString()
(package private) void	unLink(int curRot) unLink The half edge(int curRot)

Methods inherited from class java.lang.Object

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

Field Detail

permID

public final int permID

Constructor Detail

QEdge

QEdge(Node node0,
      Node node1,
      Graph g)

Method Detail

toString

public String toString()

Overrides:

toString in class Object

charName

public String charName(Graph g)

getOppNode

public Node getOppNode(Node v)

Returns the node opposite v along this QEdge. In the GS formulation, if v is e₀Rot^r.Origin, the vertex returned is e₀Rot^(r+2)%4.Origin. If no such r exists, a GraphCheckException is thrown.

Parameters:

v - the Node whose opposite end is to be returned.

Returns:

the Node opposite v on this QEdge.

getNext

public HalfEdge getNext(int r)

Return a HalfEdge representing the next half edge having the same origin node as the HalfEdge e₀Rot^r. The value returned by this method is the value of the Next field in the GS formulation, which is the half edge e₀Rot^rOnext.

Parameters:

r - the rotation index, in the range 0..3.

getOrigin

public Node getOrigin(int r)

Return the origin node of the HalfEdge e₀Rot^r.

Parameters:

r - the rotation index, in the range 0..3.

getHalfEdge

public HalfEdge getHalfEdge(int r)

Return a HalfEdge representing the the half-edge e₀Rot^r.

Parameters:

r - the rotation index, in the range 0..3.

isDirected

public boolean isDirected(int r)

Return whether the half-edge e₀Rot^r. is part of a directed edge.

Parameters:

r - the rotation index, in the range 0..3.

Returns:

true if the indicated half-edge is part of a directed edge

isHead

public boolean isHead(int r)

Return whether the origin of the half-edge e₀Rot^r is the head of the edge containing this half-edge (i.e., whether this edge is directed toward the origin of the half-edge). If the edge is either undirected or directed away from the origin of the half-edge, false is returned.

Parameters:

r - the rotation index, in the range 0..3.

Returns:

true if the origin is the head of the edge.

isTail

public boolean isTail(int r)

Return whether the origin of the half-edge e₀Rot^r is the tail of the edge containing this half-edge (i.e., whether this edge is directed away from the origin of the half-edge). If the edge is either undirected or directed toward the origin of the half-edge, false is returned.

Parameters:

r - the rotation index, in the range 0..3.

Returns:

true if the origin is the tail of the edge.

getHead

public Node getHead(int r)

Return the the head of the half-edge e₀Rot^r, which must be part of a directed edge. If the edge is directed, the return value will either be the origin of this half-edge or the origin of the symmetric half-edge e₀Rot^rSym. If the edge is not directed, a GraphCheckException will be thrown.

Parameters:

r - the rotation index, in the range 0..3.

Returns:

the head of the edge to which this half-edge belongs.

getTail

public Node getTail(int r)

Return the the tail of the half-edge e₀Rot^r, which must be part of a directed edge. If the edge is directed, the return value will either be the origin of this half-edge or the origin of the symmetric half-edge e₀Rot^rSym. If the edge is not directed, a GraphCheckException will be thrown.

Parameters:

r - the rotation index, in the range 0..3.

Returns:

the tail of the edge to which this half-edge belongs.

getRotationIndex

int getRotationIndex(Node v)

Returns the rotation index of node v. In the GS formulation, this is the value r such that v is e₀Rot^r.Origin, If no such r exists, a GraphCheckException is thrown.

Parameters:

v - the Node whose rotation index is to be computed.

Returns:

the rotation index of v.

getNextQEdge

QEdge getNextQEdge()

linkBefore

void linkBefore(int curRot,
                HalfEdge next)

Link the half edge (this,curRot) before the specified half edge (nextQEdge,nextRot).

Parameters:

curRot - The rotation coefficient of the half edge to be linked.

next - The successor halfedge

linkSolo

void linkSolo(int curRot)

Link the specified half edge to itself.

Parameters:

curRot - The rotation coefficient of the half edge to be linked.

unLink

void unLink(int curRot)

unLink The half edge(int curRot)

Parameters:

curRot - The rotation coefficient of the half edge to be linked.