Package org.tinfour.edge

Class QuadEdge

java.lang.Object

org.tinfour.edge.QuadEdge

All Implemented Interfaces:

IQuadEdge

public class QuadEdge
extends Object
implements IQuadEdge

A representation of an edge with forward and reverse links on one side and counterpart links attached to its dual (other side).

This concept is based on the structure popularized by Guibas, L. and Stolfi, J. (1985) "Primitives for the manipulation of subdivisions and the computation of Voronoi diagrams" ACM Transactions on Graphics, 4(2), 1985, p. 75-123.

Constructor Summary

Constructors

Constructor	Description
QuadEdge(int index)	Construct the edge and its dual assigning the pair the specified index.

Method Summary

Modifier and Type	Method	Description
protected void	checkConstraintIndex(int lowValue, int constraintIndex)	Checks to see if the constraint index is within the range supported by this instance.
void	clear()	Sets all vertices and link references to null (the link to a dual is not affected).
boolean	equals(Object o)	An implementation of the equals method which check for a matching reference.
Vertex	getA()	Gets the initial vertex for this edge.
Vertex	getB()	Gets the second vertex for this edge.
int	getBaseIndex()	Gets the index of the "base" side of a bi-directional edge.
QuadEdge	getBaseReference()	Gets the reference to the side-zero edge of the pair.
int	getConstraintBorderIndex()	Gets the index of the region-based constraint associated with an edge that serves as part of the polygon bounding that region.
int	getConstraintIndex()	Gets the index of the constraint associated with this edge.
int	getConstraintLineIndex()	Gets the index of a line-based constraint associated with an edge.
int	getConstraintRegionInteriorIndex()	Gets the index of the region-based constraint associated with an edge contained in the interior of a constraint polygon.
QuadEdge	getDual()	Gets the dual edge to this instance.
QuadEdge	getDualFromReverse()	Gets the dual of the reverse link.
QuadEdge	getForward()	Gets the forward reference of the edge.
QuadEdge	getForwardFromDual()	Gets the forward reference of the dual.
int	getIndex()	Gets the index value for this edge.
double	getLength()	Gets the length of the edge.
double	getLengthSq()	Gets the squared length of the edge.
QuadEdge	getReverse()	Gets the reverse reference of the edge.
QuadEdge	getReverseFromDual()	Gets the reverse link of the dual.
int	getSide()	Indicates which side of an edge a particular QuadEdge instance is attached to.
int	hashCode()
boolean	isConstrained()	Indicates whether the edge is constrained.
boolean	isConstraintLineMember()	Indicates whether the edge is a member of a constraint line, In some cases, a constraint line member edge may lie within a constrained region but will not lie on one of its borders.
boolean	isConstraintRegionBorder()	Indicates whether an edge represents the border of a constrained region.
boolean	isConstraintRegionInterior()	Indicates whether the edge is in the interior of a constrained region.
boolean	isConstraintRegionMember()	Indicates whether the edge is a member of a constrained region (is in the interior or serves as the border of a polygon-based constraint).
boolean	isSynthetic()	Indicates whether the synthetic flag is set for the edge.
Iterable<IQuadEdge>	pinwheel()	Gets an instance of an iterable that performs a pinwheel operation.
void	setA(Vertex a)	Sets the initial vertex for this edge.
void	setB(Vertex b)	Sets the second (B) vertex for this edge (also the A reference of the dual edge).
void	setConstraintBorderIndex(int constraintIndex)	Sets a flag identifying the edge as the border of a region-based constraint and stores the index for that constraint.
void	setConstraintIndex(int constraintIndex)	Sets the constraint index for this edge.
void	setConstraintLineIndex(int constraintIndex)	Sets a flag identifying the edge as the border of a line-based constraint and stores the index for that constraint.
void	setConstraintLineMemberFlag()	Sets the constraint-line member flag for the edge to true.
void	setConstraintRegionBorderFlag()	Sets a flag indicating that the edge is an edge of a constrained region.
void	setConstraintRegionInteriorIndex(int constraintIndex)	Sets a flag identifying the edge as an interior member of a region-based constraint and stores the index for that constraint.
void	setDualForward(QuadEdge e)	Sets the forward link to the dual of this edge.
void	setDualReverse(QuadEdge e)	Sets the reverse link of the dual to this edge.
void	setForward(QuadEdge e)	Sets the forward reference for this edge.
protected void	setIndex(int index)	Sets the index value for this edge.
void	setLine2D(AffineTransform transform, Line2D l2d)	A deprecated method replaced by the equivalent transcribeToLine2D().
void	setReverse(QuadEdge e)	Sets the reverse reference for this edge.
void	setSynthetic(boolean status)	Sets the synthetic flag for the edge.
void	setVertices(Vertex a, Vertex b)	Sets the vertices for this edge (and its dual).
String	toString()
void	transcribeToLine2D(AffineTransform transform, Line2D l2d)	Provides a convenience method for rendering edges by setting the Line2D argument with the transformed coordinates of the edge.

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

QuadEdge

public QuadEdge(int index)

Construct the edge and its dual assigning the pair the specified index.

Parameters:

index - an arbitrary integer value.

Method Detail

setVertices

public void setVertices(Vertex a,
                        Vertex b)

Sets the vertices for this edge (and its dual).

Parameters:

a - the initial vertex, must be a valid reference.

b - the second vertex, may be a valid reference or a null for a ghost edge.

getA

public final Vertex getA()

Gets the initial vertex for this edge.

Specified by:

getA in interface IQuadEdge

Returns:

a valid reference.

setA

public final void setA(Vertex a)

Sets the initial vertex for this edge.

Parameters:

a - a valid reference.

getB

public final Vertex getB()

Gets the second vertex for this edge.

Specified by:

getB in interface IQuadEdge

Returns:

a valid reference or a null for a ghost edge.

setB

public final void setB(Vertex b)

Sets the second (B) vertex for this edge (also the A reference of the dual edge).

Parameters:

b - a valid reference or a null for a ghost edge.

getForward

public final QuadEdge getForward()

Gets the forward reference of the edge.

Specified by:

getForward in interface IQuadEdge

Returns:

a valid reference.

getReverse

public final QuadEdge getReverse()

Gets the reverse reference of the edge.

Specified by:

getReverse in interface IQuadEdge

Returns:

a valid reference.

getForwardFromDual

public final QuadEdge getForwardFromDual()

Gets the forward reference of the dual.

Specified by:

getForwardFromDual in interface IQuadEdge

Returns:

a valid reference

getReverseFromDual

public final QuadEdge getReverseFromDual()

Gets the reverse link of the dual.

Specified by:

getReverseFromDual in interface IQuadEdge

Returns:

a valid reference

getDualFromReverse

public final QuadEdge getDualFromReverse()

Gets the dual of the reverse link.

Specified by:

getDualFromReverse in interface IQuadEdge

Returns:

a valid reference

setForward

public final void setForward(QuadEdge e)

Sets the forward reference for this edge.

Parameters:

e - a valid reference

setReverse

public final void setReverse(QuadEdge e)

Sets the reverse reference for this edge.

Parameters:

e - a valid reference

setDualForward

public final void setDualForward(QuadEdge e)

Sets the forward link to the dual of this edge.

Parameters:

e - a valid reference

setDualReverse

public final void setDualReverse(QuadEdge e)

Sets the reverse link of the dual to this edge.

Parameters:

e - a valid reference

getDual

public final QuadEdge getDual()

Gets the dual edge to this instance.

Specified by:

getDual in interface IQuadEdge

Returns:

a valid edge.

getIndex

public int getIndex()

Gets the index value for this edge.

Specified by:

getIndex in interface IQuadEdge

Returns:

an integer value

getBaseIndex

public int getBaseIndex()

Description copied from interface: IQuadEdge

Gets the index of the "base" side of a bi-directional edge. In Tinfour implementations, edges are bi-directional. In effect, the edge is implemented as a pair of unidirectional elements. Each element is assigned a separate index. The first element in the pair is designated as the "base" and is assigned an even-valued index. Its dual is assigned a value one greater than the base index. This method always returns an even value.

This method can be useful in cases where an application needs to track a complete edge without regard to which side of the edge is being considered.

Specified by:

getBaseIndex in interface IQuadEdge

Returns:

a positive, even value.

setIndex

protected void setIndex(int index)

Sets the index value for this edge. Because this index value is used by edge-pool implementations and for other data management activities, the scope of this method is limited to protected. The actual definition of this element is left to the application that uses it.

Parameters:

index - an integer value

getBaseReference

public QuadEdge getBaseReference()

Gets the reference to the side-zero edge of the pair.

Specified by:

getBaseReference in interface IQuadEdge

Returns:

a link to the side-zero edge of the pair.

getConstraintIndex

public int getConstraintIndex()

Gets the index of the constraint associated with this edge. Constraint index values must be in the range 0 to 9190, with negative numbers being reserved for internal use by the Tinfour library,

Specified by:

getConstraintIndex in interface IQuadEdge

Returns:

if constrained, a positive integer; otherwise, a negative value.

setConstraintIndex

public void setConstraintIndex(int constraintIndex)

Description copied from interface: IQuadEdge

Sets the constraint index for this edge. This method does not necessarily set an edge to a constrained status. In some implementations the constraint index may be used as a way of associating ordinary edges with a neighboring constraint. Constraint index values must be positive integers. The range of supported values will depend on the specific class that implements this interface. Please refer to the class documentation for specific values.

Specified by:

setConstraintIndex in interface IQuadEdge

Parameters:

constraintIndex - a positive number indicating which constraint a particular edge is associated with.

isConstrained

public boolean isConstrained()

Indicates whether the edge is constrained.

Specified by:

isConstrained in interface IQuadEdge

Returns:

true if the edge is constrained; otherwise, false.

clear

public void clear()

Sets all vertices and link references to null (the link to a dual is not affected).

toString

public String toString()

Overrides:

toString in class Object

getLength

public double getLength()

Gets the length of the edge.

Specified by:

getLength in interface IQuadEdge

Returns:

a positive floating point value

getLengthSq

public double getLengthSq()

Gets the squared length of the edge.

Specified by:

getLengthSq in interface IQuadEdge

Returns:

a positive floating point value

getSide

public int getSide()

Indicates which side of an edge a particular QuadEdge instance is attached to. The side value is a strictly arbitrary index used for algorithms that need to be able to assign a unique index to both sides of an edge.

Specified by:

getSide in interface IQuadEdge

Returns:

a value of 0 or 1.

equals

public boolean equals(Object o)

An implementation of the equals method which check for a matching reference.

Overrides:

equals in class Object

Parameters:

o - a valid reference or a null

Returns:

true if the specified reference matches this.

hashCode

public int hashCode()

Overrides:

hashCode in class Object

isConstraintRegionMember

public boolean isConstraintRegionMember()

Description copied from interface: IQuadEdge

Indicates whether the edge is a member of a constrained region (is in the interior or serves as the border of a polygon-based constraint). A constrained region member is not necessarily a constrained edge.

Specified by:

isConstraintRegionMember in interface IQuadEdge

Returns:

true if the edge is a member of an region; otherwise false.

isConstraintRegionInterior

public boolean isConstraintRegionInterior()

Description copied from interface: IQuadEdge

Indicates whether the edge is in the interior of a constrained region. Both sides of the edge lie within the interior of the region. All points along the edge will lie within the interior of the region with the possible exception of the endpoints. The endpoints may lie on the border of the region. An interior edge for a constrained region is not a constrained edge. Interior edges are also classified as "member" edges of a constrained region.

Specified by:

isConstraintRegionInterior in interface IQuadEdge

Returns:

true if the edge is in the interior of an region; otherwise false.

isConstraintRegionBorder

public boolean isConstraintRegionBorder()

Description copied from interface: IQuadEdge

Indicates whether an edge represents the border of a constrained region. Border edges will always be constrained. Border edges are also classified as "member" edges of a constrained region.

Specified by:

isConstraintRegionBorder in interface IQuadEdge

Returns:

true if the edge is the border of the constrained region; otherwise, false.

isConstraintLineMember

public boolean isConstraintLineMember()

Description copied from interface: IQuadEdge

Indicates whether the edge is a member of a constraint line, In some cases, a constraint line member edge may lie within a constrained region but will not lie on one of its borders.

Specified by:

isConstraintLineMember in interface IQuadEdge

Returns:

true if the edge is a member of an region; otherwise false.

setConstraintLineMemberFlag

public void setConstraintLineMemberFlag()

Description copied from interface: IQuadEdge

Sets the constraint-line member flag for the edge to true.

Specified by:

setConstraintLineMemberFlag in interface IQuadEdge

setConstraintRegionBorderFlag

public void setConstraintRegionBorderFlag()

Description copied from interface: IQuadEdge

Sets a flag indicating that the edge is an edge of a constrained region.

Specified by:

setConstraintRegionBorderFlag in interface IQuadEdge

setSynthetic

public void setSynthetic(boolean status)

Description copied from interface: IQuadEdge

Sets the synthetic flag for the edge. Synthetic edges are those that do not arise naturally from the TIN-building logic but are created by special operations.

Specified by:

setSynthetic in interface IQuadEdge

Parameters:

status - true if the edge is synthetic; otherwise, false.

isSynthetic

public boolean isSynthetic()

Description copied from interface: IQuadEdge

Indicates whether the synthetic flag is set for the edge.

Specified by:

isSynthetic in interface IQuadEdge

Returns:

true if the edge is synthetic; otherwise, false.

pinwheel

public Iterable<IQuadEdge> pinwheel()

Description copied from interface: IQuadEdge

Gets an instance of an iterable that performs a pinwheel operation. This instance may be used in a Java for statement

    for(IQuadEdge e: startingEdge.pinwheel()){
    }
 

About the pinwheel operation: In the Tinfour library, a pinwheel operation interates over the set of edges that connect to the initial vertex of the current edge. The initial vertex is the one returned from a call to getA(). Connected vertices may be obtained through a call to getB().

Null references for vertex:If vertex A lies on the perimeter of the Delaunay mesh, one or more of the connected edges may terminate on the "ghost vertex" which is used by Tinfour to complete the triangulation. The ghost vertex is represented by a null reference. So applications performing a pinwheel on an arbitrary edge should include logic to handle a null return from the getB() method.

    for(IQuadEdge e: startingEdge.pinwheel()){
        Vertex B = e.getB();
        if(B == null){
             // skip processing
        }else {
             // perform processing using B
        }
    }
 

Specified by:

pinwheel in interface IQuadEdge

Returns:

a valid Iterable.

setLine2D

public void setLine2D(AffineTransform transform,
                      Line2D l2d)

Description copied from interface: IQuadEdge

A deprecated method replaced by the equivalent transcribeToLine2D().

Specified by:

setLine2D in interface IQuadEdge

Parameters:

transform - a valid affine transform

l2d - a valid Line2D instance to receive the geometry data from the edge.

transcribeToLine2D

public void transcribeToLine2D(AffineTransform transform,
                               Line2D l2d)

Description copied from interface: IQuadEdge

Provides a convenience method for rendering edges by setting the Line2D argument with the transformed coordinates of the edge. The affine transform is used to map vertex A and B of the edge to the specified coordinate system. The transformed coordinates are then stored in the application-supplied Line2D object. If a null reference is supplied for the transform, this method treats it as the identity transform.

This method is intended to support rendering operations that may render a large number of edges using Java's Line2D class. In such cases, this method avoids the overhead involved in creating multiple Line2D instances by allowing an application to reuse a single instance multiple times.

Specified by:

transcribeToLine2D in interface IQuadEdge

Parameters:

transform - a valid affine transform

l2d - a valid Line2D instance to receive the geometry data from the edge.

checkConstraintIndex

protected void checkConstraintIndex(int lowValue,
                                    int constraintIndex)

Checks to see if the constraint index is within the range supported by this instance.

Parameters:

lowValue - the lowest allowed value for the constraint index.

constraintIndex - a positive integer.

setConstraintBorderIndex

public void setConstraintBorderIndex(int constraintIndex)

Description copied from interface: IQuadEdge

Sets a flag identifying the edge as the border of a region-based constraint and stores the index for that constraint.

Specified by:

setConstraintBorderIndex in interface IQuadEdge

Parameters:

constraintIndex - a positive integer in the range zero to 8190, or -1 for a null constraint.

getConstraintBorderIndex

public int getConstraintBorderIndex()

Description copied from interface: IQuadEdge

Gets the index of the region-based constraint associated with an edge that serves as part of the polygon bounding that region.

Specified by:

getConstraintBorderIndex in interface IQuadEdge

Returns:

a positive integer or -1 if no constraint is specified.

setConstraintLineIndex

public void setConstraintLineIndex(int constraintIndex)

Description copied from interface: IQuadEdge

Sets a flag identifying the edge as the border of a line-based constraint and stores the index for that constraint.

Specified by:

setConstraintLineIndex in interface IQuadEdge

Parameters:

constraintIndex - a positive integer in range zero to 8190

setConstraintRegionInteriorIndex

public void setConstraintRegionInteriorIndex(int constraintIndex)

Description copied from interface: IQuadEdge

Sets a flag identifying the edge as an interior member of a region-based constraint and stores the index for that constraint.

Specified by:

setConstraintRegionInteriorIndex in interface IQuadEdge

Parameters:

constraintIndex - a positive integer in the range 0 to 8190, or -1 for a null value

getConstraintRegionInteriorIndex

public int getConstraintRegionInteriorIndex()

Description copied from interface: IQuadEdge

Gets the index of the region-based constraint associated with an edge contained in the interior of a constraint polygon. The edge itself is not necessarily constrained and is not part of the definition for the polygon.

Specified by:

getConstraintRegionInteriorIndex in interface IQuadEdge

Returns:

a positive integer or -1 if no constraint is specified.

getConstraintLineIndex

public int getConstraintLineIndex()

Description copied from interface: IQuadEdge

Gets the index of a line-based constraint associated with an edge. The edge is constrained. Due to limitations of memory, the Tinfour implementation cannot support an index for an edge that happens to be a member of multiple constraints (as in the case of an edge that is also part of a border constraint).

Specified by:

getConstraintLineIndex in interface IQuadEdge

Returns:

a positive integer or -1 is no constraint index is available.