public abstract class PointDComparator extends java.lang.Object implements java.util.Comparator<PointD>, java.io.Serializable
PointD
instances,
given a specified epsilon for lexicographic coordinate comparisons.
Defines a Comparator
that lexicographically compares PointD
instances
with a given epsilon, applied to each dimension. PointDComparatorX
and
PointDComparatorY
provide implementations whose lexicographic ordering
prefers x- and y-coordinates, respectively.Modifier and Type | Field and Description |
---|---|
double |
epsilon
The epsilon used for coordinate comparisons.
|
Constructor and Description |
---|
PointDComparator()
Creates a
PointDComparator with an epsilon of zero. |
PointDComparator(double epsilon)
Creates a
PointDComparator with the specified epsilon. |
Modifier and Type | Method and Description |
---|---|
int |
findNearest(java.util.List<PointD> points,
PointD q)
Searches a sorted
PointD list for the element nearest to the specified location,
given the current epsilon for coordinate comparisons. |
PointD |
findNearest(java.util.NavigableSet<PointD> points,
PointD q)
Searches a
NavigableSet for the PointD element nearest to the
specified location, given the current epsilon for coordinate comparisons. |
<V> java.util.NavigableMap<PointD,V> |
findRange(java.util.NavigableMap<PointD,V> map,
RectD range)
|
java.util.NavigableSet<PointD> |
findRange(java.util.NavigableSet<PointD> points,
RectD range)
|
protected abstract double |
getPrimary(PointD point)
Gets the primary dimension of the specified
PointD . |
protected abstract double |
getSecondary(PointD point)
Gets the secondary dimension of the specified
PointD . |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
compare, comparing, comparing, comparingDouble, comparingInt, comparingLong, equals, naturalOrder, nullsFirst, nullsLast, reversed, reverseOrder, thenComparing, thenComparing, thenComparing, thenComparingDouble, thenComparingInt, thenComparingLong
public final double epsilon
Note: List.sort(java.util.Comparator<? super E>)
throws IllegalArgumentException
when supplied a
PointDComparator
whose epsilon
overlaps the coordinates of distinct
PointD
instances in both dimensions, resulting in the classification of
PointD
instances as equal when their PointD.equals(org.kynosarges.tektosyne.geometry.PointD, org.kynosarges.tektosyne.geometry.PointD, double)
and PointD.hashCode()
results signal inequality. ("Comparison method violates its general contract.")
public PointDComparator()
PointDComparator
with an epsilon of zero.public PointDComparator(double epsilon)
PointDComparator
with the specified epsilon.epsilon
- the maximum absolute difference at which coordinates should be considered equaljava.lang.IllegalArgumentException
- if epsilon
is less than zeropublic int findNearest(java.util.List<PointD> points, PointD q)
PointD
list for the element nearest to the specified location,
given the current epsilon for coordinate comparisons.
First approximates the index position of q
within points
by a lexicographic
binary search, using PointDComparator
methods with the current epsilon. The search
is then expanded to both increasing and decreasing index positions, using the Euclidean
distance of the first approximation, or of any subsequently found nearer element,
as the maximum search radius.
Once the vertical (PointDComparatorY
) or horizontal (PointDComparatorX
)
distances of the tested points
elements in both directions exceed the search
radius, findNearest
returns the zero-based index of the element with the smallest
Euclidean distance to q
.
The worst-case runtime is O(ld n + n), where n is the total number of points
.
However, the runtime for an evenly distributed point set is close to O(ld n) since
comparisons can be limited to a relatively narrow vertical or horizontal distance
around the initial approximation.
points
- a List
containing the PointD
locations to search,
sorted lexicographically using the current PointDComparator
q
- the PointD
location to find in points
q
in points
, if found;
otherwise, the zero-based index of the points
element with the smallest
Euclidean distance to q
java.lang.NullPointerException
- if points
or q
is null
,
or points
is empty or contains any null
elementspublic PointD findNearest(java.util.NavigableSet<PointD> points, PointD q)
NavigableSet
for the PointD
element nearest to the
specified location, given the current epsilon for coordinate comparisons.
First approximates the vicinity of q
within points
using NavigableSet.headSet(E, boolean)
and NavigableSet.tailSet(E, boolean)
. The search is then expanded
by both ascending and descending iteration, using the Euclidean distance of the first
approximation, or of any subsequently found nearer element, as the maximum search radius.
Once the vertical (PointDComparatorY
) or horizontal (PointDComparatorX
)
distances of the tested points
elements in both directions exceed the search radius,
findNearest
returns the element with the smallest Euclidean distance to q
.
The actual runtime depends on the supplied implementation of NavigableSet
.
For the algorithm to work, points
must use the PointDComparator
itself
as its SortedSet.comparator()
. This condition is accordingly checked.
points
- a NavigableSet
containing the PointD
locations to search,
sorted lexicographically using the current PointDComparator
q
- the PointD
location to find in points
q
if found in points
; otherwise, the
points
element with the smallest Euclidean distance to q
java.lang.IllegalArgumentException
- if the SortedSet.comparator()
of points
differs from the current PointDComparator
instancejava.lang.NullPointerException
- if points
or q
is null
,
or points
is empty or contains any null
elementspublic <V> java.util.NavigableMap<PointD,V> findRange(java.util.NavigableMap<PointD,V> map, RectD range)
NavigableMap
whose PointD
keys are
within the specified RectD
, given the current epsilon for coordinate comparisons.
Always returns a new NavigableMap
with the current PointDComparator
.V
- the type of all values in the NavigableMap
map
- the NavigableMap
whose PointD
keys to searchrange
- a RectD
indicating the coordinate range to findNavigableMap
containing all map
entries
whose PointD
keys are within range
java.lang.IllegalArgumentException
- if the SortedSet.comparator()
of map
differs from the current PointDComparator
instancejava.lang.NullPointerException
- if map
or range
is null
public java.util.NavigableSet<PointD> findRange(java.util.NavigableSet<PointD> points, RectD range)
PointD
elements in the specified NavigableSet
that are within
the specified RectD
, given the current epsilon for coordinate comparisons.
Always returns a new NavigableSet
with the current PointDComparator
.points
- the NavigableSet
whose PointD
elements to searchrange
- a RectD
indicating the coordinate range to findNavigableSet
containing all points
within range
java.lang.IllegalArgumentException
- if the SortedSet.comparator()
of points
differs from the current PointDComparator
instancejava.lang.NullPointerException
- if points
or range
is null
protected abstract double getPrimary(PointD point)
PointD
.