T
- the type of all nodes in the Graph
public class Visibility<T>
extends java.lang.Object
Graph
instances.
Starts on a specified starting node and recursively finds any adjacent nodes,
up to a specified maximum world distance, whose line of sight is not blocked by
any other examined nodes closer to the source. The opacity of any given node is
determined by a user-supplied Predicate
.
For each tested node, we consider its polygonal world region as defined by Graph.getWorldRegion(T)
. We draw the two tangents from the source node’s world location
to the extreme points of that region. An opaque node blocks visibility, across the angle
between its tangents, for any node whose nearest world region vertex is farther from the
source than that of the opaque node. A node is considered visible as long as a certain
fraction of its tangential arc remains unobscured, as defined by threshold()
.
If an opaque node obscures only the middle part of another node’s tangential arc, but
leaves partial arcs on both ends visible, only the greater of these partial arcs is
considered visible whereas the smaller is considered obscured. This simplifies visibility
testing, although very rarely visible nodes may be misclassified as obscured if the size
of world regions varies greatly among Graph
nodes.
Any graph node for which Graph.getWorldRegion(T)
returns null
is assigned
a default tangential arc, spanning one degree around its world location. This allows the
Visibility
algorithm to process graphs that do not define world regions for all
nodes, although the results are likely not very useful.
Modifier and Type | Field and Description |
---|---|
Graph<T> |
graph
The
Graph on which all searches are performed. |
Constructor and Description |
---|
Visibility(Graph<T> graph)
Creates a
Visibility algorithm for the specified Graph . |
Modifier and Type | Method and Description |
---|---|
boolean |
findVisible(java.util.function.Predicate<T> isOpaque,
T source,
double distance)
Finds all contiguous
graph nodes within the specified maximum
world distance that are visible from the specified source node. |
java.util.Map<T,NodeArc> |
nodeArcs()
Gets the source distances, tangential arcs, and visible fractions for all
graph nodes that were examined by the last search. |
java.util.List<T> |
nodes()
Gets all
graph nodes that were reached by the last successful search. |
void |
setThreshold(double value)
Sets the visibility threshold for any
graph node,
as a fraction of the sweep angle of its tangential arc. |
double |
threshold()
Gets the visibility threshold for any
graph node,
as a fraction of the sweep angle of its tangential arc. |
public Visibility(Graph<T> graph)
Visibility
algorithm for the specified Graph
.graph
- the Graph
on which all searches are performedjava.lang.NullPointerException
- if graph
is null
public boolean findVisible(java.util.function.Predicate<T> isOpaque, T source, double distance)
graph
nodes within the specified maximum
world distance that are visible from the specified source node.
Returns false
if graph
does not contain source
,
or if there are no visible nodes. Otherwise, returns true
and sets
nodes()
and nodeArcs()
to the result of the visibility search.
All nodes within the specified maximum distance
are considered visible,
except for those that are obscured by a node for which isOpaque
succeeds,
as described in the documentation of the Visibility
class.
If distance
is positive, any visible node must be reachable by a path
that only includes other nodes within distance
; otherwise, it will not
be found. This condition holds for any PolygonGrid
, and for any
Subdivision
that was created from a Delaunay triangulation.
isOpaque
- the Predicate
that determines whether a graph
node blocks the line of sightsource
- the source node within graph
where the search startsdistance
- the maximum world distance from source
to search,
or zero to search the entire graph
true
if one or more nodes are visible from source
within the specified distance
, else false
java.lang.IllegalArgumentException
- if distance
is less than zerojava.lang.NullPointerException
- if isOpaque
or source
is null
public java.util.List<T> nodes()
graph
nodes that were reached by the last successful search.
Returns an empty collection if the last findVisible(java.util.function.Predicate<T>, T, double)
call returned
false
, or if the method has not yet been called.
Otherwise, contains those graph
nodes in nodeArcs()
whose NodeArc.visibleFraction()
equals or exceeds the current threshold()
.
List
containing all graph
nodes that were reached
by the last successful findVisible(java.util.function.Predicate<T>, T, double)
call, not including the source nodepublic java.util.Map<T,NodeArc> nodeArcs()
graph
nodes that were examined by the last search.
Returns an empty collection if the last findVisible(java.util.function.Predicate<T>, T, double)
call returned
false
, or if the method has not yet been called.
Otherwise, contains all graph
nodes that were examined by findVisible(java.util.function.Predicate<T>, T, double)
, including partly or fully obscured nodes that were not added
to nodes()
, but excluding the source node.
Map
that maps all visited graph
nodes to the
corresponding NodeArc
instances created by findVisible(java.util.function.Predicate<T>, T, double)
public double threshold()
graph
node,
as a fraction of the sweep angle of its tangential arc.
The default is 1/3.NodeArc.visibleFraction()
for the NodeArc
of any graph
node that should be considered visiblepublic void setThreshold(double value)
graph
node,
as a fraction of the sweep angle of its tangential arc.
A value
of zero is interpreted as Double.MIN_NORMAL
, so a
graph
node is considered visible while even the smallest fraction
of its tangential arc remains unobscured.
A value
of one has the opposite effect. A graph
node is
considered visible only if its entire tangential arc remains unobscured.
Values between zero and one allow greater or lesser degrees of obscuration.
value
- the minimum NodeArc.visibleFraction()
for the NodeArc
of any graph
node that should be considered visiblejava.lang.IllegalArgumentException
- if value
is less than zero or greater than one