public class SubdivisionSearch
extends java.lang.Object
Subdivision
.
Creates a search structure that achieves a query time of O(log n) for point location
in a planar Subdivision
with n full edges. However, the search structure itself
occupies O(n) fairly big objects which require O(n log n) steps to construct, and must
be recreated whenever the underlying Subdivision
changes.
Moreover, SubdivisionSearch
requires a minimum epsilon of 1e-10 for coordinate
comparisons to reliably construct its search structure, and must use the construction
epsilon for all point location queries. Use the brute force Subdivision.find(org.kynosarges.tektosyne.geometry.PointD, double)
algorithm to avoid construction costs or perform searches with a different epsilon.
The algorithm to incrementally construct a search structure for the trapezoidal map of a
planar subdivision was adapted from Mark de Berg et al., Computational Geometry
(3rd ed.), Springer-Verlag 2008, p.122-137. This implementation uses null half-edges and
Double.MAX_VALUE
to indicate the unbounded face, rather than placing an actual
bounding rectangle around the Subdivision
.
Modifier and Type | Field and Description |
---|---|
double |
epsilon
The maximum absolute difference at which two coordinates should be considered equal.
|
Subdivision |
source
The
Subdivision for which the SubdivisionSearch graph was created. |
Constructor and Description |
---|
SubdivisionSearch(Subdivision source,
boolean ordered)
Creates a
SubdivisionSearch graph for the specified Subdivision . |
Modifier and Type | Method and Description |
---|---|
SubdivisionElement |
find(PointD q)
|
java.lang.String |
format()
Returns a
String that represents the entire SubdivisionSearch graph. |
void |
validate()
Validates the structure of the
SubdivisionSearch graph. |
public final double epsilon
Subdivision.epsilon
of the associated
source
, whichever is greater.
The SubdivisionSearch
algorithm always uses a positive epsilon
to
guard against Subdivision.vertices()
with infinitesimal coordinate differences
that might corrupt the search structure. If you encounter exceptions or incorrect
search results for a given Subdivision
, try using a greater comparison
Subdivision.epsilon
in its creation.
public final Subdivision source
Subdivision
for which the SubdivisionSearch
graph was created.
Never null
. The SubdivisionSearch
graph is not updated to reflect
structural changes in the associated Subdivision
. You must create a new
SubdivisionSearch
to receive correct results for a changed source
.public SubdivisionSearch(Subdivision source, boolean ordered)
SubdivisionSearch
graph for the specified Subdivision
.
The ordered
parameter is intended for tests that require a known edge
insertion order. A random permutation is usually preferable, as the original
Subdivision.edges()
order can result in worst-case performance for the
SubdivisionSearch
algorithm.source
- the Subdivision
to searchordered
- true
to insert the Subdivision.edges()
of source
in their original order, false
to apply a random permutationjava.lang.NullPointerException
- if source
is null
public SubdivisionElement find(PointD q)
SubdivisionElement
at the specified PointD
coordinates within the associated source
.
Returns SubdivisionElement.NULL_FACE
if q
lies within the unbounded face
of the associated source
.
If q
coincides with a SubdivisionEdge
, find
always returns the twin
SubdivisionEdge
whose SubdivisionEdge.origin()
is lexicographically smaller
than its SubdivisionEdge.destination()
, according to PointDComparatorX
.
find
always uses the default epsilon
to determine whether q
coincides with an SubdivisionElement.edge()
or SubdivisionElement.vertex()
.
The SubdivisionSearch
algorithm does not support a comparison epsilon that is
significantly different from that which was used to construct the search structure.
q
- the PointD
coordinates to examineSubdivisionElement
that coincides with q
java.lang.NullPointerException
- if q
is null
public java.lang.String format()
String
that represents the entire SubdivisionSearch
graph.
Implemented as a new method, rather than overriding Object.toString()
,
because the returned String
may be hundreds or thousands of lines long.String
containing the Object.toString()
results for all nodes
in the SubdivisionSearch
graph, traversed in breadth-first orderpublic void validate()
SubdivisionSearch
graph.
Uses assert
statements to verify the structural invariants of the SubdivisionSearch
graph. Assertions must be enabled at runtime for validate()
to have any effect.java.lang.AssertionError
- if the structure of the SubdivisionSearch
graph is invalid