Class S2ClosestPointQuery<T>
Example usage:
void test(Listpoints, List targets) { // The template argument allows auxiliary data to be attached to each point (in this case, the // array index). S2PointIndex index = new S2PointIndexinvalid input: '<'>(); for (int i = 0; i invalid input: '<' points.size(); i++) { index.add(points.get(i), i); } S2ClosestPointQuery query = new S2ClosestPointQueryinvalid input: '<'>(index); query.setMaxPoints(15); for (S2Point target : targets) { for (Result result : query.findClosestPoints(target)) { // result.entry().point() is one of the found closest points. // result.entry().data() is the auxiliary data (the "points" array index). // result.distance() is the distance to the target point. doSomething(target, result.entry().point(), result.entry().data(), result.distance()); } } }
You can find either the k closest points, or all points within a given radius, or both (i.e.,
the k closest points up to a given maximum radius). E.g. to find all the points within 5
kilometers, call query.setMaxDistance(S1Angle.fromEarthDistance(5000));
.
You can also restrict the results to an arbitrary S2Region via setRegion(S2Region)
.
The implementation is designed to be very fast for both small and large point sets.
This class is not thread-safe. In particular, setters must not be called during queries.
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprivate static class
A type that is comparable on distance only.private static class
An edge query, used to find the closest points to a query edge.private static class
A point query, used to find the closest points to a query point.private static class
A queued cell waiting to be processed by the current query, ordered by distance to any point in the cell in ascending order.static class
A query result paired with the distance to the query target.private static interface
A kind of query target. -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate final S2PointIndex
<T> The index being queried.A small (invalid input: '<'6) cell covering of the indexed points.The intersection between the index andmaxDistance
.The intersection between the index andregionCovering
.private S2Iterator
<S2PointIndex.Entry<T>> The iterator for the last-known state of the index.private static final int
The maximum number of points to process by brute force.private static final int
The maximum number of points to process without subdividing further.private S1Angle
The max distance to search for points.The covering ofmaxDistance
.private S1ChordAngle
Temporary distance to continue searching during a query, generally the distance of the furthest point in the results found so far.private int
The max number of closest points to find.private final PriorityQueue
<S2ClosestPointQuery.QueueEntry> Unprocessed cells for the current query being processed.private S2Region
The region to restrict closest point search to.The covering ofindexCovering
.private final PriorityQueue
<S2ClosestPointQuery.Result<T>> Temporary queue of results sorted in descending order.private final S2PointIndex.Entry<T>[]
Temporary storage for index entries that are of interest during query processing.private boolean
Whether to use brute force, which is cheaper when the index has few edges. -
Constructor Summary
ConstructorsConstructorDescriptionS2ClosestPointQuery
(S2PointIndex<T> index) Construct a new query for the given index. -
Method Summary
Modifier and TypeMethodDescriptionprivate boolean
addCell
(S2CellId id, S2Iterator<S2PointIndex.Entry<T>> iter, boolean seek, S2ClosestPointQuery.Target target) Processes the cell atid
, adding the contents of the cell immediately, or if there are too many points, adding it to the queue to be subdivided.private void
coverRange
(S2CellId firstId, S2CellId lastId) Adds a cell to indexCovering that covers the given inclusive range.findClosestPoint
(S2Point target) Convenience method that returns the closest point to the given target point, or null if no points satisfy thegetMaxDistance()
andgetRegion()
criteria.findClosestPoints
(S2Point target) Returns the closest points totarget
that satisfy thegetMaxDistance()
,getMaxPoints()
, andgetRegion()
criteria, ordered by increasing distance.void
findClosestPoints
(List<S2ClosestPointQuery.Result<T>> results, S2Point target) AsfindClosestPoints(S2Point)
, but sorts the results and adds them at the end of the given list.private void
private void
Returns the closest points to the given edge AB.void
findClosestPointsToEdge
(List<S2ClosestPointQuery.Result<T>> results, S2Point a, S2Point b) AsfindClosestPointsToEdge(S2Point, S2Point)
, but adds results to the given list.private void
Returns the max distance between returned points and the given target.int
Returns the max number of closest points to find.Returns the region in which point searches will be done.index()
Returns the underlying S2PointIndex.private void
Computes the "index covering", which is a small number of S2CellIds that cover the indexed points.private void
initQueue
(S2ClosestPointQuery.Target target) private void
maybeAddResult
(S2PointIndex.Entry<T> entry, S2ClosestPointQuery.Target target) void
reset()
Resets the query state.void
setMaxDistance
(S1Angle maxDistance) Sets a new max distance to search for points.void
setMaxPoints
(int maxPoints) Sets a new max number of closest points to find.void
private List
<S2ClosestPointQuery.Result<T>> toList
(List<S2ClosestPointQuery.Result<T>> list) Creates an empty list if 'list' is null, and then polls all results out ofresults
into the given list in reverse order, and returns it.(package private) void
useBruteForce
(boolean useBruteForce) Sets whether distances are computed using "brute force" (i.e., by examining every point) rather than using the S2PointIndex.
-
Field Details
-
MAX_BRUTE_FORCE_POINTS
private static final int MAX_BRUTE_FORCE_POINTSThe maximum number of points to process by brute force.- See Also:
-
MAX_LEAF_POINTS
private static final int MAX_LEAF_POINTSThe maximum number of points to process without subdividing further.- See Also:
-
index
The index being queried. -
maxPoints
private int maxPointsThe max number of closest points to find. -
maxDistance
The max distance to search for points. -
region
The region to restrict closest point search to. -
useBruteForce
private boolean useBruteForceWhether to use brute force, which is cheaper when the index has few edges. -
indexCovering
A small (invalid input: '<'6) cell covering of the indexed points. -
queue
Unprocessed cells for the current query being processed. -
iter
The iterator for the last-known state of the index. New instance built byreset()
. -
regionCovering
The covering ofindexCovering
. Type is ArrayList due toS2RegionCoverer
. -
maxDistanceCovering
The covering ofmaxDistance
. Type is ArrayList due toS2RegionCoverer
. -
intersectionWithRegion
The intersection between the index andregionCovering
. -
intersectionWithMaxDistance
The intersection between the index andmaxDistance
. -
tmpPoints
Temporary storage for index entries that are of interest during query processing. -
results
Temporary queue of results sorted in descending order. -
maxDistanceLimit
Temporary distance to continue searching during a query, generally the distance of the furthest point in the results found so far. Beyond this distance, we can safely ignore further candidate points. Candidates that are exactly at the limit are ignored; this makes things easier in the case of S2ClosestEdgeQuery and should not affect clients since distance measurements have a small amount of error anyway.Initially this is the same as the maximum distance specified by the user, but it can also be updated by the algorithm (see maybeAddResult).
-
-
Constructor Details
-
S2ClosestPointQuery
Construct a new query for the given index. Must call reset() before using the query, if the index has been modified since the query was constructed.
-
-
Method Details
-
reset
public void reset()Resets the query state. This method must be called after modifying the underlying index. -
index
Returns the underlying S2PointIndex. -
getMaxPoints
public int getMaxPoints()Returns the max number of closest points to find. -
setMaxPoints
public void setMaxPoints(int maxPoints) Sets a new max number of closest points to find. -
getMaxDistance
Returns the max distance between returned points and the given target. Default is +inf. -
setMaxDistance
Sets a new max distance to search for points. -
getRegion
Returns the region in which point searches will be done. -
setRegion
-
useBruteForce
void useBruteForce(boolean useBruteForce) Sets whether distances are computed using "brute force" (i.e., by examining every point) rather than using the S2PointIndex.This is package private, as it is intended only for testing, benchmarking, and debugging.
Do not call before init().
-
toList
Creates an empty list if 'list' is null, and then polls all results out ofresults
into the given list in reverse order, and returns it. -
findClosestPoints
Returns the closest points totarget
that satisfy thegetMaxDistance()
,getMaxPoints()
, andgetRegion()
criteria, ordered by increasing distance. If there are no criteria set, then all points are returned. -
findClosestPoints
AsfindClosestPoints(S2Point)
, but sorts the results and adds them at the end of the given list. -
findClosestPoint
Convenience method that returns the closest point to the given target point, or null if no points satisfy thegetMaxDistance()
andgetRegion()
criteria. -
findClosestPointsToEdge
Returns the closest points to the given edge AB. Otherwise similar tofindClosestPoints(S2Point)
. -
findClosestPointsToEdge
public void findClosestPointsToEdge(List<S2ClosestPointQuery.Result<T>> results, S2Point a, S2Point b) AsfindClosestPointsToEdge(S2Point, S2Point)
, but adds results to the given list. -
initIndexCovering
private void initIndexCovering()Computes the "index covering", which is a small number of S2CellIds that cover the indexed points. -
coverRange
Adds a cell to indexCovering that covers the given inclusive range. This is done withS2CellId.getCommonAncestorLevel(S2CellId)
, which requires the cells have a common ancestor. -
findClosestPointsToTarget
-
findClosestPointsBruteForce
-
findClosestPointsOptimized
-
maybeAddResult
-
initQueue
-
addCell
private boolean addCell(S2CellId id, S2Iterator<S2PointIndex.Entry<T>> iter, boolean seek, S2ClosestPointQuery.Target target) Processes the cell atid
, adding the contents of the cell immediately, or if there are too many points, adding it to the queue to be subdivided. Ifseek
is false, theniter
must already be positioned at the first indexed point within this cell.- Returns:
- true if the cell was added to the queue, and false if it was processed immediately (in
which case
iter
is left positioned at the next cell in S2CellId order.
-