Class QuadEdge
java.lang.Object
org.locationtech.jts.triangulate.quadedge.QuadEdge
A class that represents the edge data structure which implements the quadedge algebra.
The quadedge algebra was described in a well-known paper by Guibas and Stolfi,
"Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams",
ACM Transactions on Graphics, 4(2), 1985, 75-123.
Each edge object is part of a quartet of 4 edges,
linked via their rot references.
Any edge in the group may be accessed using a series of rot()
operations.
Quadedges in a subdivision are linked together via their next references.
The linkage between the quadedge quartets determines the topology
of the subdivision.
The edge class does not contain separate information for vertices or faces; a vertex is implicitly defined as a ring of edges (created using the next field).
- Author:
- David Skea, Martin Davis
-
Method Summary
Modifier and TypeMethodDescriptionstatic QuadEdge
Creates a new QuadEdge connecting the destination of a to the origin of b, in such a way that all three have the same left face after the connection is complete.void
delete()
Marks this quadedge as being deleted.final Vertex
dest()
Gets the vertex for the edge's destinationfinal QuadEdge
dNext()
Gets the next CCW edge around (into) the destination of this edge.final QuadEdge
dPrev()
Gets the next CW edge around (into) the destination of this edge.boolean
Tests if this quadedge and another have the same line segment geometry, regardless of orientation.boolean
Tests if this quadedge and another have the same line segment geometry with the same orientation.getData()
Gets the external data value for this edge.double
Gets the length of the geometry of this quadedge.Gets the primary edge of this quadedge and its sym.final QuadEdge
invRot()
Gets the dual of this edge, directed from its left to its right.boolean
isLive()
Tests whether this edge has been deleted.final QuadEdge
lNext()
Gets the CCW edge around the left face following this edge.final QuadEdge
lPrev()
Gets the CCW edge around the left face before this edge.static QuadEdge
final QuadEdge
oNext()
Gets the next CCW edge around the origin of this edge.final QuadEdge
oPrev()
Gets the next CW edge around (from) the origin of this edge.final Vertex
orig()
Gets the vertex for the edge's originfinal QuadEdge
rNext()
Gets the edge around the right face ccw following this edge.final QuadEdge
rot()
Gets the dual of this edge, directed from its right to its left.final QuadEdge
rPrev()
Gets the edge around the right face ccw before this edge.void
Sets the external data value for this edge.void
Sets the connected edgestatic void
Splices two edges together or apart.static void
Turns an edge counterclockwise inside its enclosing quadrilateral.final QuadEdge
sym()
Gets the edge from the destination to the origin of this edge.Creates aLineSegment
representing the geometry of this edge.toString()
Converts this edge to a WKT two-point LINESTRING indicating the geometry of this edge.
-
Method Details
-
makeEdge
- Parameters:
o
- the origin Vertexd
- the destination Vertex- Returns:
- the new QuadEdge quartet
-
connect
Creates a new QuadEdge connecting the destination of a to the origin of b, in such a way that all three have the same left face after the connection is complete. Additionally, the data pointers of the new edge are set.- Returns:
- the connected edge.
-
splice
Splices two edges together or apart. Splice affects the two edge rings around the origins of a and b, and, independently, the two edge rings around the left faces of a and b. In each case, (i) if the two rings are distinct, Splice will combine them into one, or (ii) if the two are the same ring, Splice will break it into two separate pieces. Thus, Splice can be used both to attach the two edges together, and to break them apart.- Parameters:
a
- an edge to spliceb
- an edge to splice
-
swap
Turns an edge counterclockwise inside its enclosing quadrilateral.- Parameters:
e
- the quadedge to turn
-
getPrimary
Gets the primary edge of this quadedge and its sym. The primary edge is the one for which the origin and destination coordinates are ordered according to the standardCoordinate
ordering- Returns:
- the primary quadedge
-
setData
Sets the external data value for this edge.- Parameters:
data
- an object containing external data
-
getData
Gets the external data value for this edge.- Returns:
- the data object
-
delete
public void delete()Marks this quadedge as being deleted. This does not free the memory used by this quadedge quartet, but indicates that this edge no longer participates in a subdivision. -
isLive
public boolean isLive()Tests whether this edge has been deleted.- Returns:
- true if this edge has not been deleted.
-
setNext
Sets the connected edge- Parameters:
next
- edge
-
rot
Gets the dual of this edge, directed from its right to its left.- Returns:
- the rotated edge
-
invRot
Gets the dual of this edge, directed from its left to its right.- Returns:
- the inverse rotated edge.
-
sym
Gets the edge from the destination to the origin of this edge.- Returns:
- the sym of the edge
-
oNext
Gets the next CCW edge around the origin of this edge.- Returns:
- the next linked edge.
-
oPrev
Gets the next CW edge around (from) the origin of this edge.- Returns:
- the previous edge.
-
dNext
Gets the next CCW edge around (into) the destination of this edge.- Returns:
- the next destination edge.
-
dPrev
Gets the next CW edge around (into) the destination of this edge.- Returns:
- the previous destination edge.
-
lNext
Gets the CCW edge around the left face following this edge.- Returns:
- the next left face edge.
-
lPrev
Gets the CCW edge around the left face before this edge.- Returns:
- the previous left face edge.
-
rNext
Gets the edge around the right face ccw following this edge.- Returns:
- the next right face edge.
-
rPrev
Gets the edge around the right face ccw before this edge.- Returns:
- the previous right face edge.
-
orig
Gets the vertex for the edge's origin- Returns:
- the origin vertex
-
dest
Gets the vertex for the edge's destination- Returns:
- the destination vertex
-
getLength
public double getLength()Gets the length of the geometry of this quadedge.- Returns:
- the length of the quadedge
-
equalsNonOriented
Tests if this quadedge and another have the same line segment geometry, regardless of orientation.- Parameters:
qe
- a quadedge- Returns:
- true if the quadedges are based on the same line segment regardless of orientation
-
equalsOriented
Tests if this quadedge and another have the same line segment geometry with the same orientation.- Parameters:
qe
- a quadedge- Returns:
- true if the quadedges are based on the same line segment
-
toLineSegment
Creates aLineSegment
representing the geometry of this edge.- Returns:
- a LineSegment
-
toString
Converts this edge to a WKT two-point LINESTRING indicating the geometry of this edge.
-