public final class SubdivisionEdge
extends java.lang.Object
Subdivision
.
Every SubdivisionEdge
holds one end point of a full edge in a Subdivision
,
and a link to its twin()
holding the opposite end point. Together
these two half-edges for a complete Subdivision
edge.
Every SubdivisionEdge
is part of a cycle of half-edges that is connected by the
next()
and previous()
links. Assuming y-coordinates
increase upward, a clockwise cycle forms the inner boundary of the incident SubdivisionFace
,
and a counter-clockwise cycle forms its outer boundary. A SubdivisionEdge
may form a cycle
with its own twin half-edge; such a zero-area cycle always forms an inner boundary.
Modifier and Type | Method and Description |
---|---|
double |
cycleArea()
Gets the area of the polygon bounding the incident
face() . |
PointD |
cycleCentroid()
Gets the centroid of the polygon bounding the incident
face() . |
java.util.List<SubdivisionEdge> |
cycleEdges()
Gets all
SubdivisionEdge instances bounding the incident face() . |
PointD[] |
cyclePolygon()
|
PointD |
destination()
Gets the
PointD coordinates where the SubdivisionEdge ends. |
boolean |
equals(java.lang.Object obj)
Compares the specified
Object to this SubdivisionEdge instance. |
SubdivisionFace |
face()
Gets the
SubdivisionFace that is bounded by the SubdivisionEdge . |
SubdivisionEdge |
findEdgeTo(PointD destination)
Finds the
SubdivisionEdge with the same origin() and the
specified destination() , using exact coordinate comparisons. |
SubdivisionEdge |
findEdgeTo(PointD destination,
double epsilon)
Finds the
SubdivisionEdge with the same origin() and the specified
destination() , given the specified epsilon for coordinate comparisons. |
int |
hashCode()
Returns a hash code for the
SubdivisionEdge . |
boolean |
isCycleAreaZero()
Determines whether the area of the polygon bounding the incident
face() is zero. |
int |
key()
Gets the unique key of the
SubdivisionEdge . |
PolygonLocation |
locate(PointD q)
|
PolygonLocation |
locate(PointD q,
double epsilon)
|
SubdivisionEdge |
next()
Gets the next
SubdivisionEdge that bounds the same face() . |
PointD |
origin()
Gets the
PointD coordinates where the SubdivisionEdge begins. |
java.util.List<SubdivisionEdge> |
originEdges()
Gets all
SubdivisionEdge instances with the same origin() . |
SubdivisionEdge |
previous()
Gets the previous
SubdivisionEdge that bounds the same face() . |
LineD |
toLine()
Converts the
SubdivisionEdge to a LineD with identical direction. |
LineD |
toLineReverse()
Converts the
SubdivisionEdge to a LineD with opposite direction. |
java.lang.String |
toString()
Returns a
String representation of the SubdivisionEdge . |
SubdivisionEdge |
twin()
Gets the
SubdivisionEdge that is the twin of the current instance. |
public int key()
SubdivisionEdge
.
Starts at zero for the first SubdivisionEdge
in a Subdivision
,
and is incremented by one for each additional SubdivisionEdge
. key()
thus reflects the order in which SubdivisionEdge
instances were created.
Immutable unless Subdivision.renumberFaces()
is called on the Subdivision
.SubdivisionEdge
within its containing Subdivision
public PointD origin()
PointD
coordinates where the SubdivisionEdge
begins.PointD
coordinates where the SubdivisionEdge
beginspublic PointD destination()
PointD
coordinates where the SubdivisionEdge
ends.origin()
of the twin()
of the SubdivisionEdge
java.lang.NullPointerException
- if twin()
has not yet been initializedpublic SubdivisionFace face()
SubdivisionFace
that is bounded by the SubdivisionEdge
.SubdivisionFace
that lies to the left of the SubdivisionEdge
,
viewed from its origin()
and assuming that y-coordinates increase upwardpublic SubdivisionEdge next()
SubdivisionEdge
that bounds the same face()
.
Returns the twin()
of the current instance if no other SubdivisionEdge
begins at its destination()
. Returns the nearest SubdivisionEdge
in clockwise
direction, assuming y-coordinates increase upward, if multiple eligible instances exist.SubdivisionEdge
that begins at the destination()
of the current instance and bounds the same face()
public SubdivisionEdge previous()
SubdivisionEdge
that bounds the same face()
.
Returns the twin()
of the current instance if no other SubdivisionEdge
ends at its origin()
. Returns the nearest SubdivisionEdge
in counter-clockwise
direction, assuming y-coordinates increase upward, if multiple eligible instances exist.SubdivisionEdge
that ends at the origin()
of the current instance and bounds the same face()
public SubdivisionEdge twin()
SubdivisionEdge
that is the twin of the current instance.
A SubdivisionEdge
and its twin()
combine to form one full edge
in a Subdivision
, corresponding to a single LineD
instance.SubdivisionEdge
that begins at the destination()
and ends at the origin()
of the current instancepublic double cycleArea()
face()
.
The absolute value of cycleArea()
equals the area of cyclePolygon()
,
and is zero if all vertices are collinear or otherwise enclose no area. In that case,
cyclePolygon()
forms an inner boundary of the incident face()
.
The sign of a non-zero value indicates the orientation of its vertices: negative if the
vertices ordered clockwise, positive if they are ordered counter-clockwise, assuming
y-coordinates increase upward. Clockwise order indicates an inner boundary of the
incident face()
, and counter-clockwise order indicates the outer boundary.
cyclePolygon()
, with a sign indicating its vertex orientationpublic PointD cycleCentroid()
face()
.
Undefined if cycleArea()
is zero.cyclePolygon()
public java.util.List<SubdivisionEdge> cycleEdges()
SubdivisionEdge
instances bounding the incident face()
.
Begins with the current instance and follows the chain of next()
links
until the sequence is complete, adding each encountered SubdivisionEdge
.List
of all SubdivisionEdge
instances in the cycle
that begins with this instance and continues along next()
linkspublic PointD[] cyclePolygon()
PointD
vertices of the polygon bounding the incident face()
.
Represents the outer boundary of the incident face()
if the vertices
contain a positive area and are ordered counter-clockwise, assuming y-coordinates
increase upward. Otherwise, represents one of the inner boundaries of face()
.origin()
of all SubdivisionEdge
instances
in the cycle that begins with this instance and continues along next()
linkspublic boolean isCycleAreaZero()
face()
is zero.
Returns true
exactly if the twins of all SubdivisionEdge
instances in the
current cycle bound the same face()
as the current instance. This implies a cycle
that comprises only complete twin()
pairs. Such a cycle cannot enclose any area,
as that would require some twins bounding a different face()
.
cycleArea()
should equal zero if isCycleAreaZero()
returns true
, but
this may not be the case due to floating-point inaccuracies. isCycleAreaZero()
is
both faster and more precise than cycleArea()
if the actual area is not required.
true
if cyclePolygon()
encloses no area, else false
public java.util.List<SubdivisionEdge> originEdges()
SubdivisionEdge
instances with the same origin()
.
Begins with the current instance and follows the chain of twin()
and next()
links until the sequence is complete, adding each encountered SubdivisionEdge
.List
of all SubdivisionEdge
instances with the same origin()
public SubdivisionEdge findEdgeTo(PointD destination)
SubdivisionEdge
with the same origin()
and the
specified destination()
, using exact coordinate comparisons.
This is an O(n) operation, where n is the number of SubdivisionEdge
instances originating from the current origin()
.destination
- the destination()
of the SubdivisionEdge
SubdivisionEdge
with the same origin()
as the current instance
and the specified destination
, or null
if no match was foundjava.lang.NullPointerException
- if destination
is null
public SubdivisionEdge findEdgeTo(PointD destination, double epsilon)
SubdivisionEdge
with the same origin()
and the specified
destination()
, given the specified epsilon for coordinate comparisons.
See findEdgeTo(PointD)
for details.destination
- the destination()
of the SubdivisionEdge
epsilon
- the maximum absolute difference at which coordinates are considered equalSubdivisionEdge
with the same origin()
as the current instance
and the specified destination
, or null
if no match was foundjava.lang.IllegalArgumentException
- if epsilon
is less than zerojava.lang.NullPointerException
- if destination
is null
public PolygonLocation locate(PointD q)
PointD
relative to the polygon
bounding the incident face()
, using exact coordinate comparisons.
Performs a ray crossings algorithm with an asymptotic runtime of O(n).
This is equivalent to GeoUtils.pointInPolygon(org.kynosarges.tektosyne.geometry.PointD, org.kynosarges.tektosyne.geometry.PointD[])
operating on the
origin()
of all SubdivisionEdge
instances in the cycle that
begins with this instances and continues along the chain of next()
links.q
- the PointD
coordinates to locatePolygonLocation
value indicating the location of q
relative to cyclePolygon()
java.lang.NullPointerException
- if destination
is null
public PolygonLocation locate(PointD q, double epsilon)
PointD
relative to the polygon bounding
the incident face()
, given the specified epsilon for coordinate comparisons.
See locate(PointD)
for details.q
- the PointD
coordinates to locateepsilon
- the maximum absolute difference at which coordinates should be considered equalPolygonLocation
value indicating the location of q
relative to cyclePolygon()
java.lang.IllegalArgumentException
- if epsilon
is less than zerojava.lang.NullPointerException
- if destination
is null
public LineD toLine()
SubdivisionEdge
to a LineD
with identical direction.LineD
whose LineD.start
is the origin()
and whose
LineD.end
is the destination()
of the SubdivisionEdge
public LineD toLineReverse()
SubdivisionEdge
to a LineD
with opposite direction.LineD
whose LineD.start
is the destination()
and whose
LineD.end
is the origin()
of the SubdivisionEdge
public boolean equals(java.lang.Object obj)
Object
to this SubdivisionEdge
instance.
Compares only the keys of twin()
, face()
, next()
, and previous()
to avoid infinite recursions in half-edge cycles. Intended for testing, as any two
SubdivisionEdge
instances in the same Subdivision
are never equal.equals
in class java.lang.Object
obj
- the Object
to compare to this instancetrue
if obj
is not null
and a SubdivisionEdge
instance whose key()
, origin()
, and linked keys equal those
of this instance, else false
public int hashCode()
SubdivisionEdge
.
Returns key()
which is guaranteed to be unique within the containing Subdivision
.hashCode
in class java.lang.Object
Integer
hash code for the SubdivisionEdge
public java.lang.String toString()
String
representation of the SubdivisionEdge
.
Objects that are null
are represented with a key value of -1.