public class Subdivision extends java.lang.Object implements Graph<PointD>
In addition to edges and vertices, Subdivision
also stores the faces formed by
all edges. Faces are any polygonal regions that are bounded by edges, whether on the inside,
on the outside, or both. Edges are represented by the SubdivisionEdge
class,
and faces are represented by the SubdivisionFace
class.
Subdivision
supports generic graph algorithms through its Graph
implementation.
The graph nodes are the PointD
coordinates of all vertices. Two nodes are considered
connected if an edge exists between their corresponding vertices. The distance measure is the
Euclidean distance between vertices.
The planar subdivision is implemented as the doubly-connected edge list described by Mark de Berg et al., Computational Geometry (3rd ed.), Springer-Verlag 2008, p.29-43. This implementation represents edges as “twin” pairs of half-edges.
Modifier and Type | Field and Description |
---|---|
double |
epsilon
The epsilon used for coordinate comparisons within the
vertices() collection. |
Constructor and Description |
---|
Subdivision(double epsilon)
Creates an empty
Subdivision . |
Modifier and Type | Method and Description |
---|---|
AddEdgeResult |
addEdge(PointD start,
PointD end)
Adds a new edge to the
Subdivision that connects the specified PointD
vertices, and returns additional information on any changed and added faces() . |
int |
connectivity()
Gets the maximum number of direct neighbors for any
Graph node. |
boolean |
contains(PointD node)
Determines whether the
Graph contains the specified node. |
Subdivision |
copy()
Creates a deep copy of the
Subdivision . |
java.util.NavigableMap<java.lang.Integer,SubdivisionEdge> |
edges()
Gets all
SubdivisionEdge instances in the Subdivision . |
java.util.NavigableMap<java.lang.Integer,SubdivisionFace> |
faces()
Gets all
SubdivisionFace instances in the Subdivision . |
SubdivisionElement |
find(PointD q,
double epsilon)
Finds the
SubdivisionElement at the specified PointD coordinates. |
SubdivisionEdge |
findEdge(PointD origin,
PointD destination)
Finds the
SubdivisionEdge with the specified PointD origin and destination. |
SubdivisionFace |
findFace(PointD q)
Finds the smallest
SubdivisionFace that contains the specified PointD coordinates. |
SubdivisionFace |
findFace(PointD[] polygon,
boolean verify)
Finds the
SubdivisionFace whose outer boundary equals the specified PointD polygon. |
FindEdgeResult |
findNearestEdge(PointD q)
Finds the
SubdivisionEdge in the Subdivision that is
nearest to and facing the specified PointD coordinates. |
PointD |
findNearestNode(PointD location)
|
PointD |
findNearestVertex(PointD q)
|
static Subdivision |
fromLines(LineD[] lines,
double epsilon)
Creates a
Subdivision from the specified LineD segments. |
static Subdivision |
fromPolygons(PointD[][] polygons,
double epsilon)
Creates a
Subdivision from the specified PointD polygons. |
double |
getDistance(PointD source,
PointD target)
Gets the distance between two specified
Graph nodes. |
SubdivisionEdge[] |
getEdgesByOrigin()
Gets all
SubdivisionEdge instances in the Subdivision ,
lexicographically sorted by SubdivisionEdge.origin() . |
java.util.List<PointD> |
getNeighbors(PointD node)
Gets all direct neighbors of the specified
Graph node. |
PointD |
getWorldLocation(PointD node)
Gets the world location of the specified
Graph node. |
PointD[] |
getWorldRegion(PointD node)
Gets the world region covered by the specified
Graph node. |
java.util.List<SubdivisionEdge> |
getZeroAreaCycles()
Gets all
SubdivisionEdge cycles in the Subdivision that enclose no area. |
static SubdivisionIntersection |
intersection(Subdivision division1,
Subdivision division2)
Creates a
Subdivision from the intersection of two specified instances,
and returns additional information on the corresponding faces() . |
boolean |
isEmpty()
Indicates whether the
Subdivision is empty. |
boolean |
moveVertex(PointD oldVertex,
PointD newVertex)
|
int |
nodeCount()
|
java.util.Set<PointD> |
nodes()
Gets all nodes in the
Graph . |
RemoveEdgeResult |
removeEdge(int edgeKey)
Removes the specified edge from the
Subdivision , and returns
additional information on any changed and removed faces() . |
boolean |
removeVertex(PointD vertex)
Removes the specified
PointD vertex by joning both incident edges. |
boolean |
renumberEdges()
Renumbers all
edges() so that each SubdivisionEdge.key()
equals the iterator position of the corresponding SubdivisionEdge . |
boolean |
renumberFaces()
Renumbers all
faces() so that each SubdivisionFace.key()
equals the iterator position of the corresponding SubdivisionFace . |
SubdivisionEdge |
splitEdge(int edgeKey)
Splits the specified edge in half.
|
boolean |
structureEquals(Subdivision division)
Determines whether the specified
Subdivision and this instance are structurally equal. |
LineD[] |
toLines()
Converts all edges in the
Subdivision to LineD instances. |
PointD[][] |
toPolygons()
|
void |
validate()
Validates the structure of the
Subdivision . |
java.util.Map<PointD,PointD[]> |
vertexRegions()
Gets a mapping of
vertices() to Graph world regions. |
java.util.NavigableMap<PointD,SubdivisionEdge> |
vertices()
|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
getNeighbors
public final double epsilon
vertices()
collection.
Defines the maximum absolute difference at which vertex coordinates should be considered
equal. Always equals the PointDComparator.epsilon
of the PointDComparator
responsible for ordering the keys of the vertices()
collection.public Subdivision(double epsilon)
Subdivision
.
All collections are empty, except for faces()
which contains
only the unbounded SubdivisionFace
.epsilon
- the epsilon used for coordinate comparisons within vertices()
java.lang.IllegalArgumentException
- if epsilon
is less than zeropublic java.util.NavigableMap<java.lang.Integer,SubdivisionEdge> edges()
SubdivisionEdge
instances in the Subdivision
.
Always contains an even number of elements since every edge in the Subdivision
is comprised of two SubdivisionEdge
instances.
This collection is provided for convenience, unit testing, and faster edge scanning.
It is not strictly needed since a list of all SubdivisionEdge
instances can be
obtained by iterating over all vertices
, e.g. using getEdgesByOrigin()
.
Maintaining the edges()
collection consumes little extra runtime but a significant
amount of memory, so an alternative Subdivision
implementation might choose to
remove this collection and create new SubdivisionEdge
collections on demand.
NavigableMap
mapping the SubdivisionEdge.key()
of each SubdivisionEdge
instance to the corresponding instancepublic java.util.NavigableMap<java.lang.Integer,SubdivisionFace> faces()
SubdivisionFace
instances in the Subdivision
.
Always contains at least one element which is the unbounded face. The unbounded
SubdivisionFace
always has a SubdivisionFace.key()
of zero.NavigableMap
mapping the SubdivisionFace.key()
of each SubdivisionFace
instance to the corresponding instancepublic boolean isEmpty()
Subdivision
is empty.
Returns true
exactly if the edges()
collection is empty. For any valid
Subdivision
, that is the case exactly if the vertices()
collection is
also empty, and the faces()
collection contains only the unbounded face.true
if the Subdivision
is empty except for the
unbounded SubdivisionFace
, else false
public java.util.Map<PointD,PointD[]> vertexRegions()
vertices()
to Graph
world regions.
Always returns an empty collection by default, as Subdivision
does not inherently
associate world regions with vertices()
. Clients must explicitly add any desired
key-and-value pairs. This collection is therefore modifiable.
getWorldRegion(org.kynosarges.tektosyne.geometry.PointD)
attempts to return the polygonal region that vertexRegions()
associates with a specified vertices()
key, i.e. Graph
node, and returns
null
if no association is found.
Map
of vertices()
keys, representing Graph
nodes,
to the corresponding Graph
world regionspublic java.util.NavigableMap<PointD,SubdivisionEdge> vertices()
PointD
vertices with an incident SubdivisionEdge
in the Subdivision
.
Sorted lexicographically by PointD
keys, using the ordering established
by PointDComparatorY
. That is, keys are sorted first by PointD.y
and then by PointD.x
coordinates.
Every vertices()
key is associated with a valid SubdivisionEdge
.
That is, a Subdivision
never contains isolated points, only edges. If multiple
SubdivisionEdge
instances originate from the same vertex, one is selected
arbitrarily for the vertices()
collection, depending on the construction
order of the Subdivision
.
NavigableMap
mapping each PointD
vertex in the
Subdivision
to a SubdivisionEdge
that originates at the vertexpublic AddEdgeResult addEdge(PointD start, PointD end)
Subdivision
that connects the specified PointD
vertices, and returns additional information on any changed and added faces()
.
First checks if the new edge would intersect any existing edges()
, except
at the specified start
and end
coordinates, and fails if so.
Otherwise, creates two new edges()
elements, from start
to end
and vice versa. If start
and/or end
are not found in the vertices()
collection, the corresponding vertices()
elements are added as well.
If the added edge connects an inner cycle of the containing SubdivisionFace
with
its outer cycle, the inner cycle is removed. If the added edge connects two inner cycles,
one of them is arbitrarily chosen for removal.
If the added edge connects two half-edges within the same inner cycle, a new
SubdivisionFace
for the resulting enclosed area is created. If the added edge
connects two half-edges within the outer cycle, a new SubdivisionFace
for the
part enclosing the smaller area is created.
start
- the PointD
coordinates of the first vertex to connectend
- the PointD
coordinates of the second vertex to connectAddEdgeResult
containing the result of the operationjava.lang.NullPointerException
- if start
or end
is null
public Subdivision copy()
Subdivision
.
Replicates the entire structure of the Subdivision
, creating a new
SubdivisionEdge
and SubdivisionFace
with identical keys
for each corresponding instance found in the current structure.
structureEquals(org.kynosarges.tektosyne.subdivision.Subdivision)
will succeed for comparing both instances.Subdivision
public SubdivisionElement find(PointD q, double epsilon)
SubdivisionElement
at the specified PointD
coordinates.
First calls findFace(org.kynosarges.tektosyne.geometry.PointD)
to determine the smallest faces()
element that
contains q
, then checks all its SubdivisionFace.outerEdge()
and
SubdivisionFace.innerEdges()
cycles to determine whether q
coincides
with an incident edges()
or vertices()
element.
find
performs a slow brute-force search. For better performance, create a
SubdivisionSearch
for repeated searches within the same Subdivision
,
or examine the edges()
and vertices()
collections directly if you expect
q
to coincide with one of their elements.
q
- the PointD
coordinates to examineepsilon
- the maximum absolute difference at which coordinates should be considered equal,
or zero to use exact coordinate comparisonsSubdivisionElement
that coincides with q
java.lang.IllegalArgumentException
- if epsilon
is less than zerojava.lang.NullPointerException
- if q
is null
public SubdivisionEdge findEdge(PointD origin, PointD destination)
SubdivisionEdge
with the specified PointD
origin and destination.
First attempts to find origin
in the vertices()
collection, then calls
SubdivisionEdge.findEdgeTo(org.kynosarges.tektosyne.geometry.PointD)
to find the SubdivisionEdge
leading from
origin
to destination
.
This is an O(ld n + m) operation, where n is the number of vertices()
and m is
the number of half-edges originating from origin
. All coordinate comparisons
use the current epsilon
of the Subdivision
.
origin
- the SubdivisionEdge.origin()
of the SubdivisionEdge
destination
- the SubdivisionEdge.destination()
of the SubdivisionEdge
SubdivisionEdge
with the specified origin
and destination
,
or null
if edges()
contains no matching elementjava.lang.NullPointerException
- if origin
or destination
is null
public SubdivisionFace findFace(PointD q)
SubdivisionFace
that contains the specified PointD
coordinates.
Performs a linear search through all bounded faces()
for an
SubdivisionFace.outerEdge()
boundary that contains q
, i.e. one for
which SubdivisionEdge.locate(org.kynosarges.tektosyne.geometry.PointD)
does not return PolygonLocation.OUTSIDE
.
The first containing face that has no SubdivisionFace.innerEdges()
is immediately
returned. If all containing faces have one or more SubdivisionFace.innerEdges()
,
the one with the smallest outer SubdivisionEdge.cycleArea()
is returned.
If no containing face was found, the unbounded face is returned.
findFace
has an average runtime of O(n/2) where n is the number of bounded
faces()
, unless faces()
elements with SubdivisionFace.innerEdges()
are frequent in which case the runtime approaches O(n).
q
- the PointD
coordinates to examineSubdivisionFace
that contains q
java.lang.NullPointerException
- if q
is null
public SubdivisionFace findFace(PointD[] polygon, boolean verify)
SubdivisionFace
whose outer boundary equals the specified PointD
polygon.
Calls findEdge(org.kynosarges.tektosyne.geometry.PointD, org.kynosarges.tektosyne.geometry.PointD)
on each pair of consecutive polygon
elements, and
immediately returns null
if no SubdivisionEdge
is found for any such pair.
Otherwise, the SubdivisionEdge.face()
links of both twin half-edges are examined.
If the SubdivisionFace
on the same side of the polygon
ever changes,
all half-edges on that side are eliminated from the search.
If verify
is false
, the SubdivisionFace
on the remaining side when
the other has been eliminated is immediately returned. Otherwise, findFace
continues
checking the half-edges on the remaining side, verifying that they form a cycle around a
single SubdivisionFace
which also contains its SubdivisionFace.outerEdge()
.
The specified polygon
may begin with any incident vertex, and the sequence of vertices
may follow either the chain of SubdivisionEdge.next()
or SubdivisionEdge.previous()
links around the incident half-edges.
Depending on the verify
flag, findFace
has a runtime between O(ld n + 2m)
and O(ld n + km), where n is the number of vertices()
, m is the number of half-edges
originating from each vertex, and k is the number of polygon
vertices. All coordinate
comparisons use the current epsilon
of the Subdivision
.
polygon
- an array whose PointD
coordinates represent the consecutive
vertices of the outer boundary of the SubdivisionFace
verify
- true
to verify that the outer boundary is fully congruent with
polygon
; false
to return a result as soon as all potential
alternatives have been eliminatedSubdivisionFace
whose outer boundary equals polygon
,
or null
if no matching faces()
element was foundjava.lang.IllegalArgumentException
- if polygon
has fewer than three elementsjava.lang.NullPointerException
- if polygon
is null
public FindEdgeResult findNearestEdge(PointD q)
SubdivisionEdge
in the Subdivision
that is
nearest to and facing the specified PointD
coordinates.
First calls findFace(PointD)
to determine the faces()
element
that contains q
, and then calls SubdivisionFace.findNearestEdge(org.kynosarges.tektosyne.geometry.PointD)
on that SubdivisionFace
to determine the nearest facing SubdivisionEdge
and its distance from q
.q
- the PointD
coordinates to examineFindEdgeResult
containing the values described abovejava.lang.NullPointerException
- if q
is null
public PointD findNearestVertex(PointD q)
PointD
vertex in the Subdivision
that is nearest to the specified PointD
coordinates.
Returns the result of PointDComparator.findNearest(java.util.List<org.kynosarges.tektosyne.geometry.PointD>, org.kynosarges.tektosyne.geometry.PointD)
for q
, executing
on the PointDComparatorY
used to sort the vertices()
collection.q
- the PointD
coordinates to examinevertices()
key with the smallest Euclidean distance to q
java.lang.NullPointerException
- if q
is null
public static Subdivision fromLines(LineD[] lines, double epsilon)
Subdivision
from the specified LineD
segments.
Also determines the faces()
that are formed by the edges()
of the new
Subdivision
, and sets its comparison epsilon
to the specified
epsilon
. The new Subdivision
is empty if lines
is empty.
Caution: The specified lines
must not intersect or overlap anywhere except
in their LineD.start
and LineD.end
points. fromLines
does not
check this condition. If violated, the returned Subdivision
will be invalid.
lines
- an array of LineD
instances representing the edges()
in the new Subdivision
epsilon
- the maximum absolute difference at which coordinates should be considered equal,
or zero to use exact coordinate comparisonsSubdivision
whose edges()
are the specified lines
,
and whose vertices()
are their LineD.start
and LineD.end
pointsjava.lang.IllegalArgumentException
- if lines
contains an element whose LineD.start
point equals its LineD.end
point, or if epsilon
is less than zerojava.lang.NullPointerException
- if lines
is null
public static Subdivision fromPolygons(PointD[][] polygons, double epsilon)
Subdivision
from the specified PointD
polygons.
Sets the comparison epsilon
of the new Subdivision
to the specified
epsilon
. The new Subdivision
is empty if polygons
is empty.
Caution: The specified polygons
may share common edges and vertices,
and may be fully contained within one another, but must not otherwise intersect
or overlap. fromPolygons
does not check this condition. If violated, the
returned Subdivision
will be invalid.
polygons
- an array of PointD
arrays representing the outer boundaries
of all bounded faces()
in the new Subdivision
epsilon
- the maximum absolute difference at which coordinates should be considered equal,
or zero to use exact coordinate comparisonsSubdivision
whose bounded faces()
are the specified polygons
java.lang.IllegalArgumentException
- if polygons
contains an array with less than three
elements or two consecutive identical elements, or if epsilon
is less than zerojava.lang.NullPointerException
- if polygons
or any of its elements is null
public SubdivisionEdge[] getEdgesByOrigin()
SubdivisionEdge
instances in the Subdivision
,
lexicographically sorted by SubdivisionEdge.origin()
.
Does not use the edges()
collection but rather scans the vertices()
collection by lexicographically ascending coordinates. All SubdivisionEdge
instances originating from the same vertex are stored in consecutive index positions,
proceeding clockwise around the vertex.edges()
, but sorted lexicographically by
SubdivisionEdge.origin()
rather than by SubdivisionEdge.key()
public java.util.List<SubdivisionEdge> getZeroAreaCycles()
SubdivisionEdge
cycles in the Subdivision
that enclose no area.
Returns all SubdivisionFace.innerEdges()
of all faces()
for which SubdivisionEdge.isCycleAreaZero()
succeeds.List
containing one SubdivisionEdge
from each cycle
in the Subdivision
that encloses no areapublic static SubdivisionIntersection intersection(Subdivision division1, Subdivision division2)
Subdivision
from the intersection of two specified instances,
and returns additional information on the corresponding faces()
.
First intersects the edges()
of division1
with those of division2
,
and then creates the resulting faces()
with consecutive keys that equal their index
positions. The original faces()
that equal or contain the new faces()
are
indicated by key collections in the returned SubdivisionIntersection
.
intersection(org.kynosarges.tektosyne.subdivision.Subdivision, org.kynosarges.tektosyne.subdivision.Subdivision)
uses the epsilon
of division1
to compare
vertices()
for equality. Therefore, division2
must use the same or a greater
epsilon
; otherwise, some of its edges()
might not be representable in the
new Subdivision
. Moreover, the comparison epsilon used to detect edge intersections
is raised to a minimum of 1e-10 for better numerical stability.
intersection(org.kynosarges.tektosyne.subdivision.Subdivision, org.kynosarges.tektosyne.subdivision.Subdivision)
performs best if either division1
or division2
is empty,
and worst if both instances are of equal size. That is because the algorithm intersects the
edges()
of division1
with those of division2
, rather than intersecting
all edges()
of the combined Subdivision
with each other.
division1
- the first Subdivision
to intersectdivision2
- the second Subdivision
to intersectSubdivisionIntersection
representing the result of the intersectionjava.lang.IllegalArgumentException
- if the epsilon
of division1
is greater than that
of division2
, or division1
or division2
is structurally invalidjava.lang.NullPointerException
- if division1
or division2
is null
public boolean moveVertex(PointD oldVertex, PointD newVertex)
PointD
vertex to the specified PointD
coordinates.
First checks whether vertices()
already contains newVertex
, or whether
moving the SubdivisionEdge.origin()
of any incident SubdivisionEdge
to
newVertex
would create an intersection with any non-incident SubdivisionEdge
on any boundary of any incident SubdivisionFace
.
If so, moveVertex
returns false
. Otherwise, oveVertex
updates
the vertices()
collection and the SubdivisionEdge.origin()
of all incident
edges()
and returns true
.
public RemoveEdgeResult removeEdge(int edgeKey)
Subdivision
, and returns
additional information on any changed and removed faces()
.
Fails immediately if edgeKey
is not found in the edges()
collection.
If the removed SubdivisionEdge
and its SubdivisionEdge.twin()
bound two
different faces, the faces()
element whose outer boundary contains a removed
half-edge is also removed. If both removed half-edges constitute outer boundaries,
the faces()
element with the greater SubdivisionFace.key()
is removed.
If the SubdivisionEdge.origin()
or SubdivisionEdge.destination()
of a removed
SubdivisionEdge
does not terminate any other edges()
, the corresponding
vertices()
element(s) are also removed.
edgeKey
- the SubdivisionEdge.key()
of one SubdivisionEdge
to remove,
with its SubdivisionEdge.twin()
implicitly removed as wellRemoveEdgeResult
containing the result of the operationpublic boolean removeVertex(PointD vertex)
PointD
vertex by joning both incident edges.
First checks whether vertices()
does not contain vertex
, or whether
vertex
has not exactly two distinct incident full edges, or whether joining
them would disturb vertex chains or create an intersection with any non-incident
SubdivisionEdge
on any boundary of the incident SubdivisionFace
.
If so, removeVertex
returns false
. Otherwise, removeVertex
links the twins of the incident edges()
into a new SubdivisionEdge
pair,
updates the vertices()
and edges()
collections, and returns true
.
vertex
- the PointD
vertex to removetrue
if vertex
and both incident edges were removed, else false
java.lang.NullPointerException
- if vertex
is null
public boolean renumberEdges()
edges()
so that each SubdivisionEdge.key()
equals the iterator position of the corresponding SubdivisionEdge
.
Deleting edges()
from an existing Subdivision
may leave gaps in the
SubdivisionEdge.key()
sequence. renumberEdges()
eliminates any such gaps,
restoring the original equivalence of SubdivisionEdge.key()
value and iterator
position in the edges()
collection.
renumberEdges()
does not change the sequence of SubdivisionEdge
instances
in the edges()
collection, only their SubdivisionEdge.key()
values.
true
if any SubdivisionEdge.key()
was changed, else false
public boolean renumberFaces()
faces()
so that each SubdivisionFace.key()
equals the iterator position of the corresponding SubdivisionFace
.
Deleting edges()
from an existing Subdivision
may leave gaps in the
SubdivisionFace.key()
sequence of the faces()
collection.
renumberFaces()
eliminates any such gaps, restoring the original equivalence of
SubdivisionFace.key()
value and iterator position in the faces()
collection.
renumberFaces()
does not change the sequence of SubdivisionFace
instances
in the faces()
collection, only their SubdivisionFace.key()
values.
Note that this invalidates any existing SubdivisionMap
face mappings.
true
if any SubdivisionEdge.key()
was changed, else false
public SubdivisionEdge splitEdge(int edgeKey)
null
if edgeKey
was not found in the edges()
collection, or if the new vertex would equal an existing vertices()
key,
given the current epsilon
.
Otherwise, creates a new vertices()
element in the center of the split edge,
and two new SubdivisionEdge
instances that originate from the new vertex.
Each is paired with one of the original SubdivisionEdge
twins, effectively
shortening them to end at the new vertex.
edgeKey
- the SubdivisionEdge.key()
of one SubdivisionEdge
to split,
implicitly splitting its SubdivisionEdge.twin()
as welledges()
that originate from the new vertices()
element if the split was successful, else null
public boolean structureEquals(Subdivision division)
Subdivision
and this instance are structurally equal.
Compares the number, order, and internal structure of all edges()
and faces()
in the two Subdivision
instances to test for structural equality. Individual objects
are compared using their own Object.equals(java.lang.Object)
methods.
Intended for testing the copy()
method which duplicates keys but not objects.
division
- the Subdivision
to compare to this instancetrue
if division
and this instance are structurally equal, else false
java.lang.NullPointerException
- if division
is null
public LineD[] toLines()
Subdivision
to LineD
instances.
The returned array has half as many elements as the edges()
collection since
each LineD
corresponds to a twin pair of SubdivisionEdge
instances.
The returned array is sorted by the smaller SubdivisionEdge.key()
of the two SubdivisionEdge
instances that constitute each full edge,
yielding the same ordering as the edges()
collection but excluding the
higher-keyed twin of each SubdivisionEdge
pair.
LineD
instances representing all edges in the Subdivision
public PointD[][] toPolygons()
faces()
in the Subdivision
to PointD
polygons.
Each nested PointD
array within the returned array contains the
SubdivisionEdge.cyclePolygon()
for the SubdivisionFace.outerEdge()
of one bounded faces()
element.
The PointD
arrays are sorted by the SubdivisionFace.key()
of the
corresponding SubdivisionFace
, yielding the same ordering as the
faces()
collection but excluding the unbounded face.
PointD
polygons representing
all bounded faces()
in the Subdivision
public void validate()
Subdivision
.
Uses assert
statements to verify the structural invariants of the Subdivision
.
Assertions must be enabled at runtime for validate()
to have any effect.java.lang.AssertionError
- if the structure of the Subdivision
is invalidpublic int connectivity()
Graph
node.
Always greater than zero. Returns the maximum number of SubdivisionEdge
instances
that originate from any single vertex. Scans the entire vertices()
collection on
first access, then returns a cached value on subsequent accesses. The scan is repeated
whenever the structure of the Subdivision
changes.connectivity
in interface Graph<PointD>
Graph
nodepublic int nodeCount()
nodes()
in the Graph
.
Never less than zero. Returns the current number of vertices()
.public java.util.Set<PointD> nodes()
Graph
.
Always contains nodeCount()
elements. Returns all PointD
keys
in the vertices()
collection, using its current sorting order.public boolean contains(PointD node)
Graph
contains the specified node.
Returns true
exactly if the vertices()
collection contains
a PointD
key that equals the specified node
. This is an O(ld n)
operation, where n is the number of vertices()
.public PointD findNearestNode(PointD location)
Graph
node nearest to the specified PointD
world location.
Returns the result of findNearestVertex(org.kynosarges.tektosyne.geometry.PointD)
for the specified location
.findNearestNode
in interface Graph<PointD>
location
- the PointD
location, in world coordinates, to examineGraph
node whose getWorldLocation(org.kynosarges.tektosyne.geometry.PointD)
result
is nearest to the specified location
java.lang.NullPointerException
- if location
is null
public double getDistance(PointD source, PointD target)
Graph
nodes.
Returns zero if the specified source
and target
are equal,
and the Euclidean distance between source
and target
otherwise.
This is equivalent to the absolute length of the edge that connects these vertices.
getDistance
does not check whether the Subdivision
actually contains
source
and target
, or whether they are connected by an edge.
getDistance
in interface Graph<PointD>
source
- the source node in the Graph
target
- the target node in the Graph
source
and target
java.lang.NullPointerException
- if source
or target
is null
public java.util.List<PointD> getNeighbors(PointD node)
Graph
node.
Returns an empty List
if node
is not a vertices()
key. Otherwise,
returns the destinations of all SubdivisionEdge
instances that originate from
node
. This is an O(ld n + m) operation, where n is the total number of
vertices()
and m is the number of half-edges originating from node
.getNeighbors
in interface Graph<PointD>
node
- the Graph
node whose direct neighbors to collectList
of all Graph
nodes that are directly connected
with node
, numbering from zero to connectivity()
java.lang.NullPointerException
- if node
is null
public PointD getWorldLocation(PointD node)
Graph
node.
Simply returns the specified node
, without checking
whether it is actually part of the Subdivision
.getWorldLocation
in interface Graph<PointD>
node
- the Graph
node whose world location to findPointD
location of node
, in world coordinatesjava.lang.NullPointerException
- if node
is null
public PointD[] getWorldRegion(PointD node)
Graph
node.
Returns the polygonal region that the user-defined vertexRegions()
collection
associates with the specified node
, if found, else, null
.getWorldRegion
in interface Graph<PointD>
node
- the Graph
node whose world region to findPointD
vertices defining the polygonal region
covered by node
, in world coordinatesjava.lang.NullPointerException
- if node
is null